[프로그래머스/Python] 명예의 전당(1) (정렬/구현) Lv1

---

문제 간단 요약 및 설명

매일 점수가 하나씩 발표된다.
지금까지 나온 점수 중 상위 k개를 “명예의 전당”에 유지한다.

매일 명예의 전당에 포함된 점수들 중
가장 낮은 점수를 기록하여 반환하는 문제이다.

---

🔥 나의 풀이 및 시행착오

1️⃣ 첫 번째 시도 : 실패

처음에는 문제를 다음과 같이 k를 기준으로 나누어 접근했다.

1) 2일차부터 k일까지
2) k일 이후부터

단, k 보다 score 길이가 짧은 경우까지 고려하지 못해 실패했다.

def solution(k, score):
    answer = [score[0]]
    honor = [score[0]]
    days = len(score)
        
    for i in range(2, k+1):
        honor.append(score[i-1])
        answer.append(min(honor))
    
    for j in range(k+1, days + 1):
        if answer[-1] < score[j-1]:
            honor.sort(reverse=True)
            honor[-1] = score[j-1]
            answer.append(min(honor))
        else:
            answer.append(answer[-1])
        
    return answer

2️⃣ 두 번째 시도 : 성공

🔍 실패 원인 : k보다 score 길이가 짧은 경우를 생각해보았는가?
🚀 해결 방법 : k보다 score 길이가 짧은 경우를 조건으로 나누어 따로 처리

이 방식으로도 풀 수는 있다. 다만 좋은 풀이는 아니다.

def solution(k, score):
    answer = [score[0]]
    honor = [score[0]]
    days = len(score)
    
    if k > days:
        for i in range(2, days+1):
            honor.append(score[i-1])
            answer.append(min(honor))
        return answer
        
    
    for i in range(2, k+1):
        honor.append(score[i-1])
        answer.append(min(honor))
    
    for j in range(k+1, days + 1):
        if answer[-1] < score[j-1]:
            honor.sort(reverse=True)
            honor[-1] = score[j-1]
            answer.append(min(honor))
        else:
            answer.append(answer[-1])
        
    return answer

---

💬 GPT의 피드백

네 코드는 “구간을 나눠서 처리”하고 있어

이 코드는 문제를 이렇게 보고 있는 거야.

• 첫째 날은 따로 처리
• 2일차 ~ k일차도 따로 처리
• k+1일차부터 또 따로 처리
• k가 전체 날짜보다 큰 경우도 따로 처리

즉, 상황별로 나눠서 계산하고 있어.

이 방식의 단점은
문제를 풀다 보면 “예외 처리”가 계속 늘어난다는 거야.

예를 들면 이런 생각이 계속 생겨:

• 첫날은 이미 넣었으니까 2일부터 시작해야 하나?
• k가 days보다 크면?
• k일까지는 그냥 넣기만 하면 되나?
• 그 다음부터는 교체만 하면 되나?

🔥 이런 식으로 코드가 점점 “문제 자체”보다 “예외를 다루는 코드”가 돼버리기 쉬워.

그렇다면 어떻게 해야하나?

정석 코드는 “매일 같은 규칙만 반복”해

💻 정석 코드

이 문제는 정답 리스트를 한 번에 만드는 문제가 아니라,
하루씩 보면서 명예의 전당 상태를 갱신하는 문제야.

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

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

즉 핵심은:

1. 오늘 점수가 들어온다
2. 명예의 전당 후보에 반영한다
3. 상위 k개만 남긴다
4. 그중 최하위 점수를 answer에 넣는다

이걸 매일 반복하면 끝이야.

문제를 이렇게 보면
“처음 k일”, “그 이후”로 나눌 필요가 없어져.
즉, 첫날도 똑같고 둘째 날도 똑같고 마지막 날도 똑같아.

이게 정석 풀이가 자연스러운 가장 큰 이유야.
문제를 매일 반복되는 하나의 규칙으로 바꿨기 때문이야.

🤔 앞으로 비슷한 문제에서 어떻게 생각하면 좋을까?

1) 상태를 유지하는 방식으로 접근해야 한다

이 문제의 핵심은 “정답을 계산”하는 것이 아니라
👉 매 순간 명예의 전당 상태를 유지하는 것이다.

2) 구간을 나누지 말고 동일한 규칙을 반복하자

• 넣는다
• k 초과면 최소값 제거
• 최솟값 기록

이 규칙 하나로 모든 케이스를 처리할 수 있다.

3) 결과 배열이 아니라 상태 배열을 기준으로 판단하자

• answer → 출력용
• honor → 상태 관리

이 둘을 분리하면 로직이 훨씬 명확해진다.

4) 문제를 이렇게 바라보면 쉬워진다

• 유지해야 하는 상태: 상위 k개
• 새로운 값이 들어왔을 때: 넣고, 넘치면 제거
• 출력: 현재 상태의 최솟값

이 3단계로 생각하면 대부분의 구현 문제가 훨씬 단순해진다.