3등 찾기

무엇을 만드나

1등을 찾는 방법으로 3등도 찾을 수 있을까요?

주어진 문제

여러 사람의 이름과 점수를 입력받아, 점수가 세 번째로 높은 사람의 이름을 내놓는 프로그램을 만듭니다.

가장 높은 점수를 찾는 것은 어렵지 않습니다. 하나씩 보며 가장 큰 것만 들고 다니면 되니까요. 그런데 세 번째는 그 방법으로 곧장 되지 않습니다. 순서대로 늘어놓고 세 번째를 꺼내는 편이 훨씬 간단합니다.

단계	여기서 답할 질문
1 요구 분석	무엇을 내놓고, 같은 점수가 있으면 어떻게 할 것인가
2 설계	무엇을 기준으로 어떤 방향으로 늘어놓을 것인가
3 구현	이름과 점수를 어떻게 한 덩어리로 담을 것인가
4 테스트	3등을 헷갈리게 만드는 값은 무엇인가

먼저 개발 문서 양식을 내려받으세요

읽기만 하지 말고 직접 채워 보세요. 단계마다 자기 답을 적어 두면 그 기록이 요구 사항 명세서이자 설계서가 됩니다. 답을 보기 전에 먼저 적어 봅니다.

Python 양식 내려받기 C 양식 내려받기

요구 분석과 설계는 언어와 상관없습니다. 두 양식의 앞부분은 같고, 구현을 적는 자리만 언어에 맞춰 다릅니다. 수업에서 쓰는 언어에 맞는 것을 받으면 됩니다. 이 강의노트의 코드 예시는 파이썬으로 되어 있습니다.

1단계 · 무엇을 만들 것인가

「3등」이라는 말이 생각보다 애매합니다.

되물어야 할 것들

같은 점수가 있으면? 1등이 둘이면 그다음은 2등인가요 3등인가요
사람이 셋보다 적으면? 3등이 없습니다
이름만 내놓나요? 점수도 함께 보여 주나요
이름에 공백이 들어갈 수 있나요?

정리한 요구 사항

첫 줄에 사람 수를 받고, 그다음 줄부터 이름과 점수를 공백으로 띄어 받는다.
이름에는 공백이 들어가지 않는다.
점수가 높은 순으로 늘어놓았을 때 세 번째에 오는 사람의 이름을 내놓는다.
같은 점수가 있어도 사람 수만큼 자리를 차지하는 것으로 본다. 「공동 1등 다음은 2등」처럼 세지 않는다.
사람은 세 명 이상 들어온다고 본다.

4번이 없으면 답이 달라집니다

점수가 100, 100, 95, 90일 때 3등은 누구일까요? 줄을 세우면 세 번째는 95점인 사람이지만, 공동 1등 다음을 2등으로 세면 95점은 2등이 되고 3등은 90점인 사람이 됩니다. 어느 쪽도 틀리지 않습니다. 그래서 정해서 적어 두어야 합니다.

스스로 확인

점수가 100, 95, 95, 90일 때 요구 사항 4번을 따르면 3등은 몇 점인 사람일까요? 그리고 그 답이 둘 중 누구인지는 정해져 있나요?

2단계 · 늘어놓고 꺼낸다

무엇을 기준으로 늘어놓을지 말해 주어야 합니다.

토막	무엇을 정하는가
입력	사람 수 하나, 그다음 사람 수만큼의 이름과 점수
처리	이름과 점수를 짝지어 담고, 점수가 높은 순으로 늘어놓는다
출력	세 번째 자리에 있는 사람의 이름

이름과 점수를 짝으로 묶는다

이름과 점수를 따로따로 두 목록에 담으면 안 됩니다. 점수만 늘어놓는 순간 이름과의 짝이 끊어지기 때문입니다. 둘을 한 덩어리로 묶어 담고, 덩어리째 늘어놓아야 짝이 유지됩니다. 목록 안에 목록을 담는 것입니다.

담긴 모양	늘어놓기 전	점수가 높은 순으로 늘어놓은 뒤
인덱스 0	학생-A, 98	학생-E, 100
인덱스 1	학생-B, 95	학생-A, 98
인덱스 2	학생-C, 92	학생-B, 95 ← 3등
인덱스 3	학생-D, 88	학생-C, 92
인덱스 4	학생-E, 100	학생-D, 88

인덱스 0이 1등이므로 3등은 인덱스 2입니다. 사람이 세는 순서(1부터)와 인덱스(0부터)가 한 칸 어긋나 있습니다.

무엇을 기준으로 늘어놓나

덩어리에는 이름과 점수 둘이 들어 있습니다. 그냥 늘어놓으라고 하면 앞에 있는 이름을 기준으로 가나다순이 되어 버립니다. 그러니 「점수를 보고 늘어놓아라」고 따로 알려 주어야 합니다. 방향도 말해 주어야 합니다. 그냥 두면 작은 것부터 갑니다.

푸는 순서

사람 수를 입력받는다.
빈 목록을 하나 마련한다.
사람 수만큼 반복하며 이름과 점수를 받아 짝으로 묶어 담는다.
목록을 점수 기준, 큰 것부터 늘어놓는다.
인덱스 2에 있는 덩어리에서 이름만 꺼내 내놓는다.

스스로 확인

설계 4번에서 「점수 기준」을 빼먹으면 어떤 순서로 늘어설까요? 그리고 그때 인덱스 2에는 누가 오게 될까요?

3단계 · 파이썬으로 옮기기

정렬에 기준을 알려 주는 방법이 있습니다.

