[백준] 토너먼트 만들기 : 2262번 - Python

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

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)