[백준] 9017 크로스 컨트리 (풀지 못했던 이유 + 코드 + 해설)

구현 & 자료구조

https://www.acmicpc.net/problem/9017

9017번: 크로스 컨트리

 

코드

import sys 
input = sys.stdin.readline

t = int(input())

for i in range(t):
	n = int(input())
	team = list(map(int, input().strip().split()))

	manage = {}
	for j in range(n):
		if team[j] not in manage:
			# 팀 명수, 선수들 점수리스트, 점수합계
			manage[team[j]] = [1, [], 0]
		else:
			manage[team[j]][0] += 1

	# 선수들의 수가 조건에 맞지 않는 팀을 우선걸러낸다
	contain = set(k for k, v in manage.items() if v[0] < 6)

	grade = 1
	for j in range(n):
		# 점수계산에서 제외해야 하는 선수가 아니라면
		if team[j] not in contain:
			manage[team[j]][1].append(grade)
			# 점수를 더하는건 상위 4명의 점수까지만 합산
			if len(manage[team[j]][1]) <= 4: 
				manage[team[j]][2] += grade
			grade += 1



	answer = []
	for k, v in manage.items():
		if len(v[1]) != 0 and v[2] != 0:
			answer.append([k, v[1][4], v[2]])

	a = sorted(answer, key = lambda x : (x[2], x[1]))
	print(a[0][0])

 

설명

 문제에서 가장 중요하게 다루어야 하는 부분의 '우선순위'를 두자면 구현의 영역보다는 '자료구조'의 영역을 잘 생각해 내는 것이 중요한 문제인 것 같다. 그 이유를 알아보자. 구현의 문제 조건은 굉장히 간단하다 설명에서 구현해 주면 되는 부분을 전부 명시해주고 있기 때문에 읽고 어렵지 않게 '시도' 할 수 있다. 하지만 이 문제에 핵심은 두가지로 볼 수 있을 것 같다.

 

 

"기준에 맞지 않는 팀은 점수계산에서 제외한다."

"동일한 점수라면 5번째 선수의 점수가 적은 순이 우승팀이 된다."

 

 

 문제 핵심이라고 해도 굉장히 간단해 보인다. 하지만 숨은 함정이 있다. 우선 기준에 맞지 않는 팀은 점수를 계산하지 않는다는 것은 쉽게 계산할 수 있다. 팀의 번호가 주어졌기 때문에 해당 팀의 번호를 카운트해서 그 팀이 6명이 채워지는지 아닌지를 판단해 주면 간단하게 구현이 가능하다. 필자는 위에서 분기문을 통해서 제외하지 않는 번호라면 점수를 부여했다. 이후에 점수의 최솟값을 판단해야 되기 때문에 딕셔너리에서 "카운트되지 않았으면서 and 선수가 없는" 조건을 가진 것들만 answer 리스트에 담아줌으로써 제외할 팀들의 값을 가지고 오지 않았다. 아마 여기서 먼저 딕셔너리에서 지우는 게 더 간단할 수 있다. 왜냐하면 먼저 지우고 나서 정렬만 수행할 수 있게 만들어주면 되기 때문이다. 하지만 위에서는 "조건의 흐름을 파악하기 위해서 해당 조건으로 작성했다." 이렇게 하면 첫 번째 조건은 만족하게 된다.

 

 두번째 조건을 보게 되면 동일한 점수라면 5번째 선수의 점수가 적은 순이 우승하게 된다는 뜻은 곧 "최소의 값을 가진 팀이 2팀 이상 있을 때" 5번째 선수의 점수를 비교해서 적은 순을 택하라는 말이 된다. 이제 이 조건이 왜 중요한지 그리고 위에서 자료구조가 구현보다 왜 우선순위를 두었는지 설명해보고자 한다.

 

 

"sort() 정렬을 정확히 알고, 두 번째 조건을 다시 읽어보자"

 

필자가 처음에 생각했던 건 아래와 같다.

 

'어? 그럼 5번째 선수를 기준으로 작은 순서대로 정렬만 해주면 되는 거 아닌가?

그러면 1팀만 있을때는 어차피 한 팀만 존재하기 때문에 정렬에 영향을 미치지 않을 것이고, 2팀 이상일 때는 최솟값을 가지고 있는 애들 중에서 5번째 선수의 값이 작은 것으로 정렬이 될 테니까 이게 정답이야!'

 

 

