[백준] 3665 - 최종 순위 (G1)

2026. 11. 22. 10:02·알고리즘 (PS)/BOJ
반응형

https://acmicpc.net/problem/3665

 

3665번: 최종 순위

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에

acmicpc.net

 

백준이 다시 돌아온 기념으로 오랜만에 한 문제를 풀어봤다.

단계 별로 풀어보기에서 위상 정렬 파트에 하나 안 풀린 문제가 있길래, 이 문제로 선정

 

문제를 이해하는데 시간이 좀 걸렸으나.. 풀이는 쉽게 나왔다.

 

(스포주의)

근데 개인적으로 마음에 안드는 건, 정답으로 나올 수 없는 케이스를 출력 형식 중 하나로 명시한 게 마음에 안든다.

'아 이 케이스는 절대 나올 수 없는 케이스니 무시해도 되겠군' 이라는 확신을 가져야 하는 것까지가 이 문제의 의도 난이도라면 어쩔 수 없긴한데.. 내 취향은 아니다..

 

이 문제에서는 '?' 출력을 하는 케이스가 나올 수 없다.

- "하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다."

- "만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다."

 

'확실한 순위를 찾을 수 없다' 와 '데이터에 일관성이 없어서 순위를 정할 수 없다' 의 차이를 아시나요?

"데이터에 일관성" 이란 뭘까요?

문제 입력 규칙에 맞지 않는 데이터가 들어온다는 걸까요?

 

근데 그냥 번역이 이상한 거 같기도.

원문을 보면 "등수를 특정할 수 없으면 해당 위치에는 정수 대신 ? 를 출력하라" 고 구체적으로 명시하고 있는데, 번역에서는 밑도 끝도없이 "?" 를 출력하라고 되어있어서, 처음엔 그냥 "?" 이거 하나만 출력하라는 건가? 싶기도 했다.

정수 대신 ? 를 출력하는 케이스면 또 이해가 된다. 위상 정렬에서는 충분히 가능한 케이스니까.

 

암튼 결론은 ? 를 출력하는 케이스는 나올 수 없다.

문제 조건에서 "순위가 뒤바뀐 모든 팀의 정보를 준다" 라고 하였기 때문에, 바꿔말하면 (설사 심사위원이 실수를 해서 정보를 주지 않았다고 하더라도) 정보가 주어지지 않은 팀은 기존의 상대 순위가 유지된다는 것을 뜻하며, 이로 인해 임의의 두 팀 사이의 상대 우위는 반드시 존재하기에 데이터에 모순은 없지만 순위를 특정할 수 없는 케이스는 존재할 수 없다.

반듯시 모순이 없이 특정이 되거나, 모순이 있어서 특정할 수 없거나, 둘 중 하나 뿐인 것이다.

 

이 특성을 활용하면 생각보다 이 문제를 푸는 것은 어렵지 않다.

임의의 두 팀 사이의 상대 우위가 반드시 존재한다 =  중복 순위가 존재할 수 없다.

따라서 위상 정렬 결과 중복 순위가 존재하는 순간 모순인 것이고, 중복 순위가 없으면 순위 대로 정렬해서 출력하면 된다.

 

그렇다면 '순위' 는 어떻게 정의해야 할까

나는 map 으로 모든 임의 두 팀 사이의 상대 우위 정보를 저장해서, "나보다 위 랭크에 있는 팀의 개수" 를 저장했다.

 

1등 팀이면 0

2등 팀이면 1

3등 팀이면 2

4등 팀이면 3

...

 

이런 식이다.

중복순위는 존재할 수 없기 때문에 "나보다 위 랭크에 있는 팀의 개수" 는 항상 유일하다.

그리고 "순위 = 나보다 위 랭크에 있는 팀의 개수가 적은 순" 이라고 정의했다.

 

신규 순위를 측정할 때는 이 관계를 바꾸어 주었다.

예를 들어, 1번 팀과 2번 팀의 상대 순위가 바뀌었는데

 

1번 팀은 2

2번 팀은 3

 

이라면, 다른 팀은 상대 순위가 여전히 고정되고 이 두 팀만 순위가 바뀌었기 때문에

 

1번 팀은 나보다 위에 있는 팀이 하나 늘었으니 2 -> 3

2번 팀은 나보다 위에 있는 팀이 하나 줄었으니 3 -> 2

 

이렇게 바뀐다.

 

이 작업을 순위가 바뀐 모든 팀에 대해 적용해주고, 

기존 "순위" 이 정의에 맞춰 이 값을 기준으로 신규 순위를 정렬만 해주면 최종 순위가 나온다.

만약 중복 값이 존재한다면 순위를 가를 수 없으니 모순이 존재하는 케이스다.

 

 

정답 코드

