[알고리즘 풀이 분석] BOJ 12933 오리

nnnyeong·2022년 3월 22일
0

알고리즘 풀이분석

목록 보기
92/101

백만년만의 알고리즘.. 바닥난 집중력으론 실버 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;
}
profile
주니어 개발자까지 ☄️☄️

0개의 댓글