#2840

• 문제

상덕이는 최근에 행운의 바퀴를 구매했다. 상덕이는 바퀴의 각 칸에 알파벳 대문자를 아래 그림과 같이 적었다.

바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 또, 바퀴는 시계방향으로만 돌아간다. 바퀴 옆에는 화살표가 있는데, 이 화살표는 항상 한 곳을 가리키고 있으며, 돌아가는 동안 가리키는 글자는 바뀌게 된다. 위의 그림에서는 H를 가리키고 있다.

상덕이는 바퀴를 연속해서 K번 돌릴 것이다. 매번 바퀴를 돌릴 때 마다, 상덕이는 화살표가 가리키는 글자가 변하는 횟수와 어떤 글자에서 회전을 멈추었는지를 종이에 적는다.

희원이는 상덕이가 적어놓은 종이를 발견했다. 그 종이를 바탕으로 상덕이가 바퀴에 적은 알파벳을 알아내려고 한다.

상덕이가 종이에 적어놓은 내용과 바퀴의 칸의 수가 주어졌을 때, 바퀴에 적어놓은 알파벳을 알아내는 프로그램을 작성하시오.

• 코드

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

using namespace std;

bool fillPattern(int n, int k, stack<int>& num, stack<char>& alp, vector<char>& result) {
	result.assign(n, '?'); //칸 수 만큼 만들기
	int tip = 0; // pointer
	int j; // 같은 글자가 위치한 자리
	
	result[tip] = alp.top();
	alp.pop();

	for (int i = 1; i < k; i++) {
		tip = (tip + num.top()) % n ; // pointer 이동
		num.pop();


		if (find(result.begin(), result.end(), alp.top()) != result.end()) { //이미 해당 글자가 vector에 들어가 있는 상태라면 
			for (j = 0; j < n; j++) {
				if (result[j] == alp.top()) { //같은 글자가 위치한 자리를 파악
					break;
				}
			}
			if (j == tip) { //같은 자리에 위치한다면 넘어감
				alp.pop();
				continue;
			}
			else { // 같은 자리에 위치하지 않는다면 같은 글자가 두 번 이상 등장
				return false;
			}
		}

		if (result[tip] == '?') {
			//새로운 글자라면 넣음
			result[tip] = alp.top();
			alp.pop();
		}
		else { //이미 같은 위치에 다른 글자가 채워져 있는 것이므로 
			return false;
		}
	}

	return true;
}



int main()
{
	int n, k; //바퀴의 칸의 수, 상덕이가 바퀴를 돌리는 횟수
	int s; // 글자가 바뀐 횟수
	char c; // 회전을 멈추었을 때 가리키던 글자
	stack<int> num; //글자가 바뀐 횟수를 저장한 배열
	stack<char> alp; //회전을 멈추었을 때 가리키던 글자를 저장한 배열
	vector<char> result; // 결과를 저장

	//입력
	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> s >> c;
		num.push(s);
		alp.push(c);
	}

	//연산 및 출력

	if (fillPattern(n, k, num, alp, result)) {
		for (int i = 0; i < n; i++) {
			cout << result[i];
		}
	}
	else {
		cout << "!";
	}

	return 0;
}

• 해설

1. fillPattern 함수

- 원판의 칸을 채우는 함수

: 유추가 불가능한 곳은 '?'로 설정하기 위해 result의 초기값을 '?'로 설정

: 뒤에서부터 유추를 하기 위해 alp의 top원소를 result[0]에다 저장

: k회 반복하며 연산을 시작

: 원판이기 때문에 queue처럼 pointer 자리에 num의 top원소를 더하고 이를 n으로 나누었을 때의 나머지로 tip을 이동

: 이미 해당 글자가 vector에 들어가 있는 상태라면 같은 글자가 위치한 자리를 찾아서 이게 pointer의 위치와 같다면 그냥 넘어감

: 같지 않다면 규칙에 어긋나므로 return false

: 만약 새로운 글자라면 pointer 위치에 글자를 넣음 

: 그렇지 않으면 이미 같은 위치에 다른 글자가 채워져 있는 것이므로 규칙에 어긋나 return false

: 위 과정을 모두 통과하면 규칙 위반에 해당되지 않으므로 return true

 

2. main 함수

: num과 alp를 스택에 받음

: fillPattern 함수를 통해 규칙 위반을 확인하고 규칙에 어긋나지 않으면 원소 출력, 그렇지 않으면 '!' 출력