(백준 2840번 행운의 바퀴 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 4

백준 2840번

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

2840번: 행운의 바퀴

 

풀이 방법

 

1. 길이가 N인 deque를 만들어 '?'으로 초기화한다.

2. K번 동안 입력 (n, k)에 대해 k가 맨 뒤에 가도록 설정하고, 맨 뒤에서 n번째에 다음 글자를 넣도록 한다.

문제 예시1에서 _ _ A → _ BA 이 되도록 한다.

3. B가 제일 뒤가 되도록 deque 원소를 이동한다. _ BA → A_B

 

2번과 3번 과정을 지속한다.

 

#define  _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;

int main() {
	int N, K;
	scanf("%d %d", &N, &K);

	deque<char> dq;
	for (int i = 0; i < N; i++) dq.push_back('?');
	int n; char k; bool Flag = true;
	scanf("%d", &n); scanf("%c", &k), scanf("%c", &k);
	K--;
	dq.back() = k;
	while (K--) {
		scanf("%d", &n); scanf("%c", &k), scanf("%c", &k);

		for (int i = 0; i < n; i++) {
			dq.push_front(dq.back());
			dq.pop_back();
		}
		
		if (dq.back() != '?' && dq.back() != k) {
			printf("!");
			return 0;
		}
		else {
        	// 기존에 같은 문자가 있으면 Flag를 false로 바꾼다.
			if (dq.end()-1 != find(dq.begin(), dq.end()-1, k)) {
				Flag = false;
			}
			dq.back() = k;
		}
	}
	dq.push_front(dq.back());
	dq.pop_back();
	
	if (Flag == false) {
		printf("!"); return 0;
	}
	for (auto iter = dq.begin(); iter != dq.end(); iter++) printf("%c", *iter);
	return 0;
	}

 

처음에 문제가 안 풀려서 반례를 찾아봤는데 아래 반례가 처리가 안된 걸 확인했다.

https://www.acmicpc.net/board/view/26362

글 읽기 - 반례

 

따봉도 누름 ㅎㅎ