개요

백준 2840번: 행운의 바퀴

• 입력
  첫째 줄에 바퀴의 칸의 수 N과 상덕이가 바퀴를 돌리는 횟수 K가 주어진다. (2 ≤ N ≤ 25, 1 ≤ K ≤ 100)

  다음 줄부터 K줄에는 바퀴를 회전시켰을 때 화살표가 가리키는 글자가 몇 번 바뀌었는지를 나타내는 S와 회전을 멈추었을 때 가리키던 글자가 주어진다. (1 ≤ S ≤ 100)

• 출력
  첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없다면 "!"를 출력한다.

접근 방식

1. 이번에도 원형 연결리스트를 사용할 수 있었지만 벡터를 이용해 구현해보았다.

2. 원형으로 돌아야하므로 cursor변수를 만들어줘서 벡터의 원소를 가리키는 용도로 사용했다.

3. 기본적으로 char형 벡터 ans에 N개의 '?'를 넣어준 후
   setAns()함수를 통해 ?를 알파벳으로 변경해주는 작업을 하였다,

4. 조건이 많은 문제다.

   • 같은 문자가 회전바퀴에 있다면 안된다!
   • 마지막 문자를 기준으로 시계방향으로 출력해야한다.
     -> 이 코드 같은 경우는 커서는 반시계방향으로 돌아가며 답을 적기 때문에
     (원판이 시계방향으로 돌면 알파벳이 적히는 방향은 반시계로 적힌다.)
     마지막 값을 기준으로 index를 줄이면서 반대로 출력해야한다.

5. ans벡터에 값을 설정해주는 setAns()함수를 bool형으로 선언하고,
   값을 넣어주다가 조건에 안맞으면 바로 false를 return해서 !를 출력하게 구현하였다.

코드

#include<iostream>
#include<vector>
using namespace std;

int N, K, cursor=0;
//답 배열
vector<char> ans;
//입력받는 두개 값 배열
vector<pair<int, char>> inputArr;

void input() {
	//몇번 돌린건지
	int inputInt =0;
	//어떤 바퀴나왔는지
	char inputChar = ' ';
	cin >> N>> K;
	for (int i = 0; i < N; i++) {
		ans.push_back('?');
	}
	for (int i = 0; i < K; i++) {
		cin >> inputInt >> inputChar;
		inputArr.push_back(make_pair(inputInt, inputChar));
	}
}
/// <summary>
/// inputArr[index]의 문자 ans벡터에 넣어주기 
/// </summary>
/// <param name="index"></param>
/// <returns>ans벡터에 같은 문자가 있거나, 같은 자리에 다른 문자가 오게될 경우 false 나머지 true</returns>
bool setAns(int index) {
	//S 변수(바퀴 몇번 돌렸는지)
	int S=inputArr[index].first;
	//커서가 ans벡터 사이즈 넘어가면 0으로 초기화하는 부분
	for (int i = 0; i < S; i++) {
		if (cursor + 1 == ans.size())
			cursor = 0;
		else
			cursor++;
	}
	//ans의 cursor자리에 ?가 잇다면 그냥 해당 자리에 넣어줌
	if(ans[cursor]=='?')
	ans[cursor] = inputArr[index].second;
	//만약 cursor자리에 다른 문자가 이미 들어가 있다면 false return해서 ! 출력
	else if(ans[cursor]!= inputArr[index].second)
	{
		return false;
	}
	//cursor자리 제외하고 나머지 칸에 다른 문자 들어가 있다면 false 리턴해서 ! 출력
	for (int i = 0; i < cursor;i++) {
		if (ans[i] == inputArr[index].second)
			return false;
	}
	//cursor자리 제외할때 cursor가 ans벡터의 끝을 가리키는지 아닌지 검색
	if (cursor + 1 < ans.size()) {
		for (int i = cursor + 1; i < ans.size(); i++) {
			if (ans[i] == inputArr[index].second)
				return false;
		}
	}
	//나머진 다 true 반환
	return true;
}

void solution() {
	//K번 만큼 반복
	for (int i = 0; i < K; i++) {
		//false 하나라도 나올 시 ! 출력
		if (!setAns(i)) {
			cout << "!";
			return;
		}

	}
	//마지막 문자를 기준으로 시계방향으로 출력해야하므로 cursor--를 ans벡터사이즈만큼 반복하면서 출력
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[cursor];
        //cursor가 0이라면 끝값가리키도록 변경
		if (cursor - 1 < 0) cursor = ans.size() - 1;
		else cursor--;
	}


}

int main() {
	input();
	solution();
}

문풀후생

같은 문자 못 쓰는 조건도 첨에 못 보고 시간 좀 걸려서 알아냈고,
마지막에 반대로 출력하는 과정에서

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[cursor];
        //cursor가 0이라면 끝값가리키도록 변경
		if (cursor - 1 < 0) cursor = ans.size() - 1;
		cursor--;
	}

else를 처음에 빼놓고 실행했더니 끝값을 계속 패스해서 시간이 좀 걸렸었다.