baekjoon(1021-회전하는 큐)_ python

1) 문제

 

2) 예시

 

 

3) 제출

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
origin = list(range(1, n+1))
want = list(map(int, input().split()))
tmp = origin.index(want[0])
cnt = min(tmp, len(origin)-tmp)

for i in range(1, m):
    origin.pop(tmp)
    # first = abs(origin.index(want[i]) - tmp)
    # second = abs(len(origin) - first)
    # cnt = min(first, second)
    cnt += min(abs(origin.index(want[i]) - tmp), abs(len(origin) - abs(origin.index(want[i]) - tmp)))
    tmp = origin.index(want[i])

print(cnt)

4) 메모리/ 시간/ 코드 길이

5) PLUS

circular queue에 대해 너무 어려워했는데 5/25(어제) 해결했던 요세푸스 문제를 통해

2022.05.24 - [백준/python] - baekjoon(1158-요세푸스 문제)_ python

baekjoon(1158-요세푸스 문제)_ python

circular queue에 자신감을 얻고 더 알가기로 했다!!

 

이번에도 전처럼 푸는데 약 1시간 정도 걸렸다

 

(문제 해결 방법)

- 변수 설명 -

n = 큐의 크기

m = 뽑아내려고 하는 수의 개수

 

origin 리스트 = 1부터 n까지의 숫자가 있는 리스트(n개의 원소를 포함하고 있는 양방향 순환 큐)

want 리스트 = 지민이가 찾고자 하는 원소

tmp = want에 찾고자 하는 원소가 origin의 어디에 있는지 

 

1) (n,m, origin, want) 입력 받기, (tmp, cnt) 저장 => 설명 생략

2) for 위로 첫 번째 want의 cnt는 알았으니 1부터 m전까지 for 문을 돌림

우선, want[0]의 원소를 위에서 cnt와 tmp를 구했으므로 pop 해줌

그 이후로 want[1]부터 값을 찾을 것임

3) 

예를 들어 1~10까지 있다고 가정하고 계산을 해봤다.

first는 초록부분이고 second는 노란 부분이다.

4) first와 second를 구한 후, first와 second 중 작은 값이 움직인 값이니까 cnt에 더해준다.

5) tmp에는 want[i]가 있는 인덱스 값을 넣어 다음 값을 for문에서 또 돌린다.