1300번 K번째 수

코딩테스트 : 1300번 K번째 수

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

51828

19424

14178

37.993%

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

public class BackJoon
{
    public static void Main()
    {
        // 아이디어 : 숫자들을 다 저장하고 푼다 ? => 비효율적

        // X라는 숫자가 몇 번째에 위치하는지 찾는다
        // X보다 낮은 숫자를 가진 것을 배열을 순회하면서 찾음 => 이것만 알면 된다. 


        long N = long.Parse(Console.ReadLine());
        long K = long.Parse(Console.ReadLine());

        long start = 1;
        long end = N * N;
        long answer = 0;
        while (start <= end)
        {
            long mid = (start + end) / 2;

            long count = 0;
            for (long i = 1; i <= N; i++)
            {
                count += Math.Min(mid / i, N);
            }
            if (count >= K)
            {
                answer = mid;
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }
        Console.WriteLine(answer);
    }
}

 

처음에는 직접 표를 그려보며 규칙을 찾으려고 했다.
N × N 크기의 배열을 기준으로, 특정 제곱수보다 작은 수들이 배열 안에 얼마나 포함되는지를 세어보고 규칙을 추측해보려 했다.

하지만 배열의 크기가 커질수록 제곱수 이하의 원소 개수가 일정한 패턴을 따르지 않아, 이 방법은 어려움이 많았고 다른 접근을 시도하게 되었다.

 

자꾸 착각하게 되는 측면이 있는데, B[k]를 구한다는 것은 k번째 인덱스에 있는 수 X를 구한다는 말과 같다.

임의의 수 X를 정하고, 그 수를 기준으로 N * N 배열에서 그보다 작은 수들의 갯수를 구하고, 이를 바탕으로 이분 탐색을 진행하면

답을 구할 수 있다. 다만 주의해야 할 점은 똑같은 숫자가 계속 나올 수 있으므로  ( 1, 2, 2, 4, 5, 6, 6 ~  ) 이를 주의해 종료조건을 설정해야 한다. 

 

이제 문제는 X라는 숫자가 주어졌을 때, 그보다 작은 숫자들의 갯수를 구하는 방법이다. 

이를 한참 헤매다가 그냥 단순한 반복문으로 해결하게 되었다. 

예를 들어서 i번째 행에서 X보다 작은 숫자의 갯수는 X / i개이다. 단, 특정 행의 모든 수가 포함된 경우보다, X / i 가 클 수가 있으므로 최댓값을 N으로 고정한다. 이를 모든 줄에서 반복해주면 N * N 배열에서 X의 수보다 작은 수들의 갯수가 도출된다.

이를 바탕으로 비교해서 이분탐색을 진행하였다. 

 

등호 처리를 신중하게 해야 한다. start <= end 조건은, 수렴 후 마지막 값을 한 번 더 확인하기 위한 조건이고

count >= K 조건은, 같은 숫자가 배열에서 여러 번 존재할 수 있기 때문에 현재 값이 정답일 가능성을 남겨두고 ( answer = mid)

범위를 줄여나가는 처리이다.  예를 들어 2는 (1,2)와 (2,1) 등에서 중복으로 등장할 수 있기 때문에,

count == K가 아니라 count >= K일 때도 탐색을 계속해야 한다.

 

이런 문제를 처음 맞닥뜨렸을 때, 10의 5승 * 10의 5승은 21억보다 큰 100억이므로, long으로 진행하는 것이 바람직하다.