[백준][Python] 16219 정렬하기

# 문제 링크

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

 

# 문제

종영이는 입력 데이터를 만들기 귀찮았다. 사실 문제를 생각하는 것 자체도 귀찮았다. 그래서 IOI 2015의 "정렬하기" 문제 ( acmicpc.net/problem/10924 )를 변형해 입력 데이터를 재탕하기로 했다! 종영이의 문제를 해결하자. 종영이의 문제는 다음과 같다.

---

에르맥과 아이잔은 길이 N의 수열 S를 가지고 게임을 하려고 한다. 수열 S에는 0부터 N-1까지의 정수가 한 번씩만 등장한다. 이 게임은 수열을 오름차순으로 정렬하는 게임으로, 아이잔은 수열을 정렬하려고 하고, 에르맥은 정렬되지 않게 하려고 하며, 불가피할 경우 최대한 오랫동안 정렬되지 않게 하는 것이 목표이다. 

한 게임에서, 각 라운드마다 에르맥이 두 수를 정해 서로의 위치를 바꾸고, 다음에 아이잔이 두 수를 정해 서로의 위치를 바꾼다. 에르맥과 아이잔 모두 같은 수를 정해 위치가 바뀌지 않게 할 수도 있다. 해당 라운드에서 수열이 오름차순으로 정렬되면 게임은 끝이 나며, 처음부터 정렬되어 있는 경우 필요한 라운드의 수는 0이다.

게임을 여러 번 하기 위해, 에르맥과 아이잔은 수열 S에 대해, S를 M번 변형하여 게임을 하려고 한다. 길이 M의 배열 X와 Y가 있을 때, 게임의 번호를 게임을 한 순서대로 0부터 M-1까지라 하면, i번째 게임을 시작하기 전에, i-1번째 게임을 시작했던 순간의 수열에서 X[i]번째 위치의 수와 Y[i]번째 위치의 수를 바꾼다. 그 후 새로운 수열을 게임에서 사용한다. -1번째 게임을 시작했던 순간의 수열은 편의상 S라고 정의하자.

각 게임에 대하여, 아이잔이 특정 라운드가 지난 후 반드시 승리하는지와, 승리한다면, 필요한 라운드 수의 최솟값을 구해야 한다.

 

# 입력

첫 줄에 N이 주어진다. (1 ≤ N ≤ 2 × 10의 5승)

둘째 줄에 수열 S가 N개의 수가 공백으로 구분되어 주어진다. (수열 S는 0부터 N-1까지의 정수가 한 번씩 등장하는 수열이다.)

세번째 줄에 M이 주어진다. (1 ≤ M ≤ 6 × 10의 5승)

M개의 줄에 걸쳐, X[i]와 Y[i]가 공백으로 구분되어 주어진다. (0 ≤ X[i], Y[i] < N)

 

# 출력

M개의 게임에 대해, 각 게임이 일어난 순서대로, 게임이 무한히 진행 가능하다면 -1, 아니면 필요한 최소 라운드의 수를 공백으로 구분되어 출력한다.

 

# 예제

예제입력	예제출력
5 4 3 2 1 0 3 0 4 1 3 2 2	-1 0 0
5 4 3 2 1 0 6 0 1 1 2 2 3 3 4 0 1 1 2	-1 -1 -1 -1 -1 -1

 

---

# 문제 풀이

문제는 장황하지만 구현해야 하는 기능은 정렬인가 판단하는 것 뿐이다. 하지만 거기에 빡빡한 시간과 예외케이스가 곁들여진 문제~...

 

맨 처음 문제를 읽고 나면 답이 0 아니면 -1 밖에 안 나올 것 같지만.. 골드4가 이렇게 간단할리 없잖아!! << 하면서 특수한 상황이 자주 발생하는 유우우우력한 후보인 n = 1부터 케이스를 생각해보다 보면, n = 2일 때 답이 1이 되는 경우가 발생함을 알 수 있다.

 

n=2 일 때 s 리스트의 상태는 다음과 같은 두 가지 케이스 뿐이다.

