백만년만의 알고리즘.. 바닥난 집중력으론 실버 2도 쉽지 않다^^
몇시간이 걸린지 모르겠는 문제는 BOJ 12933 오리
BOJ 12933 오리
오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.
영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.
갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.
녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.
영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.
입출력
[입력]
첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다.
[출력]
영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.
나의 풀이
몇달만이기도 하고 비교적 낮은 난이도의 구현 문제이기 때문에 단순하게 접근하려고 노력했던 것 같다. 사실 그마저도 그리 빠르게 생각나진 않았지만,,
무조건 q-u-a-c-k 순서대로 울음 소리가 이루어 져야 하기 때문에 일단 모든 입력의 시작은 반드시 q 로 시작 되어야 한다.
맨 첫 글자가 q 인지를 먼저 확인하고, 이후 나오는 문자들을 탐색하면서 이 전에 나온 글자 다음에 나올 글자가 맞는지를 확인 했다.
이 과정에서는 <map> 을 사용하였는데 q-u, u-a, a-c, c-k, k-q 와 같이 5쌍을 넣어주고 바로 바로 확인할 수 있도록 했다.
전체적인 알고리즘은 입력된 울음 소리의 앞쪽부터 한마리씩 확인을 해 나가는 과정이다. 탐색 하면서 조건에 맞는 글자인지를 map 을 활용해 확인하고, 확인한 글자는 체크한다.
모든 글자를 체크할 때 까지 탐색을 반복하되, 나와선 안되는 글자가 나오면 올바르지 않은 울음 소리임을 확인했으니 -1 을 return 한다.
예를 들어 한번의 탐색이 끝난 후 마지막으로 확인한 글자는 반드시 k 이어야 한다. 그렇지 않으면 quack 이란 단어가 온전하지 않음을 의미하기 때문이다!
한번 '틀렸습니다' 를 받았는데, 모든 울음 소리는 5개의 글자 q-u-a-c-k 순서대로이기 때문에 문자열의 길이는 반드시 5의 배수이어야 하고 오리의 울음소리의 길이는 5 이상이기 때문에 오리가 0마리 라면 -1을 반환 해야 하는 경우를 체크해 주니 통과하였다.
코드
#include <iostream>
#include <vector>
#include <map>
// boj 12933 오리, 구현
using namespace std;
map<char, char> nextCh;
int countDuck(string sound){
if (sound.size() % 5 != 0) return -1;
if (sound[0] != 'q') return -1;
vector<bool> isChecked(sound.size(), false);
int alive = sound.size()-1;
int count = 0;
char before = sound[0];
isChecked[0] = true;
int i = 1;
while (alive>0){
for (; i < sound.size(); ++i) {
if (isChecked[i]) continue;
if (nextCh[before] == sound[i]){
isChecked[i] = true;
alive--;
before = sound[i];
} else continue;
}
if (before == 'k'){
count ++;
if (alive==0) break;
for (int j = 0; j < sound.size(); ++j) {
if (!isChecked[j]) {
before = sound[j];
isChecked[j] = true;
alive--;
i = j+1;
break;
}
}
} else{
count = -1;
break;
}
}
if(count==0) count = -1;
return count;
}
int main(){
string sound;
cin>>sound;
nextCh.insert({'q','u'});
nextCh.insert({'u','a'});
nextCh.insert({'a','c'});
nextCh.insert({'c','k'});
nextCh.insert({'k','q'});
cout<<countDuck(sound);
return 0;
}
