숫자 배열 이동을 역으로 추정하는 코드
https://codeup.kr/problem.php?id=4684

22-05-17

fail...
왼쪽으로 밀기 -> 구간 뒤집기 -> 왼쪽으로 밀기 순에서
역으로 추정하자

22-07-30

Fail

def last_left_push(lock,N):
    lock_1 = lock.copy()
    alpha = lock_1[0]
    i = 1
    while (key[alpha] != lock_1[i]) and (i<N):
        alpha = lock_1[i]
        i += 1
    return i

def converting(lock_2,N):
    convert = []
    beta = lock_2[0]
    j = 1
    while (len(convert) < 2) and (j<N):
        if (key[beta] != lock_2[j]) and (len(convert) == 0):
            convert.append(j+1)
            beta_ = beta
        if  (len(convert) == 1):
            if (key[beta_] == lock_2[j]) or (j == N-1):
                convert.append(j+1)
        beta = lock_2[j]
        j += 1
    return convert

N = int(input())
lock = list(map(int,input().split()))

key = {n:n+1 for n in range(1,N)}
key[N] = 1

answer = []

last_right = last_left_push(lock,N)
answer.append(N-(last_right-1))

lock_2 = lock[last_right-1:].copy()
lock_2 = lock_2 + lock[:last_right-1]

convert_index = converting(lock_2,N)
answer.append(convert_index)   

convert_range = list(range(convert_index[0],convert_index[1]+1))
if lock_2.index(1)+1 in convert_range:
    answer.append(N-(convert_range[len(convert_range)-1-convert_range.index(lock_2.index(1)+1)]-1))
else:
    answer.append(N-lock.index(1))

print(answer[2])
print(*answer[1],sep=' ')
print(answer[0])

어디가 틀린지 잘 모르겠음..! 디버깅 실패..

24-01-07

Success!

N = int(input())
number_list = list(map(int, input().split()))

# 왼쪽 밀기 함수

def left_sliding(n_list, n):
    
    n_list_left = n_list.copy()

    for _ in range(n):
        i = n_list_left.pop(0)
        n_list_left.append(i)
        
    return n_list_left
    
# 구간 뒤집기

def convert_numbers(numbers, a, b):
    intervals = numbers[(a-1):(b)]
        
    n_list_convert = []
    for i in range(len(numbers)):
        k = i+1

        if k in range(a,b+1):
            n_list_convert.append(intervals.pop())
        else:
            n_list_convert.append(numbers[i])
            
    return n_list_convert, a, b
    
def max_num_find(numbers, number):
    
    return 0 if len(numbers) <= number else number
    
    
def convert_processing(n_list,a = 0,b = 0):
     
    if (a > 0) and (b > 0):# validation
        
        return convert_numbers(n_list, a, b)
    
    else: #searching interval
        
        a, b = 1, 2
        
        # searching a
        for i in range(len(n_list)):
            
            pre = max_num_find(n_list,n_list[i])
            aft = n_list[i+1]
            
            if aft != pre+1:
                
                a = i+2
                b = i+2
                
                break
                
        # searching b
        while aft != (pre+1):
            
            try:
                aft = n_list[b]
            
            except:
                return n_list, -1, -1
                
            b += 1
            
        return convert_numbers(n_list, a, b)
                
        
def check_arrange(n_list):
    
    n_list_ = n_list.copy()
    pre = n_list_.pop(0)
    while len(n_list_) > 0:
        
        aft = n_list_.pop(0)
        if max_num_find(n_list,pre)+1 != aft:
            return False
        else:
            pre = aft
            
    return True
        
        
# 첫번째 왼쪽 밀기 & 구간 뒤집기
f_left = 1
arrange_validity = False

while not arrange_validity:# Stop When arrange_validity is True
    
    number_list_f_left = left_sliding(number_list,f_left) # 첫번째 왼쪽밀기
    number_list_convert, a, b = convert_processing(number_list_f_left) # 구간 뒤집기
    
    arrange_validity = check_arrange(number_list_convert)
    if (not arrange_validity) or (a < 0) or (b<0):
        f_left += 1
    if f_left > N:
        break
       
