[PS] (백준 2840번) 행운의 바퀴 C++

전체 코드는 가장 하단에 있습니다 ~

밉다

진짜

이렇게 미운 문제는 처음이다 ...

이 글을 찾아찾아 들어오신 분들도 다 비슷하시겟죠 ...

 

문제 이해

저게대체뭔소린가 ... 싶었다 증말

옆에 있던 언니가 수능 문제 같다고

수능으로 나왔으면 본인은 대학을 못 왔다는 발언을 하였음

 

어떤 글자인지 결정하지 못하는 칸은 '?'

-> 모든 바퀴에 꽉 차게 글자가 들어가는 것이 아니다!

-> 즉 다섯 칸 중 비어있는 칸이 존재할 수 있고, 그 자리에는 '?'

 

적어놓은 종이에 해당하는 행운의 바퀴가 없다면 '!'

-> 넣으려고 하는 문자와 현재 들어가있는 문자가 다른 경우

-> 넣으려고 했는데 그 문자가 이미 다른 곳에 들어가 있는 경우

 

 

시작점은 랜덤으로 잡고 (나는 문제에 표시된 저 부분을 시작으로 잡았다)

이후부터는 바로 직전의 index 값부터 개수를 세어가면서 입력에 맞춰 하나씩 넣으면 된다

 

이제 저걸 배열로 바꾸면

이렇게 한 칸씩 채운다고 생각했다

 

memset 함수

메모리의 내용을 원하는 크기만큼 특정 값으로 설정

#include <string.h>

-> memset(포인터(배열의시작주소), 설정 값, 빼열의 크기)

 

주의할 점

예외 처리가 까다롭다고 느꼈다

 

총 4가지 경우가 존재한다

1. 넣으려고 하는 문자와 현재 들어가 있는 문자가 동일 - continue;

2. 새로 넣는데, 그 문자가 이미 다른 자리에 들어가 있음 - break;

3. 새로 넣는데, 그 문자가 어디에도 들어가 있지 않음

4. 넣으려고 하는 문자와 현재 들어가 있는 문자가 다른 경우 - break;

-> 3의 경우에만 해당 자리에 값을 넣을 수 있다

 

또한 인덱스가 음수나, N 보다 커지지 않도록 적절한 조절이 필요하다

마지막에 넣은 인덱스 기준으로 (위에서는 H, 즉 1) 반시계 방향으로 돌면서 출력한다

 

반례

질문 게시판에 있는 걸 거의 돌려봤는데, 가장 결정적이었던 반례는

4 4

1 A

1 A

1 A

1 A

였다

답은 ! 임

-> 배열에 AAAA 이 채워지는데, 이미 방문한 문자이기 때문에 바퀴가 존재하지 않는 것으로 본다

 

전체 코드

#include <iostream>
#include <string.h>
using namespace std;

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

	int N, K;
	cin >> N >> K;

	char ch_array[101];
	int check_array[26];
	memset(ch_array, '?', sizeof(ch_array));
	memset(check_array, 0, sizeof(check_array));

	int number;
	char input;
	int index = 0;
	int flag = 1;
	for (int i = 0; i < K; i++) {
		cin >> number >> input;

		index = (index + number) % N;

		if (ch_array[index] == input) {
			// 넣으려고 하는 문자와 들어가 있는 문자가 같음
			continue;
		}
		else {
			if (ch_array[index] == '?' && check_array[input - 'A'] == 1) {
				// 새로 넣는데, 그 문자가 이미 다른 곳에 들어가 있음
				flag = 0;
				break;
			}
			else if (ch_array[index] == '?') {
				// 새로 넣음
				ch_array[index] = input;
				check_array[input - 'A'] = 1;
			}
			else {
				flag = 0;
				break;
			}
		}
	}

	if (flag) {
		for (int i = 0; i < N; i++) {
			cout << ch_array[(index - i + N) % N];
		}
	}

	else {
		cout << "!";
	}

}

 

+ 알고리즘 정신적 지주님의 칭찬