-
(백준 2840번 행운의 바퀴 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 4PROGRAMMING/STL 2024. 3. 27. 20:46
백준 2840번
https://www.acmicpc.net/problem/2840
2840번: 행운의 바퀴
첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓
www.acmicpc.net
풀이 방법
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
글 읽기 - 반례
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
따봉도 누름 ㅎㅎ 'PROGRAMMING > STL' 카테고리의 다른 글
(백준 1012번 유기농배추 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 2 (0) 2024.04.04 (C++)DFS stack을 이용해서 구현해보기 (0) 2024.04.04 (백준 2346번 풍선 터뜨리기 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 3 (0) 2024.03.26 ★연결리스트 LinkedList (0) 2024.03.25 (백준 2110번 공유기 설치 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 3 (2) 2024.03.22