[BOJ 4500 // C++] “Bubble Gum, Bubble Gum, in the dish, how many pieces do you wish?”

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 4500번 문제인 “Bubble Gum, Bubble Gum, in the dish, how many pieces do you wish?”이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/4500 

4500번: “Bubble Gum, Bubble Gum, in the dish, how many pieces do you wish?”

큐 또는 덱 등의 자료구조를 이용해 문제를 해결해보자.

 

구체적으로는 다음과 같은 구현으로 문제를 해결할 수 있다. 먼저 사람들을 큐에 순서대로 저장해두고, 첫 사람이 큐의 맨 앞에 올 때까지 큐의 앞의 사람을 뒤로 보내는 것을 반복하자. 그 다음 맨 앞부터 n번째로 보이는 사람을 찾기 위해 큐의 앞의 앞의 사람을 뒤로 보내는 작업을 n-1회 더 반복하자.

 

위와 같은 과정을 거치면 문제의 답을 구해낼 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <deque>
using namespace std;

void solve() {
	string s; cin >> s;
	deque<string> que;

	while (!('0' <= s[0] && s[0] <= '9')) {
		que.push_back(s);
		cin >> s;
	}
	string target = que.back(); que.pop_back();
	while (que.front() != target) {
		que.push_back(que.front());
		que.pop_front();
	}

	int K = stoi(s);
	while (K--) {
		que.push_back(que.front());
		que.pop_front();
	}

	cout << que.back() << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) solve();
}