[백준 25305] 커트라인 (python3)

 

 

 

 

 

 

문제 분석

기본 정렬 알고리즘을 구현해서 풀거나 파이썬의 sort() 메소드, sorted()  함수를 이용해서 문제를 풀 수 있다.

 

# sort 함수를 사용해서 쉽게 풀기

# N : 리스트의 길이
# k : 출력할  리스트 인덱스 값
N, k = map(int, input().split(" "))
pri_list = list(map(int,input().split()))

# 점수가 큰 값에서부터 정렬할 수 있도록 처리
pri_list.sort( key=lambda x:-x)

# 인덱스는 0에서 시작하므로 k-1번째 인덱스가 커트라인이 된다.
print(pri_list[k-1])

# 선택 정렬 알고리즘을 구현해서 만들기
N, k = map(int, input().split(" "))
pri_list = list(map(int,input().split()))

## 선택 정렬 사용

for pri in range(len(pri_list)):
    # 지금 가장 큰 녀석이 초기 값
    max_step = pri
    
    # 2) pri+1 위치의 값부터 끝까지 다 돌리기
    for i in range(pri+1, len(pri_list)):
        if pri_list[i] > pri_list[max_step]: # 더 큰 값이 나타났다면 max값을 변경
            max_step = i
        else:
            pass
           
    # 다음 자리로 교환하기 위해 멀티할당으로 바로 swap
    pri_list[max_step], pri_list[pri] = pri_list[pri], pri_list[max_step]

print(pri_list[k-1])

 

파이썬 sort() 메소드는 시간복잡도가 n, 선택 정렬은 n^2 이라 시간에서 큰 차이가 나는 걸 알 수 있다.

 

마무리 

---

정렬 구현 방식에서는 선택 정렬로 풀어봤는데, 시간이 날 때 간단하게 삽입 정렬과 버블 정렬로 풀어본 뒤, 퀵 정렬도 구현해서 직접 풀어보고 시간의 차이를 체크 해봐야겠다.