문제 이해 단계
https://www.acmicpc.net/problem/12933
"quack"이라는 문자열이 존재하면 오리가 한 마리 있다는 의미인데,
이 문자들이 여러 개 겹쳐있다.
특이한 점은 quackquack 이런 식으로
연속적으로 문자열을 이을 수 있는 경우에는 한 마리로 취급한다는 것이다.
이런 조건일 때 오리를 최소로 했을 때의 오리 수를 구하는 문제.
문제 접근 단계
어떻게 풀지 고민하다가 힌트를 보고 감을 잡았다.
녹음: quqaquuacakcqckkuaquckqauckack
오리 1: ____q_u__a___ck_______________
오리 2: __q__u_ac_k_q___ua__ckq_u__ack
오리 3: qu_a_______c___k__qu___a_ck___힌트에서는 오리가 3마리가 있는데, 이를 판단할 수 있는 기준이 동시에 우는 오리의 수였다.
이 말을 돌려 말하면 한 오리가 'quack'문자열을 끝마치기 전에
새로운 'q'가 나온다면, 이는 오리가 1마리 더 있다는 뜻이다.
해당 힌트에서는 아래 오리 3이 우는 동안 두 마리가 더 울고 있다.
이렇게 3마리가 운다는 것을 알 수 있다.
____q_u__a__ck___
___q__u_ac_k_q__u
qu_a_______c____k
정리하자면,
오리의 최소 수는 "quack"이라는 문자열이 겹쳐있는 만큼이다.
이 원리를 이용해서 String형 벡터를 사용할 것이다.
벡터 안에 문자열의 개수가 곧 오리의 수를 뜻한다.
해당 문제에서는 quack이라는 순서 또한 중요한데,
해당 문자가 해당 순서에 오는 것이 맞는가를 확인하는 방법으로 문자열의 길이를 세는 방법을 사용했다.
예를 들어, a가 들어올 때는 qu가 미리 들어와 있어야 한다. 즉 문자열의 길이는 2여야 한다.
그리고 k가 들어와야 한다면 기존의 문자열은 quac여야 하므로 문자열의 길이는 4여야 한다.
이런 식으로 문자를 넣기 전에 해당 문자열의 길이를 확인하여 순서를 확인하다.
문자열 길이는 아래와 같이 매핑한다.
q = 0 -> 이 때는 새로운 문자열을 만든다.
u = 1
a = 2
c = 3
k = 4
다음으로 판단해봐야 할 것은, 다음에 오는 문자 'q'가 연속된 quack인지 확인하는 과정이다.
무작정 문자가 q라고 새로운 문자열을 만들어버린다면
문제에서 요구하는 연속된 울음소리인지는 확인하지 못한다.
그래서 여기서는 mod 연산을 사용하여 quack이라는 문자쌍이 완성되었는지를 확인한다.
quack이라는 문자열의 길이는 5이기 때문에 mod5이다.
넣으려는 문자열의 길이%5 == 0이라면, 해당 문자열에 최소 하나의 "quack" 쌍이 있고
다음에 들어가야 할 문자가 'q'인 것을 알 수 있다.
이 원리를 이용하여 연속을 체크할 수 있다.
알고리즘의 총과정을 정리해 보면 이렇다.
1. String형 벡터를 만든다.
2. 입력 문자열을 처음부터 끝까지 하나씩 읽는다.
3. 'q'문자일 경우3 - 1 기존 문자열[i]%5 == 0 일 경우 그 문자열에 'q' 추가
3 - 2 아닐 경우 새로운 문자열 'q' 추가
4.다른 문자일 경우 문자열의 길이에 따른 매핑이 맞을 경우에만 문자열에 넣음
4-1 아닐 경우 fail 하고 -1 반환
2~4 과정을 끝까지 반복5. string 벡터의 길이가 답이 됨
이렇게 보면 무슨 말인지 정확히 모르겠으니까 문제 구현단계에서 천천히 살펴보자.
문제 구현 단계
vector<string> ducks;
bool Solution(char word, char key, int num){
if(word == key){
for(int i = 0; i < ducks.size(); i++){
if(ducks[i].length()%5 == num){
ducks[i].push_back(word);
return false;
}
}
}
if(word == 'q' && key =='q'){
ducks.push_back("q");
return false;
}
return true;
}해당 문자가 이 문자열에 들어갈 수 있는지 없는지 판단하는 Solution 함수이다.
매개변수로 입력받은 문자
word,
기준 문자 key,
기준 문자길이 num
이 입력된다.리
턴은 bool형인데 이는 해당 녹음소리가 적절한지 아닌지 판단하기 위해 세웠다.
key와 num은 코드의 가독성을 위해 추가한 변수인데, 이는 아래 코드에서 보도록 하겠다.
일단 당연히 입력받은 문자와 기준문자가 같을 때만 문자길이를 체크하는 작업을 한다.
벡터 안에 있는 모든 문자열을 순차탐색해서, 기준 문자길이 num과 같은 문자열이 있다면
그 문자열에 word를 추가하고 false를 반환한 후 끝낸다.
mod 5를 해주는 이유는 quack의 문자길이가 5이니까, 문자가 5씩 끊어지기 때문이다.
문자가 5씩 끊어지면, 연속된 울음으로 길이가 5가 넘게 돼서 num을 판단하기 어려워진다.
따라서 mod5 연산으로 무조건 0~4 값이 나오도록 했다.
만약 for문을 빠져나왔다는 것은 모든 문자열을 돌았는데 num과 일치하는 문자열이 없다는 것을 의미한다.
이는 해당 오리들로는 해당 소리를 표현할 수 없다는 소리이므로
아래처럼 해당 문자가 'q'일 때만 새로운 문자열을 벡터에 추가한다.
그렇지 않은 경우는 모두 true를 반환한다.
bool fail;
string str;
cin >> str;
for(int i = 0; i < str.length(); i++){
fail = true;
char word = str[i];
if(ducks.empty()){
if(word == 'q') {
ducks.push_back("q");
fail = false;
}
}
else{
fail &= Solution(word,'q',0);
fail &= Solution(word,'u',1);
fail &= Solution(word,'a',2);
fail &= Solution(word,'c',3);
fail &= Solution(word,'k',4);
}
if(fail) break;
}main 함수 부분에 해당하는 코드이다.
불가능한 상태인지 체크하는 fail을 사용한다.
fail이 true라면 불가능한 상태이기 때문에 출력 시 -1
false라면 가능한 상태이기 때문에 벡터의 사이즈를 출력해 준다.
입력받은 문자 str을 처음부터 순차탐색하는데
가장 처음에는 벡터가 비어있으므로 'q'가 들어오면 바로 문자열을 만들어준다.
그 이외의 경우는 아까 설명했던 Solution함수를 호출하는데,
매개변수로 문자와 매핑해 줬던 대로 문자와 길이를 적어준다.
여기서 fail &= Solution()이게 있는데 &는 AND 비트연산자이다.간단하게 말해서
하나라도 0이면 값이 0이 되는 연산이라는 뜻이다.
이걸 여기 적용시켜서 fail을 업데이트하는데 이 5개의 fail &= 뜻은
5개의 Solution() 반환값 중 하나라도 false라면 fail = false이다.
그리고 모든 반복의 끝에는 fail이 true가 될 시 즉시 그 반복문을 탈출한다.
아래는 전체 코드이다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> ducks;
bool Solution(char word, char key, int num){
if(word == key){
for(int i = 0; i < ducks.size(); i++){
if(ducks[i].length()%5 == num){
ducks[i].push_back(word);
return false;
}
}
}
if(word == 'q' && key =='q'){
ducks.push_back("q");
return false;
}
return true;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
bool fail;
string str;
cin >> str;
for(int i = 0; i < str.length(); i++){
fail = true;
char word = str[i];
if(ducks.empty()){
if(word == 'q') {
ducks.push_back("q");
fail = false;
}
}
else{
fail &= Solution(word,'q',0);
fail &= Solution(word,'u',1);
fail &= Solution(word,'a',2);
fail &= Solution(word,'c',3);
fail &= Solution(word,'k',4);
}
if(fail) break;
}
for(int i = 0; i < ducks.size(); i++){
if(ducks[i].length() % 5 != 0){
cout << "-1";
return 0;
}
}
if(fail) cout << "-1";
else cout << ducks.size();
}마지막에 반복문으로 한 번 더 문자열을 전부 체크해 주는 이유는
위에 것 만으로는 qqqqq 등, q만 들어올 때는 fail = true로 체크해 줄 수 없기 때문이다.
원래 정상적으로 작동했다면, 모든 작업이 끝났을 때는
모든 문자열은 quackquack, quack만 들어있야한다.
따라서 문자열의 길이는 5의 배수이다. 즉 mod5를 했을 때 무조건 0이 나와야 한다.
그렇지 않다는 것은 정상적인 결과가 아니라는 뜻이므로 -1을 반환한다.
시행착오
아이디어를 생각하는 건 쉬웠는데 구현하기가 까다로웠던 문제.
그리고 생각보다 예외케이스 처리하기가 힘들어서 오래 걸렸다.
확실히 구현이 약하다는 게 느껴지는 문제였다.
이렇게 구현문제를 좀 많이 풀어보자.