백준 #30644 띠 정렬하기

문제 링크

[30644 띠 정렬하기]

문제 설명

숫자가 무작위 순서로 적혀있는 띠가 존재하고 띠를 잘라서 오름차순으로 만들어야 한다. 이때 띠 간의 순서는 자유롭게 변경 가능하고 띠 안의 순서는 역순으로 변경이 가능하다. 띠를 최소한으로 잘라야 하는 문제

코드

import sys
input = sys.stdin.readline
from collections import defaultdict


N = int(input())
origin = list(map(int, input().split()))
sorted = sorted(origin)
indices = defaultdict(int)
for i in range(N):
    indices[origin[i]] = i

cnt = 0
order = 0
for i in range(N - 1):
    cur = sorted[i]
    nxt = sorted[i + 1]

    if indices[cur] - indices[nxt] == 1:
        if order == -1:
            continue
        elif order == 1:
            cnt += 1
        order = -1
    elif indices[cur] - indices[nxt] == -1:
        if order == 1:
            continue
        elif order == -1:
            cnt += 1
        order = 1
    else:
        cnt += 1
        order = 0

print(cnt)

풀이

원래 숫자들의 인덱스를 저장해주고 정렬된 후의 숫자들을 탐색하면서 연속된 숫자의 인덱스 차이가 1이면 안잘라도 되기 때문에 인덱스 차이를 비교해주면서 풀이했다.