[백준 2505번] 두 번 뒤집기 (Python3)

from itertools import *

def find(seq):
  start=end=0
  for i in range(N+1):
    if i!=seq[i]:
      if not start:
        start=i
      end = i
  return (start,end) if start else (1,1)

def reverse(seq,start,end):
  return seq[:start]+[*reversed(seq[start:end+1])]+seq[end+1:]

N = int(input())
seq = [0]+[*map(int,input().split())]

start,end = find(seq)

interval = []; s = start
while s<=end:
  interval.append(s)
  e = s
  while e<end:
    if abs(seq[e+1]-seq[e])==1:
      e += 1
    else:
      break
  interval.append(e)
  s = e+1
  
seq0 = [i for i in range(N+1)]
for s,e in combinations(interval,2):
  s1,e1 = min(s,e),max(s,e)
  seq1 = reverse(seq,s1,e1)
  s2,e2 = find(seq1)
  if reverse(seq1,s2,e2)==seq0:
    result = [(s1,e1),(s2,e2)]
for s,e in result:
  print(s,e)

브루트 포스로 해결하였다.

 

일단 풀이를 설명하면,

1. find 함수를 정의한다. find 함수는 현재 수열에서 원래 자리에 있지 않은 숫자의 시작지점과 끝지점을 출력한다.

2. 수열에서 숫자가 1씩 연속해서 증가하거나 감소하지 않는 경우, 구간이 나누어진다고 생각하고 연속해서 증가하거나 감소하는 구간에 대해 구간의 시작과 끝 인덱스를 interval에 저장한다.

3. interval의 모든 인덱스에 대해서 itertools.combinations을 활용하여 두 인덱스를 뽑아 해당구간을 뒤집어본다.

4. 뒤집었을 때, find함수를 실행하고 시작지점과 끝지점을 뒤집어본다.

5. 3,4 과정을 거쳤을 때 원하는 배치가 나왔으면 결과를 출력한다.

 

사실 2 에서 구간을 나눈 다음에 논리적인 방법으로 뒤집어야하는 구간을 찾고 싶었는데, 여러가지 예외가 발견되고 또 과정이 쉽지 않아서 그냥 브루트 포스로 해결하였다. 딱 두번만 뒤집는 문제이기 때문에 이 문제에서는 그게 더 낫기도 하다.

하지만 더 많은 횟수를 뒤집어야하는 문제도 있을 수 있기 때문에 다양한 풀이를 고민해봐야겠다.

 

 

오늘의 교훈) 뒤집어야하는 구간을 논리적으로 찾는 방법을 생각해보자