알고리즘 - k번째 숫자 찾기

K번째 숫자 찾기

n개의 숫자가 차례대로 주어질 때, 매 순간마다 “지금까지 입력된 숫자들 중에서 k번째로 작은 수”를 반환하는 프로그램을 작성하세요. 프로그램의 입력으로는 첫째줄에 n과 k가 입력되고, 둘째줄에 n개의 숫자가 차례대로 주어집니다.

 

문제 조건

• n은 100보다 작은 숫자입니다.
• 매 순간마다 지금까지의 입력중 kk번째로 작은 수를 출력하되, 없다면 -1을 출력합니다.

입력 예시 

10 3
1 9 8 5 2 3 5 6 2 10

 

출력 예시

-1 -1 9 8 5 3 3 3 2 2

10개의 숫자가 차례대로 주어집니다. 맨 처음 1만 입력을 받았을 경우, 3번째로 작은 숫자가 없으므로 -1을 출력합니다. 그 다음 9도 마찬가지입니다. 세 번째로 숫자 8을 입력받는 순간, 지금까지 입력받은 숫자는 1, 9, 8 세 개이고, 이 중 3 번째로 작은 숫자인 9를 출력합니다. 마찬가지로 숫자 하나를 입력받을 때 마다 3번째로 작은 숫자를 출력합니다.

 

 

 

---

풀이

문제를 해결하는 방법

1. 숫자 하나를 입력받는다.
2. 지금까지 받은 숫자들을 정렬한다.
3. k번째로 작은 숫자를 출력한다.

def findKth(myInput, k) :
    '''
    매 순간마다 k번째로 작은 원소를 리스트로 반환합니다.
    '''

    result = []
    data = []
    
    for element in myInput : 
        data.append(element)
        data.sort()
        
        # data[k-1] = 우리가 찾는 값
        # data에 들어있는 수가 k보다 적을 땐?
        
        if len(data) < k:
            result.append(-1)
        else:
            result.append(data[k-1])
    
    return result

def main():
    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    firstLine = [int(x) for x in input("n과 k를 입력하세요 (예시:10 3): ").split()]
    myInput = [int(x) for x in input("n개의 숫자를 차례대로 입력하세요 (예시:1 9 8 5 2 3 5 6 2 10): ").split()]

    print('정렬 결과: ', *findKth(myInput, firstLine[1]))
if __name__ == "__main__":
    main()