BOJ_1021 : 회전하는 큐

👉 문제링크

1021번: 회전하는 큐

---

🔹 문제 🔹

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다.
지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
  1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
  2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
  3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다.
그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.)
이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

🔹 입력 🔹

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다.
N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다.
둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다.
위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

🔹 출력 🔹

첫째 줄에 문제의 정답을 출력한다.

 

---

🔸 문제 분석 🔸

양방향 순환 큐를 활용한 문제이다. 하지만 연산은 큐의 맨 앞 원소의 제거만 수행한다.

큐는 좌우로 원소의 쉬프트가 가능해야 한다. 배열, vector 모두 풀이 가능하지만 vector를 사용하였다.

🔸 코드 🔸

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
	int N, M, answer = 0;
	cin >> N >> M;

	vector<int> que(N);	//큐로 사용할 vector

	for (int i = 0; i < N; i++)	//큐에 1~N 값 넣어주기
		que[i] = i + 1;

	int size = N, pick, idx, temp;	//현재 큐의 크기, 찾는 값, 찾는 값의 인덱스, 임시 변수

	for (int i = 0; i < M; i++) {
		cin >> pick;	//찾는 값
		idx = find(que.begin(), que.end(), pick) - que.begin();	//찾는 값의 인덱스

		//출력 테스트
		/*cout << "\nque : ";
		for (int j : que) {
			cout << j << " ";
		}
		cout << "\npic : " << pick << "  idx : " << idx << endl;*/
		
		while (true) {
			if (que.front() == pick) {	//값을 찾음
				que.erase(que.begin());
				size--;
				break;
			}
			if (idx <= size / 2) {		//큐를 왼쪽으로 밀기
				temp = que.front();
				que.erase(que.begin());
				que.push_back(temp);
			}
			else {						//큐를 오른쪽으로 밀기
				temp = que.back();
				que.erase(que.end()-1);
				que.insert(que.begin(), temp);
			}
			answer++;
		}
	}
	cout << answer;
	return 0;
}

🔸 코드 해석 🔸

vector<int> que(N);	//큐로 사용할 vector

int형 vector를 양방향 큐로 사용하였다.

 

for (int i = 0; i < N; i++)	//큐에 1~N 값 넣어주기
	que[i] = i + 1;

문제에서는 설명이 부족했지만, 큐는 자동으로 1~N 까지의 값이 입력된다.

(원래 찾는 값은 처음 큐 상태의 원소의 위치이기 때문)

 

cin >> pick;	//찾는 값
idx = find(que.begin(), que.end(), pick) - que.begin();	//찾는 값의 인덱스

찾는 값을 입력받으면, 그 값의 현재 인덱스를 확인한다.

 

while (true) {
	if (que.front() == pick) {	//값을 찾음
		que.erase(que.begin());
		size--;
		break;
	}
	if (idx <= size / 2) {		//큐를 왼쪽으로 밀기
		temp = que.front();
		que.erase(que.begin());
		que.push_back(temp);
	}
	else {						//큐를 오른쪽으로 밀기
		temp = que.back();
		que.erase(que.end()-1);
		que.insert(que.begin(), temp);
	}
	answer++;
}

큐의 처음 값이 찾는 값과 같으면 제거한다. (큐의 맨 앞에서만 pop이 가능하기 때문)

아니라면, 현재 인덱스를 확인하고 더 가까운 방향으로 쉬프트 한다. (반복)

---

🔸 code review 🔸

• A : fine부분의 예외처리가 필요하지 않을까요?
  • find 사용 하실 때, empty에 대한 예외처리가 있으면 좋을 것 같습니다.
  • find 했을 때, 해당 자료가 없으면 vector의 size를 출력합니다. (엄밀히 말하면, vector의 end)
    • 포인터 연산을 했기 때문에(vector의 begin 주소를 뺌) vector의 size가 나오는 것.

if (idx == que.size()) {
    continue;
}

• B : 일반적(실무적)으로 타당한 의견이지만 이와 같이 입력의 범위와 조건이 명확한 알고리즘 문제풀이에서는 예상 불가능한 예외가 없기 때문에 그럴 필요는 없습니다. 여기서도 find에서는 찾는 값이 항상 있을 수 밖에 없기 때문에 오버헤드만 증가할 뿐 무의미합니다.

 

• A : while문에 첫 if문을 while문 조건으로 바꿀 수 있을 것 같습니다.

 

🔸 feedback code 🔸

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
	int N, M, answer = 0;
	cin >> N >> M;

	vector<int> que(N);	//큐로 사용할 vector

	for (int i = 0; i < N; i++)	//큐에 1~N 값 넣어주기
		que[i] = i + 1;

	int size = N, pick, idx, temp;	//현재 큐의 크기, 찾는 값, 찾는 값의 인덱스, 임시 변수

	for (int i = 0; i < M; i++) {
		cin >> pick;	//찾는 값
		idx = find(que.begin(), que.end(), pick) - que.begin();	//찾는 값의 인덱스
		
		while (que.front() != pick) { //찾는 값이 나올때까지 반복
			if (idx <= size / 2) {		//큐를 왼쪽으로 밀기
				temp = que.front();
				que.erase(que.begin());
				que.push_back(temp);
			}
			else {						//큐를 오른쪽으로 밀기
				temp = que.back();
				que.erase(que.end()-1);
				que.insert(que.begin(), temp);
			}
			answer++;
		}
		que.erase(que.begin());
		size--;
	}
	cout << answer;
	return 0;
}

---

🔸 end 🔸

오버헤드, 메모리 관리 등을 신경쓰면서 코딩하려니 새롭게 신경써야 할 부분이 많아진 것 같다.

아직 익숙하지 않아서 그런 것 같은데, 좋은 개발자가 되기 위해서 더 철저히 따져보아야 겠다.