[백준(Baekjoon)] 2535 아시아 정보올림피아드

문제

최근 아시아 지역의 학생들만 참여하는 정보 올림피아드 대회가 만들어졌다. 이 대회는 온라인으로 치러지기 때문에 각 나라에서 이 대회에 참여하는 학생 수의 제한은 없다. 

참여한 학생들의 성적 순서대로 세 명에게만 금, 은, 동메달을 수여한다. 단, 동점자는 없다고 가정한다. 그리고 나라별 메달 수는 최대 두 개다.

예를 들어, 대회 결과가 다음의 표와 같이 주어졌다고 하자.

 

참가국	학생번호	점수
1	1	230
1	2	210
1	3	205
2	1	100
2	2	150
3	1	175
3	2	190
3	3	180
3	4	195

 

이 경우, 금메달 수상자는 1번 국가의 1번 학생이고, 은메달 수상자는 1번 국가의 2번 학생이며, 동메달 수상자는 3번 국가의 4번 학생이다. (1번 국가의 3번 학생의 성적이 동메달 수여자보다 높지만, 나라 별 메달 수가 두 개 이하 이므로 1번 국가 3번 학생은 동메달을 받을 수 없다.)

대회 결과가 입력으로 주어질 때, 메달 수상자를 결정하여 출력하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에는 대회 참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사이에 두고 주어진다. 단, 국가 번호는 1부터 순서대로 하나의 정수로 주어지며, 각 학생 번호는 각 나라별로 1부터 순서대로 하나의 정수로 주어진다, 점수는 0 이상 1000 이하의 정수이고, 동점자는 없다고 가정한다. 입력으로 제공되는 국가는 적어도 두 나라 이상이다.

 

출력

메달을 받는 학생들을 금, 은, 동메달 순서대로 한 줄에 한 명씩 출력한다. 즉, 첫 번째 줄에는 금메달 수상자를, 두 번째 줄에는 은메달 수상자를, 세 번째 줄에는 동메달 수상자를 출력한다. 하나의 줄에는 소속 국가 번호와 학생 번호를 하나의 빈칸을 사이에 두고 출력한다. 

 

예제 입력 1

9

1 1 230

1 2 210

1 3 205

2 1 100

2 2 150

3 1 175

3 2 190

3 3 180

3 4 195

 

예제 출력 1

1 1

1 2

3 4

 

 

---

나의 풀이

[python(파이썬)]

 

풀이 1 - 금, 은 구하고 동만 따로 구현한 경우

student_num = int(input())	# 대회 참가 학생 수
info, point, n_check, now_n = [], [], [0], 0

for i in range(student_num):
    a, b, c = map(int, input().split())
    info.append([a, b])	# a = 참가 학생 [소속 국가 번호, 학생 번호]
    point.append(c)	# 점수
    if a != now_n:	# 소속 국가 번호 저장
   	n_check.append(0)

for _ in range(2):
    s_index = point.index(max(point))
    print(f'{info[s_index][0]} {info[s_index][1]}')
    n_check[info[s_index][0]] += 1
    point[s_index] = 0

while tf:
    s_index = point.index(max(point))
    point[s_index] = 0
    if n_check[info[s_index][0]] == 2:
        tf = True
    else:
        print(f'{info[s_index][0]} {info[s_index][1]}')
        break

 

풀이 2 - 금, 은, 동을 하나의 while에서 함께 구현한 경우

student_num = int(input())	# 대회 참가 학생 수
info, point, n_check, now_n = [], [], [0], 0

for i in range(student_num):
    a, b, c = map(int, input().split())
    info.append([a, b])	# a = 참가 학생 [소속 국가 번호, 학생 번호]
    point.append(c)	# 점수
    if a != now_n:	# 소속 국가 번호 저장
   	n_check.append(0)