# 두번째 왼쪽 밀기
def check_site_one(n_list):
    
    for i in range(len(n_list)):
        
        if n_list[i] == 1:
            
            return i

s_left = check_site_one(number_list_convert)
arranged_list = left_sliding(number_list_convert,s_left)

# output
left_sliding_1 = N-s_left
int_a, int_b = a, b
left_sliding_2 = N-f_left

print(left_sliding_1)
print(int_a, int_b)
print(left_sliding_2)

Grid Search 기법으로 문제 풀이

문제 상황은 첫번째 왼쪽 K번 밀고 (a,b)번째 구역의 정렬을 역으로 뒤집고 다시 왼쪽 M번 밀어 만든 숫자 정렬을 제시한다.
K와 (a,b) 그리고 M에 대한 정보를 알아내는 것이 목표이다.

K : 2, (a,b): (4,7), M : 6인 상황을 예시로 들겠다.

1 2 3 4 5 6 7 8 9 10 -> (K:2) -> 3 4 5 6 7 8 9 10 1 2
(a,b): (4,7) -> 3 4 5 9 8 7 6 10 1 2
(M:6) -> 6 10 1 2 3 4 5 9 8 7

"6 10 1 2 3 4 5 9 8 7"란 input을 받고 K, (a,b), M을 추정해야 한다.
여기서 포인트는 답은 다중 답을 포함할 수 있으며, 숫자의 정렬은 (a,b) 수행에 의해서만 바뀔 수 있다. 따라서 나는 K, M을 찾기보단 (a,b)를 찾은 후 K, M을 상황에 따라 조정하는 방법으로 문제를 풀이했다. 그리고 input을 원래 정렬대로 만드는 방법을 찾은 후, K, (a,b), M에 맞는 숫자로 다시 산출하였다.

코드에서 # 첫번째 왼쪽 밀기 & 구간 뒤집기 구역을 보자.
왼쪽으로 M'번 밀고 (a,b) 뒤집기를 진행한다. (M = 10 - M')
여기서 포인트는 해당 프로세스 진행 후 숫자 정렬이 1씩 증가하는 순으로 정렬되어야 한다는 것이다.
예를 들어, M' = 1인 경우를 보자.
"6 10 1 2 3 4 5 9 8 7" -> (M' : 1) -> "10 1 2 3 4 5 9 8 7 6"
숫자 5 뒤에 6 대신 9가 나오므로 정렬이 이상하다. => 정렬이 역으로 뒤집힌 구간을 의미한다.
여기서 나의 코드는 a를 7로 결정한다.
그리고 6의 자리를 b로 결정한다.
(a,b) => (7, 10)
만약 6이 5보다 앞 자리에 있다면 M'를 1 증가시켜 해당 과정을 다시 진행한다.

그런 다음 #두번째 왼쪽 밀기 구간을 보자. 여기서는 K'를 산출한다. (K = 10 - K')
"6 10 1 2 3 4 5 9 8 7" -> (M' : 1) -> "10 1 2 3 4 5 9 8 7 6"
(a,b) : (7, 10) -> "10 1 2 3 4 5 6 7 8 9"
K'는 첫번째 자리가 1이 되도록 K' 왼쪽 밀기를 진행한다. 따라서 K'는 1이다.
"6 10 1 2 3 4 5 9 8 7" -> (M' : 1) -> "10 1 2 3 4 5 9 8 7 6"
(a,b) : (7, 10) -> "10 1 2 3 4 5 6 7 8 9"
(K':1) -> "1 2 3 4 5 6 7 8 9 10"

따라서 답은 아래와 같다.
K = 10 -1 = 9
(a, b) = (7, 10)
M = 10 - 1 = 9

답 검증 진행
input : "6 10 1 2 3 4 5 9 8 7"
"1 2 3 4 5 6 7 8 9 10" -> (K:9) -> "10 1 2 3 4 5 6 7 8 9"
(a,b) : (7, 10) -> "10 1 2 3 4 5 9 8 7 6"
(M : 9) -> "6 10 1 2 3 4 5 9 8 7" (input과 동일)