[백준 알고리즘] - K번째 수 (1300번) with Python

📎 간략한 문제 정리

• 2차원 배열 A의 요소는 다음과 같이 정의됩니다.

  A[i][j] = i*j

  이 리스트를 1차원으로 만든 후 k번째 요소를 찾는 문제입니다.

📈 문제 분석

• 배열을 일반적으로 정렬하기 위해서는 O(NlogN)의 속도가 발생합니다. 문제에 주어진 N의 범위가 100000이므로 NlogN은 약 1600000 정도로 속도 이슈가 발생하지 않을 것 같습니다. -> 메모리 이슈가 발생합니다. 속도에는 문제가 없을지 모르지만 메모리에 문제가 발생합니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 병합정렬은 O(NlogN)으로 tim sort 역시 O(NlogN)이라서 우선 tim sort를 활용해보겠습니다.
• 위의 방법은 메모리 이슈가 발생하므로 메모리와 속도가 tim sort보다 동시에 여유가 있는 Heap Sort를 활용해보겠습니다. -> Heap Sort도 메모리 초과입니다.

💻 풀이한 코드

from sys import stdin
input = stdin.readline
N, k = int(input()), int(input())
start, end = 1, k
answer = 0
while start <= end:
    mid = (start + end)//2
    temp = 0
    for i in range(1, N+1):
        temp += min(N, mid//i)
    if temp < k:
        start = mid + 1
    else:
        answer = mid
        end = mid - 1
print(answer)

📝 해결 과정에서 만난 문제, 고민들

• 메모리 이슈:

  일반적으로 정렬을 생각할 때 big-O만 생각한 경향이 있습니다. 분명 메모리도 고려해야할 요소입니다.

  

  처음 시도했던 Tim Sort는 Insertion Sort와 Merge Sort를 합친 것입니다.

• 문제가 병합 정렬 섹션에 있는 줄 착각하여 정렬 풀이에 고착화 되었습니다. 섹션 단위로 풀고 있기 때문에 어느 정도의 고정관념이 있을 수 있지만 주의할 필요가 있습니다.

• 문제만 봤을 때는 전혀 이분 탐색의 문제 같지 않습니다. 카카오 기출 문제 중 이분 탐색 문제 역시 마찬가지였는데 어려운 이분탐색 문제는 탐색의 기준이 문제에 있는 것이 아니라 결과물에 있어서 이분탐색으로 풀이가 가능한지 보이지 않습니다.

🤩 이 문제에서 배운 점

• 이분 탐색의 전제조건은 탐색하려는 배열이 정렬되어 있어야 한다는 것입니다. 그래서 정렬되지 않은 상태인 B 배열에서는 어차피 이분 탐색을 사용할 수 없기 때문에 이 문제는 이분 탐색을 사용할 수 없는 문제라고 단정지었습니다. 하지만 생각해보면 i*j가 요소이기 때문에 A 배열에 각 행의 요소들은 오름차순을 유지할 수 밖에 없습니다. 즉, 각 행단위로 어떤 수보다 큰 수, 작은 수의 개수를 구하면 전체에서 어떤 수보다 작은 수의 개수를 구할 수 있습니다.

• 예를 들어 N이 10인 배열을 생각해보겠습니다.

  1 2 3 4 5 6 7 8 9 10

  2 4 6 8 10 12 14 16 18 20

  3 ...

  4 ...

  위와 같은 배열에서 30보다 작은 수의 개수를 구해보겠습니다. 우선 첫 행에서 30보다 작은 수의 개수는 30//1 = 10개입니다.(최대 개수가 N개입니다) 두번째 행에서 역시 30//2 = 10개 입니다. 3행은 30//3 = 10개입니다. 4행은 30//4 = 7입니다. 10행은 30//10 = 3개입니다.

• 이 문제에서 충격받은 포인트는 이분 탐색의 기준이 1부터 k 사이라는 것입니다. 이렇게 정의할 수 있는 이유는 배열의 정의를 보면 알 수 있습니다. 계속 헷갈렸던 점은 왜 탐색의 기준이 1부터 N^2이 아닌가 였습니다. 가능한 범위가 최대 N^2이기 때문입니다. 하지만 탐색의 기준은 k번째 요소에 들어있는 숫자가 무엇인가입니다. 생각해보면 k번째 수에는 k보다 큰 수가 들어있을 수 없습니다. 그래서 검색의 범위는 k까지면 충분합니다.

  탐색의 범위인 start, end는 k번째 수가 될 수 있는 후보의 범위라고 정의할 수 있습니다. 시작점과 끝점을 기준으로 k번째 수가 될 수 있는 수인지 판단합니다. 각 행에 k번째 수가 될 수 있는 후보보다 작은 수의 개수는 각 행 i에서 min(N, mid//i)가 됩니다. 이유는 다음과 같습니다.

  우선 각 행의 요소수는 N을 넘을 수 없기 때문에 min으로 처리가 됩니다. 그리고 각 행의 요소를 보면

  i, 2 * i, 3 * i, ..., 10*i

  로 구성되어 있기 때문에 위의 식을 i로 나누면

  1, 2, 3, ..., 10

  mid // i

  가 됩니다. 예를 들어 mid//i가 4라면 저 행에서 4보다 작은 수는 총 4개이고, i를 다시 곱해서 생각해보면 이 행에서 mid보다 작은 수의 개수는 4개가 됩니다. 1씩 증가하는 오름차순이기 때문에 나눈 값 자체가 개수가 됩니다. 그렇게 각 행에서 후보 mid보다 작은 수의 총합을 계산했을 때 k보다 작다면 해당 후보는 k번째 수가 절대 될 수 없기 때문에 start를 재조정하여 다시 탐색하고, 만약 총합이 k보다 크거나 같다면 이것은 k번째 수가 될 수 있으므로 답을 저장하고, 이것보다 더 작은 수도 선택 가능할 수 있기 때문에 end를 재조정하여 다시 탐색합니다.

• 이 문제의 포인트는 k번째 수를 선택할 때, 정렬하여 k번째 수를 찾을 수도 있지만 역발상으로 k번째 수가 될 수 있는 것은 무엇인가를 생각하는 것이었습니다.

https://www.acmicpc.net/problem/1300

https://d2.naver.com/helloworld/0315536