while True:
    s_index = point.index(max(point))	# 현재 최대값을 가진 수상자의 인덱스 저장
    if n_check[info[s_index][0]] != 2:	# 한 국가에서 수상자가 두 명 이상이 아닌 경우
        print(f'{info[s_index][0]} {info[s_index][1]}')	# 수상자 출력
        if sum(n_check) != 2:	# 금, 은 메달수상자 인 경우 -> 다음 수상자 구하기 위해 준비
            n_check[info[s_index][0]] += 1	# 해당 국가의 수상자 수 1 증가
        else:	# 동메달 수상자 -> 다음 수상자 없으므로 중지
            break # while문 stop
    point[s_index] = 0	# 다음 최대값을 구하기 위해 0으로 변경

 

풀이 3 - 코드 길이는 짧아지고 시간은 조금 늘어난 코드

student_num = int(input())
info = [[*map(int, input().split())] for _ in range(student_num)]
info = sorted(info, key=lambda x: (-x[2]))  # 인덱스 2번 기준으로 내림차순
n_check = []    # 국가별 수상자 체크 리스트

for i in range(len(info)):
    if n_check.count(info[i][0]) != 2:	# 현재 수상 후보자 국가에서 2명 이상이 나오지 않은 경우
        print(f'{info[i][0]} {info[i][1]}')	# 수상자의 국가, 학생 번호 출력
        n_check.append(info[i][0])	# 수상자의 국가 번호를 국가별 수상자 체크 리스트에 append
    if len(n_check) == 3:	# 전체 수상자가 3명인지 검사
        break

 

---

풀이 과정

1. 입력받기
2. 금메달, 은메달 수상자 -> 풀이 1
3. 동메달 수상자 -> 풀이 1
4. 금, 은, 동을 하나의 while에서 함께 구현한 경우 (앞의 2, 3번을 합쳐서 구현) -> 풀이 2
5.  코드 길이는 짧아지고 시간은 조금 늘어난 코드 -> 풀이 3

 

1. 입력 받기

 

student_num = int(input())	# 대회 참가 학생 수
info, point, n_check, now_n = [], [], [0], 0

for i in range(student_num):
    a, b, c = map(int, input().split())
    info.append([a, b])	# a = 참가 학생 [소속 국가 번호, 학생 번호]
    point.append(c)	# 점수
    if a != now_n:	# 소속 국가 번호 저장
   	n_check.append(0)

 

1) 대회 참가 학생 수를 입력받는다. 

2) 대회 참가 학생 수만큼 for문을 돌려 학생의 정보를 입력받는다. 

3) info 리스트에 참가 학생의 [소속 국가 번호, 학생 번호]를 저장

4) point 리스트에 참가 학생의 점수를 저장

5) n_check에 참가 국가를 저장한다. 

5) 추가 설명
n_check = [0] 초기화 -> n_check = [0]은 참가 국가가 없음을 의미
now_n = 0 초기화 -> 현재 0번 국가 학생이 입력되고 있음을 의미 ( 0번 국가는 없으므로 초기화 )
ex) n_check = [0, 0, 0]라면 인덱스 0, 1, 2에 값이 있으므로 1, 2번에서 참가한 학생이 있다는 의미

ex)
1 1 230
1 2 210
2 1 205를 입력받는다고 가정할 때 

5-1) 1 1 230 입력 -> n_check = [0]인 상황
if a != now_n: -> now_n = 0, a = 1 -> 다르므로 아래 실행
     n_check.append(0) -> 1번 국가 추가(인덱스 1 = 1번 국가라는 의미) -> n_check = [0, 0]

5-2) 1 2 210 입력 -> n_check = [0, 0]인 상황 -> 국가 1번에서 온 학생이 있음 의미
if a != now_n : -> now_n =  1, a = 1 -> 같으므로 아래 실행 x
     n_check.append(0)

5-3) 2 1 205 입력 -> n_check = [0, 0]인 상황 -> 국가 1번에서 온 학생이 있음 의미
if a != now_n : ->  now_n = 1, a = 2-> 다르므로 아래 실행
     n_check.append(0) -> 2번 국가 추가(인덱스 2 = 2번 국가라는 의미)
