N개의 수로 이루어진 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 배열에 연산을 총 M번 적용하려고 한다. 이때, 가장 처음에 K번째에 있던 수가 모든 연산이 종료된 후 몇 번째 위치로 이동하는지 구하는 프로그램을 작성하시오.
배열에 적용할 수 있는 연산은 정수 i 하나로 이루어져 있다.
i가 양의 정수인 경우에는 배열 A의 처음 i개의 순서를 뒤집는 것이고, i가 음의 정수인 경우에는 마지막 -i개의 순서를 뒤집는 것이다.
예를 들어, N = 5이고, A = [1, 3, 2, 4, 5]인 경우에 연산 3을 적용하면, 배열 A는 [2, 3, 1, 4, 5]가 된다. 여기에 연산 -4를 적용하면, 뒤의 4개를 순서를 뒤집어 [2, 5, 4, 1, 3]이 된다. 가장 처음에 1번째 위치에 있던 수는 4번째 위치로 이동하게 되고, 3번째 위치에 있던 수는 1번째 위치로 이동하게 된다.
입력
첫째 줄에 배열 A의 크기 N(1 ≤ N ≤ 100,000)과 위치 K(1 ≤ K ≤ N), 연산의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째에는 배열 A에 들어있는 수가 1번째 수부터 순서대로 주어진다. 배열에 들어있는 수는 100,000보다 작거나 같은 자연수이다. 배열에는 같은 수가 여러 번 들어있을 수도 있다.
셋째 줄부터 M개의 줄에는 연산을 나타내는 정수 i가 한 줄에 하나씩 주어진다. i는 절댓값이 N보다 작거나 같은 0이 아닌 정수이다.
출력
첫째 줄에 K번째 수가 연산 M번이 완료된 후에 몇 번째 위치로 이동했는지 출력한다.
예제 입력 1
5 1 2
1 3 2 4 5
3
-4
예제 출력 1
4
일단 문제를 보면 입력 범위가 굉장히 크다는 것을 알 수 있다. 따라서 시간 초과 또는 메모리 제한을 고려할 필요가 있다.
그러나 일단 문제를 구현해보면
import sys
if __name__=="__main__":
N,K,M=map(int, input().split())
arr = list(map(int, input().split()))
for _ in range(M):
i = int(input())
if i >0:
tmp = arr[:i]
in_True=True
for j in range(i):
arr[j]=tmp[-1-j]
if j == K-1 and in_True:
K=i-1-j+1
in_True = False
else:
tmp = arr[i:]
in_True=True
for j in range(i,0,1):
arr[j]=tmp[-1-j]
if N+j+1 == K and in_True:
K=N+i+(-1-j)+1
in_True = False
print(K)
실제로 리스트의 숫자들을 이동시켜 볼 수 있다. 그러나 이렇게 하면 시간 초과가 날 수 밖에 없다.
그렇다면 해당 위치와 위치의 숫자만 실제로 이동시켜 보면 되지 않을까?
import sys
if __name__=="__main__":
N,K,M=map(int, input().split())
arr = list(map(int, input().split()))
target=arr[K-1]
for _ in range(M):
i = int(input())
if i >0:
tmp = arr[:i]
in_True=True
for j in range(i):
if j != K-1:
continue
if j == K-1 and in_True:
arr[j]=tmp[-1-j]
K=i-1-j+1
in_True = False
break
else:
tmp = arr[i:]
in_True=True
for j in range(i,0,1):
if N+j+1 != K:
continue
if N+j+1 == K and in_True:
arr[j]=tmp[-1-j]
K=N+i+(-1-j)+1
in_True = False
break
print(K)
그러나 여전히 99%에서 시간 초과를 겪을 수 있다. 따라서
1. for문을 넣지 말고
2. 실제 리스트의 해당 위치의 숫자를 이동시키지 말자
즉, 위치만 고려해본다.
최종 정답
import sys
if __name__=="__main__":
N, K, M = map(int, input().split())
arr = list(map(int,input().split()))
for _ in range(M):
i = int(input())
if i > 0:
if K <= i:
K = i-K+1
else:
if K > i+N:
K = N + i - (K - 1 - N)
print(K)
빠르게 해결 할 수 있었다.
틀렸다고 또는 시간 초과 난다고 당황하지 말자.
그러나 내가 틀렸는지 안틀렸는지 알고 고치니깐 풀 수 있는거지 실전에서는 바로 고려해서 풀자.
