백준 온라인 저지 (BOJ) 17499 수열과 시프트 쿼리

문제

백준 온라인 저지를 여행하다 보면 하나의 수열이 주어지고 여기에 여러 가지 연산을 하는 문제들을 만나볼 수 있습니다.

진수는 백준 온라인 저지에서 문제를 풀다 다음과 같은 문제를 찾았습니다.

길이가 N인 정수 수열 [a1, a2, ..., aN] 이 주어진다. 다음과 같은 연산들을 수행한 후 수열을 출력하는 프로그램을 작성하시오.

• 1 i x : ai에 정수 x만큼 더한다.
• 2 s : 수열을 오른쪽으로 s칸 시프트한다.
• 3 s : 수열을 왼쪽으로 s칸 시프트한다.

수열을 오른쪽으로 한 칸 시프트하면 수열 [a1, a2, …, aN-1, aN] 은 [aN, a1, a2, …, aN-1] 이 되고

수열을 왼쪽으로 한 칸 시프트하면 수열 [a1, a2, …, aN-1, aN] 은 [a2, …, aN-1, aN, a1] 이 된다.

진수는 빠르게 코딩하여 제출하였는데 '시간 초과' 판정을 받았습니다.

진수가 작성한 코드는 시프트 연산을 수행할 때마다 반복문이 N번 실행되어 너무 느리기 때문입니다.

진수는 이 문제를 풀어 '맞았습니다!!' 를 띄워줄 누군가를 기다리고 있습니다.

입력

첫 번째 줄에 수열의 길이 N (2 ≤ N ≤ 200,000) 과 연산의 개수 Q (1 ≤ Q ≤ 200,000) 가 주어집니다.

두 번째 줄에는 정수 a1, a2, ..., aN (-10,000 ≤ ai ≤ 10,000) 이 주어집니다.

다음 Q개의 줄에는 각 줄 마다 연산이 주어집니다. 

출력

첫 번째 줄에 Q개의 연산을 차례대로 수행한 후 a1, a2, …, aN 을 공백을 사이에 두고 출력합니다.

제한

• 1 ≤ i ≤ N
• -10,000 ≤ x ≤ 10,000
• 1 ≤ s ≤ N-1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include<bits/stdc++.h> using namespace std; int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);     int n, q, top = 0;     int* arr = nullptr;     int x, y, z;     cin >> n >> q;     arr = new int[n];     for (int i = 0; i < n; i++)         cin >> arr[i];     for (int i = 0; i < q; i++) {         cin >> x;         switch (x)         {         case 1:             cin >> y >> z;             arr[(top + y - 1) % n] += z;             break;         case 2:             cin >> y;             top = (top + (n-y)) % n;             break;         case 3:             cin >> y;             top = (top + y) % n;             break;         default:             break;         }     }     for (int i = top; i < n; i++)         cout << arr[i] << ' ';     for (int i = 0; i < top; i++)         cout << arr[i] << ' ';     cout << '\n';     delete[]arr;     return 0; } Colored by Color Scripter

cs

 

수열의 시작점(?)을 이용해서 연산을 최소화하는 문제였다.