-> n_check = [0, 0, 0]  -> 국가 1번, 2번에서 온 학생이 있음 의미

 

 

2. 금메달, 은메달 수상자 -> 풀이 1

 

나라 별 메달 수가 2개 이하 이므로 금메달, 은메달 수상자의 국가는 상관하지 않아도 된다. 

for _ in range(2):
    s_index = point.index(max(point))
    print(f'{info[s_index][0]} {info[s_index][1]}')
    n_check[info[s_index][0]] += 1
    point[s_index] = 0

 

1) for문 2번 반복 (금, 은)

2) point 리스트에서 가장 큰 값을 가진 인덱스를 s_index에 저장 

3) info에서 해당 인덱스 값을 출력 -> 점수가 가장 큰 학생의 국가와 학생 번호 출력

4) n_check[info[s_index][0]] += 1 -> 해당 나라 획득 메달 수 증가

ex) n_check = [0, 0, 0] 일 때
1 1 230이 금메달이라면 [0, 1, 0] 1번 국가에서 1명 수상(n_check[1] = 1)
1 1 210이 은메달이라면 [0, 2, 0] 1번 국가에서 2명 수상(n_check[1] = 2)

5) point[s_index] = 0 -> 다음 최댓값을 구하기 위해 현재 최댓값을 0으로 변경

 

 

3. 동메달 수상자  -> 풀이 1

 

동메달 수상자는 금메달, 은메달 수상자의 국가 수에 영향을 미친다. (나라 별 메달 수가 2개 이하)

 

while tf:
    s_index = point.index(max(point))
    point[s_index] = 0
    if n_check[info[s_index][0]] == 2:
        tf = True
    else:
        print(f'{info[s_index][0]} {info[s_index][1]}')
        break

1) tf가 True이면 계속 반복한다. -> 해당 국가에서 수상자가 2명 이상 나왔다는 의미

2) point 리스트에서 가장 큰 값을 가진 인덱스를 s_index에 저장 

3) point[s_index] = 0 -> 다음 최댓값을 구하기 위해 현재 최댓값을 0으로 변경

4) 3번째 최댓값인 학생의 국가에서 수상자가 2명 이상 나왔다면 다시 2번으로 돌아감

ex) n_check = [0, 0, 0] 일 때
1 1 230이 금메달이라면 [0, 1, 0] 1번 국가에서 1명 수상(n_check[1] = 1)
1 1 210이 은메달이라면 [0, 2, 0] 1번 국가에서 2명 수상(n_check[1] = 2)
1 3 205 이 그다음 점수가 높더라도 n_check[1] = 2이므로 수상할 수 없음
다음 점수가 높은 3 4 195 학생이 동메달을 획득하게 된다. 

5) 3번째 최댓값인 학생의 국가에서 수상자가 2명 이상 나오지 않은 경우에 해당 학생의 국가 번호와 학생 번호 출력 후 종료

 

 

4. 금, 은, 동을 하나의 while에서 함께 구현한 경우 (앞의 2, 3번을 합쳐서 구현)  -> 풀이 2

 

while True:
    s_index = point.index(max(point))	# 현재 최대값을 가진 수상자의 인덱스 저장
    if n_check[info[s_index][0]] != 2:	# 한 국가에서 수상자가 두 명 이상이 아닌 경우
        print(f'{info[s_index][0]} {info[s_index][1]}')	# 수상자 출력
        if sum(n_check) != 2:	# 금, 은 메달수상자 인 경우 -> 다음 수상자 구하기 위해 준비
            n_check[info[s_index][0]] += 1	# 해당 국가의 수상자 수 1 증가
        else:	# 동메달 수상자 -> 다음 수상자 없으므로 중지
            break # while문 stop
    point[s_index] = 0	# 다음 최대값을 구하기 위해 0으로 변경

 

 

