1300
-
[백준]1300: K번째 수 - JAVA문제풀이/백준 2021. 5. 13. 15:05
[백준]1300: K번째 수 풀이 이분탐색 문제이다. 문제의 조건에 따라 직접 배열을 만들고, 정렬하는 것도 방법 중 하나이겠지만 입력 조건에 N은 10의 5제곱 이기 때문에 이를 2차원 배열로 만들면 메모리 소비와 시간도 엄청 걸릴 것 이다. 그러므로 이분탐색으로 풀어야 한다. 문제의 예제입력을 푸는 과정을 살펴보자. 배열 A를 2차원 배열로 표현하면 다음과 같다. 배열A 1 2 3 2 4 6 3 6 9 이때, 6이라는 숫자가 오름차순 정렬되었을때 몇 번째에 오는지 알아보자. 1번열은 모두 6이하 이므로 3을 더해준다. 2번열은 모두 6이하 이므로 3을 더해준다. 3번열은 3, 6 두개의 숫자가 6이하 이므로 2를 더해준다. 즉, 6은 8번째에 오는 숫자가 된다. 진짜인지 확인해 보자. A를 오름차순 ..