백준 1021번 Pseudo code

문제 링크

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

1021번: 회전하는 큐

 

시간 제한 / 메모리 제한

2 초

128 MB

 

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

10 3
2 9 5

예제 출력

8

 

문제 풀이를 위해 생각한 것

1. 처음에는 문제가 잘 이해되지 않아 문제를 이해하는 데에 시간을 많이 씀. N이 덱의 크기, M이 뽑으려는 숫자의 초기 인덱스라는 것.
2. 문제에서 주어지는 인덱스와 1:1 매칭 되도록 1부터 N까지 총 N 크기의 오름차순 덱 구현 (1, 2, 3, 4, 5, 6, ..., N)
3. POP은 왼쪽에서만 할 수 있다.
4. 뽑으려는 원소의 첫 인덱스 (2, 9, 5)는 주어진 순서대로 찾아야 한다. 
   • 2번을 popleft하기 위해 연산을 수행한 뒤,
   • 바뀐 덱 구성에서 다시 9번을 찾기 위한 연산을 수행...
5. 한 원소가 오른쪽으로 회전할 것인지, 왼쪽으로 회전할 것인지 결정하는 기준은 원소가 덱의 중심을 기준으로 왼쪽과 오른쪽 둘 중 어느 끝 단과 가까운가 이다.
6. (다시) POP은 왼쪽에서만 할 수 있다.

 

사용한 자료구조

덱.

삽입 삭제가 양 끝단에서 이루어질 수 있다.

회전 시키는 연산의 시간 복잡도가 O(1)이다. 

 

풀이 코드

n, m = 첫줄의 n과 m을 정수로
toFind = 두번째 줄 찾아야 할 원소 입력을 정수 리스트로
d = 덱 선언 및 1부터 n까지의 원소로 초기화
len = 덱의 길이 할당
cnt = 0

toFind의 원소 i에 대하여:
	while True:
		if d[0] == i:
			d.popleft()
			len -= 1
			break
		else:
			if len - find(i) > len / 2: // 왼쪽 회전
				while d[0] != i:
					d.append(d.popleft())
					cnt += 1
			elif len - find(i) < len / 2: // 오른쪽 회전
				while d[0] != i:
					d.appendleft(d.pop()) 
					cnt += 1
                    
print cnt

 

시간 복잡도 분석

O(NM) 

각 원소 M마다, 중심으로부터 양 끝단 까지의 절댓값 중 작은 값 만큼 회전 (O(1) 연산)

 

문제에서 중요한 부분

덱을 회전시키는 기준을 명확히 정의해야 코드로 구현할 수 있었다.

 

본 문제의 시간제한에서는 충분히 여유가 있었지만, 더 타이트한 시간제한이 있었다면 매 연산마다 덱의 길이를 구하기 위해 len() 연산을 사용했을 때 시간 초과가 날 수 있었다. len연산은 O(N)이기 때문이다. 따라서 len() 연산을 사용하는 대신에 len을 한 번 구해 변수에 저장한 뒤, pop할 때마다 변수의 값을 1씩 감소시키며 비교를 수행하면 O(1)에 덱의 길이를 구할 수 있다.

 

*수정사항*

파이썬 len() 연산은 O(1)이라고 한다.

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

https://stackoverflow.com/questions/1115313/cost-of-len-function

Cost of len() function