[프로그래머스] Lv.0 옹알이(1)

유지연·2023년 4월 27일

PS

목록 보기

13/16

✍ 문제

머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.

✍ 제한 설명

1 ≤ babbling의 길이 ≤ 100
1 ≤ babbling[i]의 길이 ≤ 15
babbling의 각 문자열에서 "aya", "ye", "woo", "ma"는 각각 최대 한 번씩만 등장합니다.
즉, 각 문자열의 가능한 모든 부분 문자열 중에서 "aya", "ye", "woo", "ma"가 한 번씩만 등장합니다.
문자열은 알파벳 소문자로만 이루어져 있습니다.

✍ 입출력 예시

babbling	result
["aya", "yee", "u", "maa", "wyeoo"]	3
["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]	3

✅ 코드

❗ vector, string 사용 C++ 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(vector<string> babbling) {
    
    int answer = 0;
    vector<string> can_speak = {"aya", "ye", "woo", "ma"};
    int size = babbling.size();
    
    for (int i=0; i < size; i++) { //입력값에 따른 반복
        
        string check = babbling[i];
        
        for (int j=0; j<4; j++) {
            int fail = 0;
            size_t nPos;
            for (int k=0; k < can_speak.size(); k++) {
                nPos = check.find(can_speak[k]);
                if (nPos == 0 ) { //문자열이 있는 경우
                    check = check.substr(can_speak[k].length());
                    can_speak.erase(can_speak.begin()+k);
                    break;
                }
                if (k == (can_speak.size()-1) && nPos != 0) fail = 1;
            }
            if (fail == 1) break;
            if (check.length() == 0 ) {
                answer += 1;
                break;
            }
        }
        can_speak = {"aya", "ye", "woo", "ma"};
    }
    return answer;
}

✅ 코드풀이

위 문제는 vector와 string의 멤버 함수를 적절히 이용하면 되는 문제이다. 주어지는 string에 대해 그것이 "aya", "ye", "woo", "ma" 네 가지 문자열의 조합으로 만들어 질 수 있는 지 판단하면 된다. 이 때 주의해야 할 점은 네 문자열이 최대 한 번씩만 나올 수 있다는 것이다.

❗ 알고리즘

babbling[i]에 해당하는 문자열이 주어진 네 가지의 문자열의 조합으로 만들어 질 수 있는 것인지 판단하기 위해 옹알이가 가능한 "aya", "ye", "woo", "ma"를 원소로 하는 can_speak라는 벡터를 생성하였다. 반복문을 통해 can_speak 벡터의 원소를 check 문자열에서 찾을 수 있는지를 확인한다.
이 때, string의 멤버함수인 find를 사용하였다.

❗ string.find( )

string 클래스의 멤버함수인 find는 인자로 받은 것이 string에 포함되어 있다면 해당 부분의 가장 첫번째 index값을 반환해주는 함수이다.

int result
size_t nPos
string name = "jiyeonyoo";
result = name.find("yoo");
nPos= name.find("abc");

위 코드 상의 3번째 line에서는 "jiyeonyoo"라는 string에서 "yoo"를 찾고있으므로 두 번째 y의 index 값인 6을 반환할 것이다. 하지만 만약 find 함수의 인자가 string에 포함되어 있지 않는다면 어떻게 될까?

보통 찾고자하는 문자열이 없을 경우 -1이 반환된다고 생각하지만, 이 경우에는 -1이 아닌 엄청 큰 값의 쓰레기 값이 반환된다. nPos의 자료형을 size_t로 둔 것도 이러한 이유 때문이다. 만약 int 자료형에 찾고자 하는 문자열이 없는 find 함수의 반환값을 저장하려고 한다면 런타임 에러가 발생할 수 있으니 주의하자!

이 문제에서 옹알이가 될 수 있는 문자열 속에는 "aya", "ye", "woo", "ma" 이외의 다른 문자가 나올 수 없기 때문에 만약 4가지 중 어떤 문자열이 포함이 되어 있는 경우, find 함수의 반환값은 반드시 0이 되어야 한다. 만약 can_speak의 모든 문자열을 find 했는데도 nPos가 0이 아닌 경우 그 즉시 반복문을 break하여 다음 babbling 값으로 넘어가도록 하였다. (이를 컨트롤 하는 변수로 fail을 두었다.)

❗ string.substr( )

위의 find 함수를 통해 can_speak 벡터의 원소 값이 포함되어 있는 경우, 반드시 nPos의 값이 0이 되어야 함을 설명하였다. 이 논리가 성립이 되려면 can_speak의 원소를 find 한 후, 그 원소를 해당 문자열에서 삭제시키는 과정을 추가해야 한다. 이것을 위해 string의 멤버 함수인 substr을 이용하였다.

string name = "sonny";
result1 = name.substr( );   //result1 = "sonny"
result2 = name.substr(2);   //result2 = "nny"
result3 = name.substr(1,4); //result3 = "onny"

인자가 없는 경우 str.substr( ) : 문자열 전체 반환
인자가 한 개인 경우 str.substr(n) : n번째 index부터 끝까지의 부분 문자열 반환
인자가 두 개인 경우 str.substr(n, k) : n번째 index부터 k개의 문자로 된 부분 문자열 반환

첫 번재로 find 함수를 통해 check 문자열에서 can_speak의 원소를 찾은 경우 해당 부분의 index값은 0이 되고, 그 부분의 길이는 can_speak[k].length()이다. 따라서 index 0 ~ can_speak[k].lenth()-1 까지를 삭제해야 하므로 check = check.substr(can_speak[k].length()) 가 된다.

따라서 check 문자열에서 can_speak의 원소를 찾을 때마다 그 부분을 삭제시켜 주기 때문에, find 함수를 통해 can_speak의 원소를 찾은 경우 그 반환 값은 0이 되야 하는 것이다.

❗ vector.erase( )

이제 거의 완성되었다! 우리가 아직 만족시키지 못한 조건은 "aya", "ye", "woo", "ma"가 주어진 문자열에서 최대 한 번씩만 나올 수 있다는 것이다. 이 조건을 만족시키기 위해 can_speak의 원소값이 find 함수를 통해 포함되어 있음을 확인한 경우, can_speak 벡터에서 해당 원소를 삭제시켜야 한다. 이를 위해 vector의 멤버함수인 erase를 사용하였다.

주어진 문자열에서 can_speak의 원소가 포함되어 있는지 확인

→ 포함되어 있는 경우

문자열에서 해당 부분을 삭제
can_speak에서 find에 인자에 해당했던 원소를 삭제

처음 옹알이가 가능하다고 주어진 문자열이 4개이므로 4가지 문자열이 다 나오는 경우가 가장 최대이다. 따라서 위 과정을 최대 4번 반복하고, 각 반복마다 can_speak의 크기만큼 이중 반복문이 들어간다. (글로 설명하니 너무 복잡해보이지만 이해하면 매우 간단하다ㅠㅠ 나의 필력... 지못미)

위 과정을 반복하면서 주어진 check 문자열의 길이가 0이 되면 그 문자열은 옹알이가 가능한 문자열이므로 answer 값을 1 증가시킨다.

마지막으로 중요한 것은 우리가 하나의 babbling[i] 문자열을 체크하면서 can_speak의 원소값을 삭제하는 경우가 있으므로 다음 babbling[i+1]의 문자열로 넘어가기 전에 이를 원상복구 시켜주어야 한다. 따라서 j, k를 이용한 이중반복문 바깥에 can_speak = {"aya", "ye", "woo", "ma"} 를 넣어주어야 완벽하게 끝이난다!

문제 풀면서 공개된 테스트케이스에 대해서는 통과를 하는데 계속 성공률이 50%도 못미쳐서 내가 미쳐갈 때 즈음 바보같은 실수를 발견하고 겨우겨우 끝마칠 수 있었따...😩 can_speak를 원상복구 시키는 코드의 위치를 이상한 곳에 해놓았었음 ㅎㅎ 그리구 velog 올릴 때마다 느끼는 건데 내 머리속에 정리된 알고리즘을 글로 잘 설명하는게 굉장히 어려운 것 같다. 공부 할 수록 느끼는 것이지만 아직도 개선해야 할 점이 한 두개가 아니다 !! 그래도 차근차근 나아지고 있으리라 믿고 있다 💪

계속 백준에서만 풀다가 오랜만에 프로그래머스에서 해보았는데 문제집이나 풀이 환경이 훨씬 잘 만들어져 있어서 앞으로는 프로그래머스도 활발하게 사용할 것 같다. 각잡고 코테 준비하기에는 프로그래머스가 훨씬 좋은 듯? (~~지극히 제 개인적인 생각입니다~~)

벌써 4월도 다 지나가고 있는데 뭐가 됐든 더 열심히 해야겠다는 생각이 든다!! 빠이팅!!