[백준 파이썬] 2505번 두 번 뒤집기

[백준 파이썬] 2505번 두 번 뒤집기

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

2505번: 두 번 뒤집기

 

문제

입력

-첫 줄에는 숫자판의 크기를 나타내는 정수 n이 주어진다 

-두 번째에는 두 개의 구간이 뒤집힌 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다

출력

첫 두줄에는 뒤집어야 할 구간을 차례대로 출력해야 한다  각 줄에는 구간[i, j]을 나타내면 이는 i와 j를 빈칸 사이에 두고 출력해야 하면 답은 항상 존재한다 

풀이

-뒤집는 구간을 선택 방법은 왼쪽에서 부터 시작하느냐 오른쪽에서부터 시작하느냐에 따라 나눠지면

왼쪽에서만 2번 뒤지는 방법을 선택할수 있고 오른쪽 두 번 , 왼쪽 오른쪽, 오른쪽 왼쪽 이렇게 총 4가지 경우의 수가 존재한다. 항상 답이 존재해야 하므로 우리는 이 4개 가지 방법을 다 확이해 야한다 

 

왼쪽에서부터 시작할 경우 어떻게 구간을 구할 수 있을까?

나는 순서대로 처음 주어진 배열을 돌면서 일단 순서대로 있는지 체크하였다.(1부터 순서대로 나열되어 있는지)

만약 순서대로 있지 않다면 그 순서대로가 아닌 값 하고 인덱스 값을 저장하였다

처음 순서대로 나오지 않은 값의 인덱스를 left 순서대로 나오지 않은 값 중에서 가장 작은 값이 나오는 나오는 위치를 right에 집어넣었다. 그 후 그 left와 right 사이의 배열의 값들을 다른 배열로 만들어 뒤집어 다시 원래 배열에 넣었다 

 

오른쪽부터 시작할 경우에는 주어진 숫자판의 크기값을 시작으로 -1 일한 값들이 뒤에서 순서대로 나열되어있는지 확인하면 처음순서대로 나오지 않은 값의 인덱스를 right에 순서대로 나오지 않는 값 중 가장 큰 값의 인덱스를 left에 저장하였다

left와 right를 구하고 난 후 그 범위만큼의 배열의 새로 만들고 그 새로 만든 배열을 뒤집고 난후 원래 배열에 집어넣었다

 

각 구간을 구하는 방법에서 left와 right값을 구하면 정답에 넣은 배열에 넣었다 그리고 if문을 이용하여 순서대로 나와있다면 정답을 출력하고 순서대로 나와있지 않다면 다른 경우의 방법으로 돌리는 형태로 정답을 출력하도록 만들었다. 

 

이거 적으면서 이게 무슨 말이지 남이 이해하지 못할 것 같긴 하다 플래티넘이라 그런지 생각보다 어려웠다

일단 손으로 위의 방법으로 뒤집어 보면 이해가 될 거다 

 

 

코드

import copy

n = int(input())
array = list(map(int, input().split()))
array2 = [x for x in range(1, n + 1)]
array3 = copy.deepcopy(array)
array4 = copy.deepcopy(array)
array5 = copy.deepcopy(array)
ans = []


def left_change(array):
    global ans
    for i in range(1):
        check = False
        count = 1
        temp = 100000
        left = 0
        right = 0

        for i in range(n):
            if array[i] != count:
                if check == False:
                    left = i
                if array[i] <= temp:
                    temp = array[i]
                    right = i
                    check = True

            count += 1
        array_temp = array[left:right + 1]
        array_temp = array_temp[::-1]
        now = 0
        for i in range(left, right + 1):
            array[i] = array_temp[now]
            now += 1
        ans.append([left + 1, right + 1])
    return array


def right_change(array):
    global ans
    for i in range(1):
        check = False
        count = n
        temp = 0
        left = 0
        right = 0

        for i in range(n - 1, -1, -1):
            if array[i] != count:
                if check == False:
                    right = i
                if array[i] >= temp:
                    temp = array[i]
                    left = i
                    check = True

            count -= 1
        array_temp = array[left:right + 1]
        array_temp = array_temp[::-1]
        now = 0
        for i in range(left, right + 1):
            array[i] = array_temp[now]
            now += 1
        ans.append([left + 1, right + 1])

    return array


ans_array = left_change(array)
ans_array = left_change(ans_array)

if ans_array == array2:

    print(*ans[0])
    print(*ans[1])

else:
    ans = []
    ans_array = right_change(array3)
    ans_array = right_change(ans_array)

    if ans_array == array2:

        print(*ans[0])
        print(*ans[1])
    else:
        ans = []
        ans_array =left_change(array4)
        ans_array = right_change(ans_array)

        if ans_array == array2:

            print(*ans[0])
            print(*ans[1])
        else:
            ans = []
            ans_array =right_change(array5)
            ans_array = left_change(ans_array)
            print(*ans[0])
            print(*ans[1])

 

결과