제로베이스 20220318

코딩테스트 연습

1. 홍익 투어리스트

• 도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, … , $N$번 구역이 존재하고, $N$번 구역에서 시계 방향으로 한 칸 더 갈 경우 $1$번 구역으로 도착한다.

• 홍익대학교에는 명소가 존재한다. 도현이는 알찬 투어를 위해 명소만을 방문하려 한다. 도현이는 $1$번 구역에 서있다.

• 도현이를 위해 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

  1. $1$ $i$ : $i$번 구역이 명소가 아니었다면 명소로 지정되고, 명소였다면 지정이 풀리게 된다. ($1 \leq i \leq N$)

  2. $2$ $x$ : 도현이가 시계방향으로 $x$만큼 이동한다. ($1 \leq x \leq 10^9$)

  3. $3$ : 도현이가 명소에 도달하기 위해 시계방향으로 최소 몇 칸 움직여야 하는 지 출력한다. 명소가 존재하지 않는 경우 $-1$을 출력한다.

입력

• 첫째 줄에 구역의 개수 $N$ ($1 \leq N \leq 500\,000$)과 쿼리의 개수 $Q$ ($1 \leq Q \leq 100\,000$)가 정수로 주어진다.

• 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번째 구역이 명소라면 $A_i$는 $1$, 그렇지 않다면 $0$이다.

• 셋째 줄부터 $Q$줄에 걸쳐 본문의 쿼리가 주어진다. $3$번 쿼리는 하나 이상 존재한다.

출력

•  $3$번 쿼리가 주어질 때마다 해당 쿼리의 값을 출력한다.

풀이

# your code goes here
 
import sys
 
# 첫째 줄에 구역의 개수 N과 쿼리의 개수 Q 가 정수로 주어진다.
 
N, Q = list(map(int,sys.stdin.readline().split()))
 
# 둘째 줄에 길이 N의 수열 A가 주어진다. i번째 구역이 명소라면 A_i는 1, 그렇지 않다면 0이다.
 
A = list(map(int,sys.stdin.readline().split()))
 
famous = {}
 
# {인덱스 : 거리}
for num in range(0,len(A)):
	if A[num] == 1:
		famous[num] = num
 
 
p = 0
i = 0
x = 0
# 셋째 줄부터 Q줄에 걸쳐 본문의 쿼리가 주어진다. 3번 쿼리는 하나 이상 존재한다.
 
for _ in range(0,Q):
	query = list(map(int,sys.stdin.readline().split()))
	# 각 쿼리별 행동
	# 1 i : i번 구역이 명소가 아니었다면 명소로 지정되고, 명소였다면 지정이 풀리게 된다.
	# 장소 번호는 1~N번까지 존재한다.
	if query[0] == 1:
		i = query[1] - 1
 
		# 명소 인덱스에 없으면 추가(i-p or len(A)-i)
		# 명소는 {인덱스 : 거리}이다.
		if i not in famous.keys():
			if i-p < 0:
				famous[i] = len(A)-i
			else:
				famous[i] = i-p
		# 명소 인덱스에 있으면 제거
		else:
			del famous[i]
 
	# 2 x : 시계방향으로 x만큼 이동한다.
	if query[0] == 2:
		x = query[1] % len(A)
		p += x
		p %= len(A)
 
		for key,val in famous.items():
			if val-x < 0:
				famous[key] = len(A)-x
			else:
				famous[key] = val-x
 
	# 3 : 명소에 도달하기 위해 시계방향으로 최소 몇 칸 움직여야 하는 지 출력한다.
	# 명소가 존재하지 않는 경우 -1을 출력한다.
 
	if query[0] == 3:
		if famous != {}:
			print(min(famous.values()))
		else:
			print(-1)

채점 결과

• 오답(시간 초과)

리뷰

• 최대한 시간최적화를 위해 이런저런 노력을 해보았으나, 모두 실패로 돌아갔다.

• 애당초 이 문제를 python으로 푼 사람이 단 한명밖에 없는것을 보면, python 자체가 느려서 그럴수도 있겠다는 생각이 든다.