먼저 스스로 적어 본 뒤에 코드를 보세요. 설계 다섯 줄이 코드에서도 다섯 줄쯤입니다. 설계에서 말한 목록은 파이썬의 리스트([ ])이고, 목록 안의 목록은 리스트 안에 리스트를 담은 것입니다.

3등.기본.py

# 사람 수를 먼저 받고, 그다음 줄부터 이름과 점수를 받는다
n = int(input())

students = []
for _ in range(n):
    name, score = input().split()
    students.append([name, int(score)])

# 점수를 기준으로 큰 것부터 늘어놓는다
students.sort(key=lambda s: s[1], reverse=True)

# 인덱스 0이 1등이므로 3등은 인덱스 2다
print(students[2][0])

기준을 알려 주는 자리

늘어놓을 때 「덩어리를 받으면 그중 인덱스 1을 보라」고 알려 주고 있습니다. sort의 key=에는 덩어리 하나를 받아 비교할 값을 돌려주는 함수를 넘깁니다. lambda s: s[1]은 「s를 받아 s[1]을 돌려준다」는 뜻으로, lambda 매개변수: 식 꼴로 그 자리에서 만들어 쓰는 이름 없는 함수(lambda)입니다. 방향은 reverse=True로 따로 켜 주어야 큰 것부터 갑니다.

점수를 수로 바꾸는 이유

입력받은 점수는 글자입니다. 수로 바꾸지 않고 늘어놓으면 글자 순서로 늘어섭니다. 그러면 「9」가 「100」보다 크다고 판정됩니다. 문법 검사도 통과하고 답도 나오는데 순서만 틀린 논리 오류(멈추지 않고 틀린 답을 내는 오류)입니다.

스스로 확인

점수를 글자인 채로 늘어놓으면 100, 98, 95, 92, 88은 어떤 순서가 될까요? 사전에서 낱말을 찾듯 앞 글자부터 비교한다고 생각해 보세요.

4단계 · 넣어 보고 확인하기

정렬이 맞는지 보려면 순서를 흐트러뜨려 넣어야 합니다.

이미 높은 순으로 입력하면 정렬이 빠져 있어도 답이 맞습니다. 그러니 일부러 뒤섞어 넣어야 합니다.

넣은 값 (점수만 적음)	나와야 할 결과	무엇을 보려는 값인가
98, 95, 92, 88, 100	95인 사람	1등이 맨 끝에 있는 경우
100, 98, 95	95인 사람	딱 세 명 — 마지막이 3등
88, 92, 95, 98, 100	95인 사람	낮은 순으로 들어온 경우
100, 100, 95, 90	95인 사람	같은 점수가 있는 경우 — 요구 사항 4번
100, 95, 95, 90	95인 사람 중 하나	3등 자리가 동점인 경우

결과가 어긋났다면 여기부터 봅니다

가장 낮은 점수 쪽이 나온다 — 방향을 거꾸로 켜지 않았습니다
이름 가나다순처럼 보인다 — 기준을 알려 주지 않았습니다
2등이나 4등이 나온다 — 인덱스가 2가 맞는지 봅니다
이름 대신 점수가 나온다 — 덩어리에서 인덱스 0을 꺼내야 합니다
100점이 맨 뒤로 간다 — 점수를 글자인 채로 늘어놓고 있습니다

3등 자리가 동점인 줄은 답이 하나로 정해지지 않습니다

3등 자리가 동점이면 둘 중 누가 나올지는 요구 사항이 말해 주지 않습니다. 이것은 버그가 아니라 정하지 않은 것입니다. 지금 코드는 먼저 입력한 사람을 내놓는데, 파이썬의 정렬이 같은 값끼리는 들어온 순서를 지키기 때문입니다. 요구 사항이 정한 결과가 아니므로 입력 순서가 바뀌면 답도 바뀝니다. 「답이 여러 개일 수 있는 테스트」를 그렇게 적어 두는 것도 정직한 방법입니다. 하나로 정하고 싶다면 1단계로 돌아가 「동점이면 이름이 앞서는 쪽」 같은 규칙을 더해야 합니다.

스스로 확인

테스트 표에서 같은 점수가 있는 경우인 100, 100, 95, 90에서 요구 사항 4번을 「공동 1등 다음은 2등」으로 바꾸면 답이 달라질까요?

더 해 보기

정하지 않고 남겨 둔 것들입니다.

동점일 때를 정한다

점수가 같으면 이름이 앞서는 쪽이 먼저 오게 해 봅니다. 기준을 두 개 알려 주어야 합니다. 점수는 큰 것부터, 이름은 가나다순으로요.

몇 등인지 입력받는다

3등으로 고정한 것을 풀어 봅니다. 사람 수보다 큰 등수를 넣으면 어떻게 할지도 정해야 합니다.

정렬 없이 찾아본다

늘어놓지 않고 세 번 순회해서 3등을 찾아 봅니다. 정렬이 얼마나 편한 도구인지 직접 겪어 보는 과제입니다. 다만 편한 것과 빠른 것은 다릅니다. 사람 수가 아주 많아지면 세 번 순회하는 쪽이 확인하는 횟수가 더 적습니다.

세 명보다 적으면

요구 사항 5번을 풀어 봅니다. 지금 코드는 없는 인덱스를 꺼내려다 실행 오류로 멈춥니다. 꺼내기 전에 사람 수를 확인해 막아야 합니다.

스스로 확인

3등이 아니라 100등을 찾아야 한다면 「정렬 없이 여러 번 순회하기」와 「정렬한 뒤 꺼내기」 중 어느 쪽이 확인하는 횟수가 적을까요? 순회를 몇 번 해야 하는지부터 세어 보세요.