0 1	-> 정렬되어 있으므로 답은 0
1 0	-> 에르맥이 뒷구르기 앞구르기 옆구르기해도 결국 다음 턴 아이잔에 의해 "0 1" 으로 정렬 됨. 즉, 답은 1

 

이제 M번의 게임마다 정렬되어 있는지 판단하기만 하면 되는데,, 변수 범위가 십만이고 시간제한은 1초다. 매 게임마다 S리스트를 순회하며 정렬 상태인지 판단하는 것은 절대 무리이니, 꼼수를 써야 한다. 문제 조건으로 '수열 S는 0부터 N-1까지의 정수가 한 번씩 등장하는 수열' 이라고 하였으므로, 수열 S가 정렬된 상태일 경우는 하나 뿐이다. 그리고 정렬된 수열 S는 인덱스 값과 원소 값이 같다. 이 점을 활용해서 미리 정렬이 아닌 수의 개수(not_sort_num)를 구하고, 이 수로 수열 S가 정렬된 상태인지 판단하는 방식을 이용하였다.

 

게임을 실행 할 때마다 조건문으로 not_sort_num을 갱신해준 뒤, 해당 게임에서  not_sort_num이 0이 된다면 수열 S가 정렬된 상태이므로 답은 0이다. 만약 not_sort_num이 0이 아니라면 수열 S는 영원히 정렬될 수 없으므로 답은 -1 이다. 이때 예외 케이스인 n=2 일때 조건 처리를 한 번 더 해주었다.

 

https://github.com/taerimiiii/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/16219.%E2%80%85%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0

Algorithm/백준/Gold/16219. 정렬하기 at main · taerimiiii/Algorithm

 

 

맞은 코드

import sys
input = sys.stdin.readline

# 입력 처리
n = int(input())
s = list(map(int, input().split()))
m = int(input())

# 정렬되지 않은 수의 개수 구하기
not_sort_num = 0
for i in range(n) :
    if s[i] != i :
        not_sort_num += 1

# m번 게임 실행
for _ in range(m) :

    # x, y 입력 처리
    x, y = map(int, input().split())

    # 교환 좌표가 같다면 상태 변화가 없으므로 제외
    if x != y :

        # 교환 전 x좌표의 정렬 여부 구하기
        if s[x] == x :
            prev_x = True
        else :
            prev_x = False

        # 교환 전 y좌표의 정렬 여부 구하기
        if s[y] == y :
            prev_y = True
        else :
            prev_y = False

        # x, y 좌표 교환
        s[x], s[y] = s[y], s[x]

        # 교환 후 x좌표의 정렬 여부 구하기
        if s[x] == x :
            curr_x = True
        else :
            curr_x = False

        # 교환 후 y좌표의 정렬 여부 구하기
        if s[y] == y :
            curr_y = True
        else :
            curr_y = False
            
        # 교환 전 x좌표가 정렬 상태이었고, 교환 후 x좌표가 비정렬 상태인 경우
        if prev_x and not curr_x :   # 정렬이 깨지면(x좌표)
            not_sort_num += 1        # 정렬되지 않은 수 개수 + 1

        # 교환 전 x좌표가 비정렬 상태이었고, 교환 후 x좌표가 정렬 상태인 경우
        elif not prev_x and curr_x : # 정렬이 되면(x좌표)
            not_sort_num -= 1        # 정렬되지 않은 수 개수 - 1

        if prev_y and not curr_y :   # 정렬이 깨지면(y좌표)
            not_sort_num += 1        # 정렬되지 않은 수 개수 + 1
        elif not prev_y and curr_y : # 정렬이 되면(y좌표)
            not_sort_num -= 1        # 정렬되지 않은 수 개수 - 1

    # 출력 처리
    if not_sort_num == 0 :  # 정렬된 상태일 경우
        print(0, end=' ')
    elif n == 2 :           # 비정렬 + n=2 일 경우(특수상황)
        print(1, end=' ')
    else :                  # 비정렬 상태일 경우
        print(-1, end=' ')