a = sorted(answer, key=lambda x : x[1])

or

answer.sort(key=lambda x : x[1])

 자 위에 방법대로 하면 무조건 틀리게 되어있다. 혹시 필자가 생각했던 부분에서 이상한 점을 느꼈다면 문해력이 정말 뛰어나다고 생각한다..

틀린 이유를 이렇게 설명해보고 싶다. '문제의 의도는 맞지만 구현은 틀리다.' 아마 곱씹어 느껴본다면 자료구조를 정확히 이해하지 못하고 있었다고 생각할 수 있다. 왜냐하면 문제의 조건에서는 '두 팀의 점수가 같으면 다섯 번째 선수의 점수가 작은 순으로 우승팀을 결정한다.'라고 되어 있다. 그럼 만약 잘못된 위 코드로 구현하게 되면 어떻게 될까? 최솟값을 가진 한 개의 팀에는 문제가 생기지 않는다. 항상 한 팀만 나오게 되니까 이는 문제에서 "적어도 한 팀은 참가 선수가 여섯" 이기 때문에 한 팀은 무조건 승리자가 나온다. 그럼 2개의 팀 이상이 동일한 값을 가질 때 문제가 생긴다. 왜냐하면 현재 코드에서는 '동일한 최솟값을 가진 팀을 선별하고 있지 않다.' 단순히 점수 계산에서 제외된 팀만을 가지고 올뿐이다. 따라서 "최솟값이 들어있는 값 + 최솟값이 아닌 값"이 공존하고 있는 상황이다. 즉 위 상황에서는 값이 공존해 있는 상황에서 단순 '5번째 선수로만' 정렬하고 있기 때문에 아래를 생각해 보면 반례가 나올 수 있다.

 

 

"점수의 합이 가장 큰 값이 5번째 선수의 값이 가장 작을 수 있고"

"점수의 합이 가장 작은 값이 5번째 선수의 점수가 가장 클 수 있다."

 

 

 위 코드가 잘못되었다는 명백한 증거가 될 수 있다. 즉 문제의 조건 "동일한 점수라면 5번째 선수를 비교한다."라는 조건에 위배된다.

그렇기 때문에 알아야 할 중요한 사실은 '자료구조'를 정확히 알아야 한다는 것이다. 이것은 곧 위 우선수위를 둔 이유를 설명해 준다.

sort()는 정렬 함수이다. 람다와 같이 사용할 경우 '기준'을 중심으로 정렬을 수행한다. 그럼 우리가 수행해야 될 정렬 기준은 무엇일까 생각해 볼 수 있게 된다. 정렬하는 건 알겠는데 우선순위를 무엇으로 두느냐가 sort() 함수가 설명해 준다. 람다 표현식에서 기준을 두 개 이상 설정해 준다면 첫 번째 튜플로 묶인 파라미터를 기준으로 우선 정렬하고 이후 두 번째 파라미터를 기준으로 정렬해 주게 된다. 그럼 이걸 문제에 그대로 대입해 보자.

 

 

sorted(answer, key=lambda : (x [2], [x1))

 

x[2]를 우선 정렬하고 (점수의 합이 가장 작게 오름차순으로 정렬)

이후 x[1] (5번째 선수의 점수가 가장 작은 순서대로 오름차순으로 정렬)

 

 이제 문제가 해결되었다. 점수의 합이 가장 작은 것이 2팀 이상일 때 5번 사람을 기준으로 정렬해서 가장 적은 선수를 포함한 팀이 우승하도록 작성된 것이다. 이것은 곧 1팀만 있을 때는 영향을 받지 않지만 두 팀 이상일 때는 정확히 문제의 조건에 부합한다.

따라서 람다를 사용할 때 정렬이 어떻게 구성되는지 원리를 정확히 이해하고 문제에 대입해서 풀어야 했으며, 문제의 조건을 그대로 구현하는 연습이 아직 부족하다는 근거가 되었다고 생각한다. 이 문제를 가지고 하루 동안 '틀렸습니다.'만 나와서 이 사실을 알고 나서는 구현할 때도 자료구조의 원리를 깊게 생각해 보면서 접근해야 되겠다고 생각이 들었다.