[프로그래머스 Python] 명예의 전당 (1)

💡문제 설명

💡제한 사항 및 입출력 예시

k = 4 인 경우

💡나의 정답 코드

# 기본적으로 for 문이 실행될 때 마다 reverse sorting(역순 정렬) 수행을 하고, 가장 작은 값 [-1]인덱스 값을 answer 에 추가

1. 명예의 전당 (glory) 리스트가 다 채워지기전 까지는 계속 더해준다 ; len(glory) < k

2. 다 채워진 후, glory 리스트의 가장 작은 값과 해당 순서의 s 값과 비교했을 때 s 값이 더 큰 경우에 glory 리스트의 가장 작은 값을 제거해주고 (pop 함수 활용) s 값을 glory 에 추가해준다.

 

-> 이렇게 실행하면 리스트 개수는 계속해서 k 개로 유지되며, answer 에는 해당 일차에 가장 작은 값을 반환 가능 !

def solution(k, score):
    answer = []
    glory = []

    for s in score : 
        if len(glory) < k : # glory 가 3을 넘지 않도록
            glory.append(s)
        elif (len(glory) >= k) and (glory[-1] < s) : # len(glory) > 3
            glory.pop()
            glory.append(s)
        glory.sort(reverse=True)
        answer.append(glory[-1])
    return answer

💡다른 분의 조금 더 간결한 코드

1. glory 리스트에 계속해서 더하는 것은 동일하나

2. 조건을 리스트의 길이가 k 를 넘어섰을 때, 더해진 s 값을 포함해서 가장 작은 값을 remove 해주는 방식으로 수행

 

answer = [] 
glory = []

for s in score : 
    glory.append(s)
    if (len(glory) > k) : 
        glory.remove(min(glory))
    answer.append(min(glory))
answer

 

💡두 코드의 비교

나의 코드	리스트를 매번 정렬하기 때문에 시간 복잡도가 상대적으로 높다. 매 반복마다 O(k log k)의 시간 복잡도를 가진다.
다른 분의 코드	소값을 찾고 제거하는 연산은 O(k) 시간이 소요된다. 이는 정렬보다 효율적.

 

*시간복잡도 기준 : per iteration

 

---