[CodingTest] 백준 #1021 회전하는 큐 / rotate()

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

1021번: 회전하는 큐

 

 

내 풀이

from collections import deque
n,m=map(int,input().split())
nums=list(map(int,input().split()))

arr=deque([i+1 for i in range(n)])
gap=0
count=0
flag=0

for i in range(m):
    flag = 0
    if nums[i]==arr[0]:
        arr.popleft()   
        
    else:
        gap = arr.index(nums[i])
        if gap>len(arr)/2:
            gap = len(arr)-gap
            flag=1 
            
        if flag==0:
            for j in range(gap):
                arr.rotate(-1)
                #앞에서 뒤로
                
            arr.popleft()
            count+=gap
        
        elif flag==1:
            
            for j in range(gap):
                #뒤에서 앞으로
                arr.rotate(1)
            arr.popleft()
            count+=gap
        
print(count)

 

 

주석 

from collections import deque
n,m=map(int,input().split())
nums=list(map(int,input().split()))

arr=deque([i+1 for i in range(n)])
#인덱스 간의 거리차 저장 변수 gap
gap=0
#2, 3번 연산 횟수 저장 변수 count
count=0
#좌우의 gap을 계산하고, 좌, 우 중 더 작은 값에 따라 계산하기 위해 좌, 우를 구분해줄 변수 flag
#좌측의 gap이 더 작을 경우 flag = 1, 우측의 gap이 더 작을 경우 flag = 0 으로 설정
flag=0

for i in range(m):
    #flag 초기값은 0으로 설정
    flag = 0
    #만약 0번째 값과 nums의 i번째 값이 같다면 pop
    if nums[i]==arr[0]:
        arr.popleft()   
        
    #0번째 값과 nums의 i 번째 값이 다르다면 rotate해주어야 함
    else:
    #gap은 인덱스 0과 arr에서 nums[i]의 인덱스의 비교이므로, 결국 arr.index(nums[i] 이다.
        gap = arr.index(nums[i])
        #gap이 아래의 값보다 크다면, 좌측 gap이 더 작은 것으로 판단
        if gap>len(arr)/2:
            gap = len(arr)-gap
            flag=1 
        #우측 gap이 더작다면    
        if flag==0:
        	#gap번 만큼 앞에서 뒤로 rotate
            for j in range(gap):
                #앞에서 뒤로
                arr.rotate(-1)
            #rotate완료 시 pop, count에 gap 더하기               
            arr.popleft()
            count+=gap
        #좌측 gap이 더 작다면
        elif flag==1:
            
            for j in range(gap):
                #gap번 만큼 뒤에서 앞으로 rotate
                arr.rotate(1)
            #rotate완료 후 pop, count에 gap 더하기
            arr.popleft()
            count+=gap
        
print(count)

덱과 rotate를 사용해보았다. 

rotate 방향이 헷갈린다 ㅠㅠ -1은 앞에서 뒤로,,, 1은 뒤에서 앞으로,, 왜 거꾸로 같이 느껴지죠,, ㅠㅠ

rotate를 사용하면 0번째 값과의 비교만 하면돼서 편리하다.

 

다른 사람 풀이 

n, m = map(int, input().split())
dq = [i for i in range(1, n+1)]

ans = 0

for find in map(int, input().split()):
    ix = dq.index(find)
    ans += min(len(dq[ix:]), len(dq[:ix]))
    dq = dq[ix+1:] + dq[:ix]

print(ans)

이분은 덱이나 큐를 사용하지 않고 리스트를 사용했다.

index 바로 찾아서 그냥 바로 해당 값을 삭제하셨는데 간결하다! 하지만 나는 rotate를 사용해보고 싶었다 ㅎ

 

다른 사람 풀이는 왤캐 해석이 어려울까 .. 파이썬은 코드 잘 짜면 한 줄 코딩도 가능해서 해석이 더 어려운 것 같다 ㅠㅠ 해석이 어려우므로 ,, 다른 사람 코드 리뷰는 여기까지만 .. ㅠ 

나도 코드 간결하고 쉽게 잘 짜고 싶다!!! ㅠㅠ