[백준 3758 / Python / 실버2] KCPC

문제

 

구현, 정렬 문제이다. 입력값이 다양하게 주어져서 헷갈리고, 관리해야 하는 데이터가 많아 헷갈린다.

그러나 정렬 조건만 제대로 숙지한다면 크게 어렵지 않게 풀 수 있는 문제이다.

 

import sys

input = sys.stdin.readline

"""

k개의 문제를 풀면 0점 ~ 100점 획득함 -> 팀ID/문제번호/점수 저장

한 문제를 여러 번 제출하면, 최고점수가 최종점수 -> 제출안하면 0점

팀의 점수는 각 문제 최종 점수의 합

점수가 동일한 팀이 있을 경우

1. 점수가 같으면, 제출 횟수가 적은 팀이 이긴다

2. 점수와 제출 횟수가 같으면, 마지막 제출 시간이 빠른 팀이 이긴다

정렬 조건: 점수 높은순, 제출횟수 적은순, 제출시간 빠른순

"""

for _ in range(int(input())):

    """

    n: 팀 개수 (3 <= n)

    k: 문제 개수 (k <= 100)

    team: 나의 팀 (1 <= t <= n)

    m: 로그 개수 (3 <= m <= 10000)

    """

    n, k, my_team, m = map(int, input().split())

    # 각 팀 점수 계산용 리스트

    # [[문제1점수, 문제2점수, ... 크기는 k + 1] 이걸 n + 1개수만큼 팀별로 할당]

    team_and_score = [[0] * (k + 1) for _ in range(n + 1)]  # 1 based

    # 최종 정렬용 리스트 -> 팀별 총합점수, 제출횟수, 마지막 제출시간

    score_count_time = [[0, 0, int(1e9)] for _ in range(n + 1)]  # 1 based

    """로그 입력받기"""

    for submit in range(m):

        """

        cur_team: 팀 id

        num: 문제 번호

        score: 획득한 점수

        """

        cur_team, num, score = map(int, input().split())

        # 각 문제는 더 높은 점수로 갱신

        team_and_score[cur_team][num] = max(team_and_score[cur_team][num], score)

        # 제출횟수 더하기

        score_count_time[cur_team][1] += 1

        # 마지막 제출시간 갱신

        score_count_time[cur_team][2] = submit

   

    """계산된 팀별 점수를 정렬용 리스트에 할당"""

    for team in range(1, n + 1):

        score_count_time[team][0] = sum(team_and_score[team])

        score_count_time[team].append(team)  # 정렬되면 인덱스로 구분되던 팀이 섞이니, 팀 번호를 리스트에 추가해준다

   

    """

    문제 조건대로 정렬

    점수 높은순, 제출횟수 적은순, 제출시간 빠른순

    """

    score_count_time.sort(key = lambda x: (-x[0], x[1], x[2]))

    for rank in range(len(score_count_time) - 1):

        # 우리 팀 랭킹 출력

        # 정렬되면서 패딩 요소는 맨뒤로 밀려남. 따라서 0번인덱스부터 검사

        # 순위는 1부터 시작이니, 인덱스 + 1 출력

        if score_count_time[rank][-1] == my_team:

            print(rank + 1)

            break

 

우선 중요한 리스트가 2개 있다.

team_and_score: 팀별 최종 점수를 계산하기 위한 리스트

score_count_time: 팀별 최종점수, 제출횟수, 제출시간을 저장하고 정렬하기 위한 리스트

 

우선 로그를 입력받는 동시에, team_and_score 리스트를 이용해 각 팀의 각 문제에 대한 점수를 max함수를 이용해 지속적으로 갱신한다.

score_count_time 리스트에는 제출횟수와 제출시간을 실시간으로 업데이트 한다.

 

모든 로그를 입력받았다면, team_and_score에 저장된 팀별 점수를 sum()으로 더해서 score_count_time 리스트에 넣어준다. 그러면 문제 정렬 조건인 점수 높은순, 제출횟수 적은순, 제출시간 빠른순에 해당하는 3가지 요소가 하나의 리스트에 전부 들어가게 된다. 단, 여기서 각 요소마다 팀번호를 추가해줘서 정렬 후에도 팀 번호를 잃어버리지 않게 된다. (그냥 정렬하면 순위대로 정렬되지만, 팀 번호는 잃어버린다)

 

마지막으로 lambda를 활용해서 정렬한 후, 입력받은 team에 대한 순위를 출력해주면 끝.

 

결과

 

다른 사람들 풀이도 몇개 봤는데 나름 잘 푼 편에 속한 것 같다. 시간은 거의 제일 빠른 편인 듯.

 

다만 한가지 최적화할 게 있다면, 팀 번호와 순위를 매핑하는 딕셔너리를 이용해볼까? 였는데,

어차피 각 테스트 케이스마다 순위는 단 한번 출력하고, 다음 테스트 케이스에서는 새로운 순위를 갱신하기 때문에,

팀 번호와 순위를 매핑하는 딕셔너리를 만들어 둔다 해도 단 한번 활용될 뿐이라 굳이 할 필요 없다고 생각했다.