[C++]백준(BOJ) 17499번 수열과 시프트 쿼리 문제풀이

 

https://www.acmicpc.net/problem/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개의 줄에는 각 줄 마다 연산이 주어집니다.

 

 

---

예제 입력, 출력

 

 

 

 

---

알고리즘 분류

#수학

#구현

 

---

 

해설

총 세가지 케이스의 연산을 수행할 수 있는 프로그램을 구현해야하는 문제이다.

 

1번 연산은 단순히 수열의 N번째 요소에 대해 더하기 연산만 구현하면 되지만

2, 3번 연산은 수열에 대한 쉬프트 연산을 수행해야 한다. 직관적으로 접근했을때 반복문을 이용하여 하나씩 요소들을 움직이는 방향으로 구현해도 되겠지만, 문제에 나와있듯이 해당 방법을 사용하지 않고 시프트 연산을 구현하는 것이 문제의 목적이다.

 

이를 해결하기 위해 배열을 이용한 원형 큐에서의 인덱스 관리에 사용되는 방법을 응용하여 적용해 보았다.

• 시작 인덱스(초기 값 0), 끝 인덱스(초기 값 배열 크기 - 1) 설정
• 배열의 요소를 이동하지 않고 N번 시프트 한 만큼 인덱스를 이동
• 초기 설정한 배열의 크기를 인덱스가 넘게된다면 0으로 회귀
• 배열의 실제 저장순서에 상관 없이 시작 인덱스부터 끝 인덱스까지 순서대로 출력

 

왼쪽으로 N번 시프트 연산 수행 시

시작 인덱스, 끝 인덱스 각각 N 더함, 단 배열 크기를 넘어가게 된다면 다시 0으로 회귀

 

오른쪽으로 N번 시프트 연산 수행 시

왼쪽 시프트 연산과 반대로 N을 빼야 하는데 해당 경우에는 "배열 크기를 넘어갈 시 0으로 회귀" 를 이용한 인덱스 관리를 사용할 수 없게 되므로

왼쪽으로 (배열 크기 - N)번 시프트 연산 수행으로 바꿔서 생각.

 

---

소스코드

// 배열을 이용한 원형 큐의 인덱스 관리를 이용하여 구현
#include <iostream>
#include <string>


using namespace std;
int n = 0; // 수열의 길이
int q = 0; // 연산을 수행할 횟수
int arr[200001] = { 0, }; // 수열
int s_index = 0; // 첫 번째 인덱스
int e_index = 0; // 마지막 인덱스

void case_1() {
	int a, b; // a번째 요소 에 b를 더함
	cin >> a >> b;
	arr[(s_index + a - 1) % n] += b;
}

void case_2() {
	int a; // 오른쪽으로 a칸 시프트
	cin >> a;
    // 왼쪽으로 (n - a)칸으로 쉬프트 하는 것과 같다
	s_index = (s_index + (n - a)) % n;
	e_index = (e_index + (n - a)) % n;
}

void case_3() {
	int a; // 왼쪽으로 a칸 시프트
	cin >> a;
	s_index = (s_index + a) % n;
	e_index = (e_index + a) % n;
}

// 수열을 출력하는 함수
void display() {
	int i;
	// 마지막 인덱스값은 접근하지 못하기 때문에 외부 변수로 선언하고 따로 출력
	for (i = s_index; i != e_index; i = (i + 1) % n) {
		cout << arr[i] << " ";
	}
	cout << arr[i];
}
int main() {
	cin >> n >> q;
	e_index = n - 1; // 종료 인덱스 초기값 설정
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	// 연산 수행
	for (int i = 0; i < q; i++) {
		int case_t;
		cin >> case_t;
		if (case_t == 1) {
			case_1();
		}
		else if (case_t == 2) {
			case_2();
		}
		else if (case_t == 3) {
			case_3();
		}
	}
	display();
}