5.  코드 길이는 짧아지고 시간은 조금 늘어난 코드  -> 풀이 3

 

입력부터 다르게 코딩해서 구현해보았다. 

student_num = int(input())
info = [[*map(int, input().split())] for _ in range(student_num)]
info = sorted(info, key=lambda x: (-x[2]))  # 인덱스 2번 기준으로 내림차순
n_check = []    # 국가별 수상자 체크 리스트

for i in range(len(info)):
    if n_check.count(info[i][0]) != 2:	# 현재 수상 후보자 국가에서 2명 이상이 나오지 않은 경우
        print(f'{info[i][0]} {info[i][1]}')	# 수상자의 국가, 학생 번호 출력
        n_check.append(info[i][0])	# 수상자의 국가 번호를 국가별 수상자 체크 리스트에 append
    if len(n_check) == 3:	# 전체 수상자가 3명인지 검사
        break

1) 학생 수를 입력 받는다. 

2) 대회 참가자의 정보를 입력 받은 후 인덱스 2번(점수)를 기준으로 내림차순 정렬
3) for문을 돌린다. 

4) if n_check.count(info[i][0]) != 2 -> 현재 수상 후보자 국가에서 2명 이상이 나오지 않은 경우 5번을 실행

5) 수상자의 국가와 학생번호 출력

6) 수상자의 국가 번호를 국가별 수상자 체크 리스트에 추가 -> 한 국가에서 2명 이상 나오는지 체크하기 위함

7) len(n_check) == 3 -> 전체 수상자가 3명인지 검사 -> 메달은 3개

 

---

※ 백준에서 정답을 제출했을 때 맞았다고 나오지만 틀린 코드!!

 

student_num = int(input())
info, point, n_check, now_n = [], [], [0], 0

for i in range(student_num):
    a, b, c = map(int, input().split())
    info.append([a, b])
    point.append(c)
    if a != now_n:
        n_check.append(0)

for _ in range(2):
    s_index = point.index(max(point))
    print(f'{info[s_index][0]} {info[s_index][1]}')
    n_check[info[s_index][0]] += 1
    point[s_index] = 0

s_index = point.index(max(point))
point[s_index] = 0
if n_check[info[s_index][0]] == 2:
    s_index = point.index(max(point))
    print(f'{info[s_index][0]} {info[s_index][1]}')
else:
    print(f'{info[s_index][0]} {info[s_index][1]}')

 

예제가 아래와 같을 때

9
1 1 230 -> 금메달 수상자
1 2 210 -> 은메달 수상자
1 3 205 -> 동메달 수상해야 하지만 앞서 1번 국가에서 2명 수상자가 나왔으므로 패스
1 3 200 -> 동메달 수상자 (동메달 수상자가 아니 여야 하는데 동메달 수상자로 나옴)
2 1 100
2 2 150
3 1 175
3 2 190
3 3 180
3 4 195 -> 동메달 수상자

 

s_index = point.index(max(point))
point[s_index] = 0
if n_check[info[s_index][0]] == 2:
    s_index = point.index(max(point))
    print(f'{info[s_index][0]} {info[s_index][1]}')
else:
    print(f'{info[s_index][0]} {info[s_index][1]}')

동메달을 수상하는 부분에서 while을 하지 않고 그냥 if문만 실행하기 때문에 세 번째 최댓값 학생이 금, 은 수상자와 국가가 같을 때만 패스가 되고 네 번째 최댓값 학생인 1 3 바로 출력된다. 

하지만 네 번째 최댓값 학생도 1번 국가이므로 패스가 맞는 것!! -> while문을 사용해야 한다. 

-> 이 경우 백준에서 정답 제출했을 때 틀렸다고 나와야 하는데 맞다고 떴다. (테스트 케이스가 추가돼야 할 듯)

---

 

문제 출처

2535번: 아시아 정보올림피아드