💻 Computer Science/Algorithm🐇

[python] 백준 1021 : 회전하는 큐

노가다 권씨 2024. 3. 9. 15:24
728x90
반응형

target value를 리스트 제일 앞으로 가져와서 빼내야한다. 리스트 앞쪽으로 가져올때 왼쪽으로 한칸씩 옮기기, 오른쪽으로 한칸씩 옮기기 이 두 동작만을 이용한다. 

 

논리구조를 생각해보면 입력된 target value에 대해 2,3번 동작을 동시에 실행한다. 그리고 각 target value에 대해 더 적은 수행횟수를 갖는 동작의 수행횟수를 전체 count에 더해준다. 예를들어 target value가 4,6일때 처음 큐에서 2,3번 동작을 한번씩 수행해서 각각의 수행횟수를 카운트한다. 이제 이 두 시행을 비교해주는 함수를 정의해 (이 함수에는 리스트 초기화 기능이 수반된다. 예를들어 아래의 리스트 L에대해 go_left함수를 먼저 수행했을때 반환되는 L은 원본리스트가 아니므로 go_right에 넣으면 안된다. go_left 실행후 리스트를 한번 초기화해주고 go_right에 넣어줘서 비교해준다.

def go_left (L:list,value):
    cnt_left=0
    while True:
        
        if L[0]==value:
            L.remove(L[0])

            break

        else:        
            val=L.pop(0)
            L.append(val)
            cnt_left+=1

    return L,cnt_left

def go_right(L:list,value):
    cnt_right=0
    while True:

        if L[0]==value:
            L.remove(L[0])

            break

        else:
            val=L.pop()
            L.insert(0,val)
            cnt_right+=1
            
    return L,cnt_right

2,3번 동작에 대한 코드는 위와같다. 리스트의 첫번째자리에 target value가 올때까지 각 왼,오른쪽으로 한칸씩 리스트 요소들을 움직인다. target value가 첫번째자리에 온다면 해당값을 리스트에서 제거하며 while문을 종료한다

위에서부터 left, right로 1~10 리스트에서 4를 찾은 결과. 결과리스트는 4가 뽑힌 직후의 상태로 0번 index엔 숫자 5가 위치한다. 각 실행횟수는 3번,7번으로 이경우엔 left의 실행횟수를 채택해야한다. (실제 문제해결에선 리스트까지 반환할 필요는 없다. cnt횟수만 쓰이므로.. 그냥 잘 돌아가는지 확인하기위해 출력한거임 ㅇㅇ..)

 

이 두 함수를 이용해서 입력값으로 리스트형성 -> 첫번째 target value에 대해 두 함수 시행횟수 비교 -> target value가 빠진, 순서 뒤바뀐 리스트에서 두번째 target value에 대해 두 함수 시행횟수 비교 -> 모든 target value를 찾을때까지 iteration 반복 하면서 동작하면된다. 

 

이때 문제점은.. 바로 리스트의 초기화였다. 두 함수에 동일한 리스트를 넣어 시행횟수를 비교해야한다. 근데 left든 right든 어느 한 함수가 시행되고나면, 위엣 그림처럼 리스트가 어지럽혀진다. 이 리스트를 다시 원래로 초기화시킨후 나머지 함수에 넣어 시행횟수를 측정해야한다. 

근데 만약.. target value가 한개라면 그냥 리스트자체를 비워버리고 다시 채워넣으면되지만.. 예를들어 길이 10짜리 리스트에 target value가 4,7 두개가 있다고하면.. left함수를 먼저 시행해서 4를 찾을경우 리스트는 [5,6,7,8,9,10,1,2,3]이 된다. 그러나 right가 4를 찾는 행동을 하려면 다시 원래 리스트인 [1,2,3,4,5,6,7,8,9,10]을 입력해줘야하므로 리스트를 초기화해줘야한다. 여기까진 괜찮은데 두번째 target value인 7을 찾는과정에선, [5,6,7,8,9,10,1,2,3]리스트에서 7을 찾아줘야한다. 이번에도 left먼저 실행하면 리스트는 [8,9,10,1,2,3,5,6]이 된다. 여기서가 문제다. 이제 right함수가 7을 찾는데 걸리는 횟수를 찾아야하는데 이때 입력되어야 하는 리스트는 아까 4를 찾고 남은 리스트인 [5,6,7,8,9,10,1,2,3]이다. 이런식으로 리스트를 초기화하되, 아예 처음이 아닌, 바로 직전 target value를 찾은 상황의 리스트로 초기화 해야된다는건데 이게 꽤나 큰 걸림돌이었다.

 

그러다 문득 든 생각... '애초에 left,right 각각 리스트를 만들어버리면 초기화할 필요가 없지않나..?'  그렇다. 어차피 결과 cnt크기만 다를뿐 target value를 빼낸 리스트는 left, right 둘다 똑같다. 그냥 각각 리스트를 만들어주자.

def go_left (L,value):
    cnt_left=0
    while True:
        
        if L[0]==value:
            L.remove(L[0])

            break

        else:        
            val=L.pop(0)
            L.append(val)
            cnt_left+=1

    return cnt_left

def go_right(L,value):
    cnt_right=0
    while True:

        if L[0]==value:
            L.remove(L[0])

            break

        else:
            val=L.pop()
            L.insert(0,val)
            cnt_right+=1
            
    return cnt_right    

list_target=[]

l,m=map(int,input().split())

list_target.append(input().split())

cnt=0
list_origin_right=[]
list_origin_left=[]
for i in range(l):
    list_origin_right.append(i+1)
    list_origin_left.append(i+1)
    
for i in range(m):
        
    l_num=go_left(list_origin_left,int(list_target[0][i]))
    r_num=go_right(list_origin_right,int(list_target[0][i]))

    cnt+=min(l_num,r_num)

print(cnt)

list_target[0][i]와 같이 2차원 행렬로 찾는 이유는.. 리스트에 바로 값을 추가해줄때 이상하게 입력값들이 또 따로 리스트에 쌓여져 나온다. 아마 입력값 갯수를 정하지않고 여러개 입력받다보니 자체적으로 리스트로 만들어 받나보다.

 

위에서 말했듯 각각 list_origin 을 만들어 시행, 비교해준다. 두 함수의 시행횟수중 최솟값을 cnt에 계속 더해준다

 

각각 리스트를 만들어 입력받는다는 생각을 못해 한참 고민했다. 리스트를 잘 초기화시키는 방법이 도저히 생각나지 않았다. 

 

그래도 요근래 푼 문제중 가장 깔끔하게 생각해서 푼거같다.

 

반응형