import sys
input = sys.stdin.readline

t = int(input())
for i in range(t):
    team_to_ranking = dict()
    new_team_to_ranking = dict()
    team_count = int(input())
    team_rankings = list(map(int, input().split()))
    for (idx, team) in enumerate(team_rankings):
        team_to_ranking[team] = idx
        new_team_to_ranking[team] = idx

    change_count = int(input())
    for _ in range(change_count):
        team1, team2 = map(int, input().split())
        if team_to_ranking[team1] > team_to_ranking[team2]:
            new_team_to_ranking[team1] -= 1
            new_team_to_ranking[team2] += 1
        else:
            new_team_to_ranking[team1] += 1
            new_team_to_ranking[team2] -= 1

    if len(set(new_team_to_ranking.values())) < team_count:
        print("IMPOSSIBLE")
    else:
        new_rankings = sorted(new_team_to_ranking, key=lambda k: new_team_to_ranking[k])
        print(*new_rankings)

 

한 가지 주의할 점은, 순위 뒤바꾸기를 할 때는 "작년 기준" 으로 측정해야 하므로, 신규 측정 중인 "new_team_to_ranking" 딕셔너리 정보가 아닌 "team_to_ranking" 딕셔너리 정보를 기준으로 순위를 측정해서 어떻게 바꿀지 판단해야 한다.

 

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 (PS) > BOJ' 카테고리의 다른 글

[백준] 14868 - 문명 (P4)  (0) 2025.04.24
[백준] 1876 - 튕기는 볼링공  (0) 2025.03.29
[백준] 1248 - Guess (G3)  (0) 2025.03.20
[백준] 1166 - 선물  (0) 2024.11.13
[백준] 4315 - 나무 위의 구슬 (Python)  (0) 2024.11.12
'알고리즘 (PS)/BOJ' 카테고리의 다른 글
  • [백준] 14868 - 문명 (P4)
  • [백준] 1876 - 튕기는 볼링공
  • [백준] 1248 - Guess (G3)
  • [백준] 1166 - 선물
에버듀
에버듀
개발은 좋은데 뭘로 개발할까
  • 에버듀
    Blog. 에버듀
    에버듀
  • 전체
    오늘
    어제
    • 분류 전체보기 (624) N
      • 자기계발 (51)
        • 회고 & 생각 정리 (29)
        • 대외활동 (11)
        • 동아리 (7)
        • 자격증 (3)
        • 머니 스터디 (1)
      • CS (335)
        • 자료구조 (19)
        • 어셈블리 (41)
        • 멀티미디어응용수학 (7)
        • 컴퓨터 구조 (29)
        • 알고리즘 분석 (4)
        • 컴퓨터 네트워크 (38)
        • 프로그래밍언어론 (15)
        • HCI 윈도우즈프로그래밍 (26)
        • 기초데이터베이스 (29)
        • 운영체제 (23)
        • 오토마타 (24)
        • 문제해결기법 (11)
        • 블록체인 (22)
        • 소프트웨어공학 (21)
        • 기계학습심화 (12)
        • 컴퓨터그래픽스와 메타버스 (8)
        • 분산시스템특론 (6)
      • 개인 프로젝트 (43)
        • 토이 프로젝트 (3)
        • [2020] 카카오톡 봇 (9)
        • [2021] 코드악보 공유APP (22)
        • [2022] 유튜브 뮤직 클론코딩 (9)
        • [2025] 한글 SQL 데이터베이스 (0)
      • 팀 프로젝트 (24)
        • [2020] 인공지능 숫자야구 (4)
        • [2022] OSAM 온라인 해커톤 (10)
        • [2024] GDSC 프로젝트 트랙 (6)
        • [2025] 큰소리 웹 페이지 (4)
      • 알고리즘 (PS) (108) N
        • BOJ (102) N
        • Programmers (5)
        • 알고리즘 이모저모 (1)
      • Infra (12)
        • AWS (1)
        • Oracle Cloud (8)
        • Firebase (2)
        • Network (1)
      • WEB(BE) (8)
        • express.js (1)
        • Spring & Spring Boot (7)
      • WEB(FE) (2)
        • html, css, js (1)
        • React.js (1)
      • Tool & Language (6)
        • Edit Plus (1)
        • Git (1)
        • Python3 (2)
        • Java (2)
      • Android (18)
        • Java (6)
        • Flutter (12)
      • Window (2)
        • Visual Studio 없이 WPF (1)
        • MFC (1)
      • 독서 (14)
        • Inside Javascript (7)
        • Database Internals (6)
        • 한 글 후기 (1)
  • 링크

    • github
    • website
  • 인기 글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.6
에버듀
[백준] 3665 - 최종 순위 (G1)
상단으로

티스토리툴바