[BOJ] 16455 | K번째 수 찾는 함수

 

16455 | K번째 수 찾는 함수
https://www.acmicpc.net/problem/16455

 

 

# 크기가 N인 수열 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 
# 앞에서부터 K번째 있는 수를 리턴하는 함수를 작성하시오.

# -> 주어진 배열에서 오름차순으로 정렬했을 때, K 번째 있는 수를 return 하는 문제 입니다

# a 는 배열, k 는 찾고자 하는 위치 값 (k번째)
def kth(a, k):
    # [0, 0, 0 ....] -> 0이 44725개 있는 배열
    cnt1 = [0] * 44725
    cnt2 = [0] * 44725

    # 배열 a 를 돌며 하나씩 원소를 꺼냄
    for i in a:
        # 인덱스 : i를 44725로 나눈 몫에 22359를 더한 값
        # 해당 인덱스를 가진 배열 요소에 1을 더함
        cnt1[i // 44725 + 22359] += 1

    # cnt1 배열을 돌며 i1(인덱스) c(요소) 값을 꺼냄
    for i1, c in enumerate(cnt1):
        # k (찾고자하는 위치 값 - k번째)에서 c 를 뺌
        k -= c
        if k <= 0: 
            # 만약 k 가 0 이하라면, 반복문 중단
            k += c
            break

    # 배열 a 를 돌며 하나씩 원소를 꺼냄
    for i in a:

        # 만약 i 를 4472 로 나눈 몫에 22359를 더한 값이 i1(아까 위에서 break 중단된 값) 과 같다면
        if i // 44725 + 22359 == i1: 
            # 인덱스 : i를 44725 로 나눈 나머지
            # 해당 인덱스를 가진 배열 요소에 1을 더함
            cnt2[i % 44725] += 1

    # cnt2 배열을 돌며 i2(인덱스) c(요소) 값을 꺼냄
    for i2, c in enumerate(cnt2):
        # k (찾고자하는 위치 값 - k번째)에서 c 를 뺌
        k -= c
        if k <= 0: 
            # 만약 k 가 0 이하라면, 반복문 중단
            break

    # 몇 번째인지 return
    return i2 + (i1 - 22359) * 44725


# 함수 호출, 
print(kth([123,1,2,3], 2))