[알고리즘][백준] 9017. 크로스 컨트리

반응형

문제

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

 

해결 아이디어

조건이 은근 까다로운데,

1. 한 팀에 최소 6명. 6명 안되면 탈락
2. 등수가 곧 점수. 팀별 점수 합산이 낮을 수록 유리한 것
3. 동점이면 5번째 주자 점수가 낮은 쪽이 승리

그래서 아래와 같은 방식으로 풀었습니다.

1. 일단 카운팅부터 해서 6명 안되는 팀은 리스트에서 다 빼버렸습니다.
2. 빼버린 리스트를 다시 돌면서 팀별로 카운팅하면서 4명까지만 합산하고, 5번째 선수에 대한 정보는 따로 저장했습니다.
3. 맵 전체를 돌면서 점수를 기준으로 순위를 정하고, 동점이면 5번째 선수 저장한 곳에서 빼서 비교해줬습니다.

 

 

 

N = int(input())
for i in range(N):
    T = int(input())
    allLi = list(map(int, input().split(' ')))
    li = []

    teams = {} # 각 팀의 점수를 저장할 곳
    teamsLastMember = {} # 팀별 5번째 주자의 점수를 저장할 곳
    teamsCount = {} # 몇명인지 셀 곳
    # 참고로 teamsCount에 카운팅하고 list에서 6명 안되는 조 빼주고,
    # 다시 재활용해서 여기서 6명되는 팀들 팀별로 카운팅하는 용도로 사용

    for member in allLi:
        teamsCount[member] = (1 if member not in teamsCount else teamsCount[member] + 1)

    for item in allLi:
        if (teamsCount[item] >= 6):
            li.append(item)

    teamsCount = {}
    for idx, member in enumerate(li):
        index = idx + 1
        if (member not in teams):
            teams[member] = index

        else:
            if (teamsCount[member] < 4):
                teams[member] += index
            else:
                if (member not in teamsLastMember):
                    teamsLastMember[member] = index
        
        teamsCount[member] = 1 if member not in teamsCount else teamsCount[member] + 1
        

    # print(teams)
    # print(teamsLastMember)
    # print(teamsCount)

    mx = list(teams.keys())[0]
    for team in teams:
        if (teams[mx] > teams[team] or 
            (teams[mx] == teams[team] and teamsLastMember[mx] > teamsLastMember[team])):
            mx = team

    
    print(mx)

1 if member not in teamsCount else teamsCount[member] + 1
파이썬에서 삼항 연산자 같은 느낌으로 사용할 수 있습니다.

list(teams.keys()) : 딕셔너리에서 키만 모아서 리스트화
list(teams.values()) : 딕셔너리에서 값만 모아서 리스트화
list(teams.items()) : key, value 모두 사용하려고 할 때 사용