여러 참가자의 점수가 담긴 리스트가 주어졌을 때, 그중 준우승(두 번째로 높은) 점수를 찾아야 하는 문제입니다.
예를 들어 입력이 scores = [5,8,2,6,8,5,8,7]이라면 출력은 7입니다. 최고 점수(우승 점수)는 8이고, 그다음으로 큰 점수는 7이기 때문입니다.
해결 방법
이 문제는 다음과 같은 단계를 따라 해결할 수 있습니다.
- 변수
winner(최고 점수)를 -99999로 초기화합니다. - 변수
runner_up(준우승 점수)도 -99999로 초기화합니다. - scores 리스트의 각 요소
i에 대해 다음을 반복합니다.i가winner보다 크면 → 기존winner값을runner_up에 저장하고,winner를i로 갱신합니다.i가winner보다 작으면서runner_up보다 크면 →runner_up을i로 갱신합니다.
- 반복이 끝나면
runner_up을 반환합니다.
이 방식은 리스트를 한 번만 순회하므로 시간 복잡도가 O(n)으로 매우 효율적입니다. 또한 중복된 최고 점수가 여러 개 있더라도, 조건에서 i < winner(엄격한 비교)를 사용하기 때문에 정확한 준우승 점수를 구할 수 있습니다.
예제 코드
아래 파이썬 구현 예시를 통해 더 자세히 이해해 보겠습니다.
def solve(scores):
winner = -99999
runner_up = -99999
for i in scores:
if (i > winner):
winner, runner_up = i, winner
elif (i < winner and i > runner_up):
runner_up = i
return runner_up
scores = [5,8,2,6,8,5,8,7]
print(solve(scores))
입력
[5,8,2,6,8,5,8,7]
출력
7
정리
이 알고리즘은 최고 점수와 준우승 점수를 동시에 추적하면서 리스트를 한 번만 순회하는 간단하고 효율적인 방법입니다. 초기값을 충분히 작은 음수(-99999)로 설정함으로써 음수 점수가 포함된 경우에도 올바르게 동작합니다.