https://www.acmicpc.net/problem/2262
문제를 풀면서 몰랐던 개념
[Python] 리스트에서 값의 위치를 찾아주는 함수 index()
: index함수는 특정 값의 위치를 반환해주고, 만약 중복된 값이 있으면 가장 최소의 위치를 리턴해준다.
my_list = [1,2,3,4,5,6,7]
print(my_list.index(3))
>>> 2
문제의 접근 방법
- 랭킹이 낮은(숫자가 더 큰) 선수는 어차피 우승을 할 수 없기 때문에 먼저 떨어뜨려야 한다.
- 랭킹이 낮은(숫자가 더 큰) 선수부터 양쪽 선수들 중 랭킹의 차이가 더 적은 선수랑 짝꿍을 시켜야 한다. 최솟값을 위해!
ex)
1 6 2 5 3 4 >>> (6-2 = 4)
1 2 5 3 4 >>> (5-3 = 2)
1 2 3 4 >>> (4-3 = 1)
1 2 3 >>> (3-2 = 1)
1 2 >>> (2-1 = 1)
최솟값: 4+2+1+1+1 = 9
내가 막혔던 부분
- 각 선수들의 양쪽 선수들과의 랭킹 차이가 더 적은 선수랑 짝을 지어 경기를 진행해야 한다는 것까지는 생각했는데 무슨 기준으로 비교할 순서를 선택해야 할지에 대해 아이디어를 떠올리지 못했다.
문제 풀이 방법
(1) 선수 n명을 입력받고 각 선수들의 랭킹을 입력받아 리스트 형태로 rank에 저장하기
(2) 랭킹이 가장 낮은 선수(가장 큰 숫자)를 찾아서 변수 target에 저장하기
(3) 리스트 rank 안에서 target의 인덱스 위치를 찾기 위해 index함수를 사용해서 idx에 저장하기
(4) (2)~(3)에서 구한 값들을 통해 랭킹이 가장 낮은 선수(target)가 맨 앞에 있는지, 맨 뒤에 위치하고 있는지, 중간에 위치하고 있는지를 판별해 그에 맞게 차이를 계산하기
그 값을 변수 hap에 누적해서 더해주기
- 맨 앞에 있는 선수가 랭킹이 제일 낮을 때: 오른쪽에 있는 선수(그 다음 인덱스)의 랭킹과의 차를 계산
- 맨 뒤에 있는 선수가 랭킹이 제일 낮을 때: 왼쪽에 있는 선수(그 전 인덱스)의 랭킹과의 차를 계산
- 중간에 있는 선수가 랭킹이 제일 낮을 때: 양쪽에 있는 선수들의 랭킹과의 차를 계산해서 더 작은 값을 추출
(5) 가장 랭킹이 낮았던 선수는 토너먼트에서 탈락이므로(우승 불가능) 해당 인덱스 idx를 리스트 rank에서 제거해주기
(6) (2)~(5)의 과정을 반복해서 더해진 값 hap을 출력해주기!
소스코드
n = int(input())
rank = list(map(int, input().split()))
hap = 0
for _ in range(len(rank)-1):
target = max(rank) # 가장 랭킹이 낮은 선수(숫자가 제일 큰 선수)
idx = rank.index(target) # 그 선수의 인덱스 위치
if idx == 0: # 맨 앞에 있는 선수가 랭킹이 제일 낮을 때
hap += rank[idx] - rank[idx+1]
elif idx == len(rank)-1: # 맨 뒤에 있는 선수가 랭킹이 제일 낮을 때
hap += rank[idx] - rank[idx-1]
else: # 양 쪽 선수들과 모두 비교를 해봐야 할 때
hap += min(rank[idx]-rank[idx+1], rank[idx]-rank[idx-1])
del rank[idx] # 탈락한 선수는 리스트에서 제거해주기
print(hap)
'백준 write-up > 정렬 & 그리디' 카테고리의 다른 글
[백준] 욱제는 도박쟁이야!! : 14655번 - Python (0) | 2021.08.26 |
---|---|
[백준] 동전 뒤집기 : 1285번 - Python (0) | 2021.08.25 |
[백준] 슬라임 합치기 : 14241번 - Python (0) | 2021.08.21 |
[백준] ZOAC 2 : 18238번 - Python (0) | 2021.08.20 |
[백준] 라디오 : 3135번 - Python (0) | 2021.08.18 |