Today I Learned

토요일까지 이틀남았다!

회전 수열

회전 수열

n개의 정수로 이루어진 수열 A는 회전하는 수열이다.
회전 한번은 수열의 첫 수만큼 왼쪽으로 회전하는데 맨 왼쪽은 맨오른쪽으로 이동한다. 수열을 총 m번 회전했을 때 최종 수열의 첫 값을 출력해라

입력
6 5
7 6 8 4 8 8
출력
6

코드 및 문제 풀이

• 이 문제는 자바로 ArrayDeque을 이용해서 풀어봤으나 timeout으로 실패했다. 바로 index만 바꿔서 풀어봤으나 이것도 뒤쪽 테스트 케이스에 fail 했다.

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);
		int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int r = m%n;
		int firstIndex = (n-r) % n;
		
		System.out.println(A[firstIndex]);
	}
}

• 처음 자바로 풀었던 코드를 파이썬으로 풀어보니 바로 풀렸다. 이 사이트는 언어별로 풀어지는게 있고 아닌게 있는 것 같다.

• rotate라고 deque에 따로 회전을 시켜주는 함수가 있다.

  rotate(n=1)
  Rotate the deque n steps to the right. If n is negative, rotate to the left.
  When the deque is not empty, rotating one step to the right is equivalent to d.appendleft(d.pop()), and rotating one step to the left is equivalent to d.append(d.popleft()).

from collections import deque

n, m = map(int, input().split())
a = list(map(int, input().split()))

q = deque(a)

for _ in range(m):
	f = q[0];
	q.rotate(-f)

print(q[0])