[프로그래머스/자바] 옹알이 (1) - 두 가지 풀이 방식

[프로그래머스/자바] 옹알이 (1) - 두 가지 풀이 방식

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/120956

 

 

 

 

📌 문제 

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

 

 

⚔ 제한 사항

입출력 예 설명

입출력 예 #1["aya", "yee", "u", "maa", "wyeoo"]에서 발음할 수 있는 것은 "aya"뿐입니다. 따라서 1을 return합니다.입출력 예 #2["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]에서 발음할 수 있는 것은 "aya" + "ye" = "ayaye", "ye", "ye" + "ma" + "woo" = "yemawoo"로 3개입니다. 따라서 3을 return합니다.


유의사항

네 가지를 붙여 만들 수 있는 발음 이외에는 어떤 발음도 할 수 없는 것으로 규정합니다. 예를 들어 "woowo"는 "woo"는 발음할 수 있지만 "wo"를 발음할 수 없기 때문에 할 수 없는 발음입니다.

 

 

---

 

💡 풀이 과정 

 

 

코딩 테스트 입문 문제로 문제 자체가 엄청 복잡하거나 어려운 문제는 아니다. 하지만 입문 섹션에서 가장 마지막에 위치한 문제이고 정답률이 낮았다.

 

1년 전쯤 도전했던 기억이 난다. 그때 반복문을 엄청 비벼가면서 풀어보려고 했는데 안풀려서 중간에 포기했던 기억이... 

 

 

문제의 요구 사항에 따라 제시된 문자열과 입력된 문자열을 비교하는 로직을 구현해주는 것이 핵심이다.

 

입력 부분을 받는 부분을 구현하면 다음과 같다. 

 

for (String word : babbling) {
      if (isValidWord(word)) {
            count++;
      }

 

친절하게 입력이 String배열로 주어지므로 배열의 원소를 순회하면서 검증 함수에 던져주고 검증 함수가 true이면 정답을 올려주면 된다. 

 

검증 함수는 어떻게 구현 하면 될까? 

 

첫 번째로 단순하게 생각해볼 수 있는 부분은, 단순 일치 여부를 체크하는 것이다. 

 

private boolean isValidWord(String word) {
   String[] validSounds = {"aya", "ye", "woo", "ma"};
   for (String sound : validSounds) {
      if (word.contains(sound)) {
         word = word.replaceFirst(sound, "");
      }
   }
   return word.isEmpty();
}

 

 

가능한 문자열에 대해서 주어진 문자열과 하나씩 비교해가면서 만약에 해당하는 문자열을 포함하고 있다면 replaceFirst 함수를 통해 해당 문자열 제거한다. 

 

즉, 주어진 문자열에서 유효한 발음이 있는지를 체크하고, 발견되면 그 부분을 공백으로 치환한다. 이렇게 하여 모든 유효한 발음을 찾아 제거한 후에, 최종적으로 남은 문자열이 비어있다면, 입력된 문자열은 유효한 조합으로만 이루어진 것으로 간주하는 것이다. 만약에 남은 문자열이 비어있지 않다면, 그것은 유효한 발음 이외의 다른 문자가 포함되어 있다는 것을 의미하며, 이는 주어진 문제의 요구사항을 충족하지 않는 것으로 판단하면 된다.

 

문제는 다음과 같은 입력이 주어지는 경우 정답이 1인데 2를 리턴하게 된다. 왜냐하면 "wyeoo" 때문이다. 

	["aya", "yee", "u", "maa", "wyeoo"]

 

구현된 코드에 따르면 

wyeoo

역시 정답이 된다.

 

왜냐면 "ye"를 돌면서 해당 부분이 ""로 치환되어 "woo"가 되고, 바로 다음에 "woo"가 나오면서 또 일치하게 되어 valid 한 것으로 판단되기 때문이다.

 

따라서 이 알고리즘은 이러한 예외케이스를 잡아내지 못하므로 완전하지 못한 알고리즘으로 실패한다. 

 

어떻게 고쳐야 할까? 

 

두 가지 방법의 다른 풀이가 있다. 

 

 

 

1. 첫 글자부터 판단하면서 일치여부를 판단하고, 그 다음 문자열에 대해서 재귀적으로 탐색하기 

 

먼저 코드는 다음과 같다. 

 

private boolean isValidWord(String word) {
   String[] validSounds = {"aya", "ye", "woo", "ma"};
   return checkWord(word, validSounds);
}

private boolean checkWord(String word, String[] validSounds) {
   if (word.isEmpty()) {
      return true;
   }

   for (String sound : validSounds) {
      if (word.startsWith(sound)) {
         return checkWord(word.substring(sound.length()), validSounds);
      }
   }

   return false;
}

 

 

각 발음이 문자열의 시작 부분에서부터 일치하는지를 확인한다. 문자열이 주어진 발음으로 시작하는지 확인하고, 만약 시작한다면 해당 발음을 문자열에서 제거한 후 나머지 부분에 대해 같은 검사를 재귀적으로 수행하므로 놓치는 부분 없이 모두 탐색할 수 있다. 각 발음을 문자열의 시작 부분에서부터 차례대로 확인하기 때문에, 중간만 맞거나, 앞에는 맞는데 뒤에는 틀린 경우 등의 정답이 아닌 케이스들을 걸러낼 수 있다.

 

 

2. 공백으로 치환하지 않고 "-"로 치환하기 

 

두 번째 방식은 조금 다르게 접근해보는 것이다. 

 

무슨 말인지 조금 의아할 수 있다. 약간 아이디어가 적용된 풀이이다.

 

private boolean isValidWord(String word) {
   String[] validSounds = {"aya", "ye", "woo", "ma"};
   for (String sound : validSounds) {
      word = word.replaceFirst(sound, "-");
   }
   return word.replaceAll("-", "").isEmpty();
}

 

 

단순하게 생각해서 앞에서 문제가 되었던 케이스를 생각해보자. 중간의 단어를 포착하고 ""로 치환하면서 생성한 문자가 또 match 되면서 정답으로 카운트 되는 것이 문제였다. 그렇다면 그 오류를 해결해주는 것이다. 

 

문자열에서 유효한 발음을 찾은 경우, 그 부분을 공백 대신 `"-"`로 치환한다. 모든 유효한 발음에 대해 이 치환 과정을 수행한 후, 최종적으로 문자열에서 `"-"`를 제외한 나머지 부분이 완전히 비어 있는지를 확인한다. 

이 방법의 핵심은 유효한 발음을 제거한 후에도 문자열의 구조를 유지하여, 각 발음이 문자열 내에서 어떻게 위치하는지를 파악하는 데 있다. 예를 들어, "yee"라는 문자열의 경우, "ye" 발음을 찾아 "-"로 치환하면 "-e"가 되고, 이후에 남은 "e"는 유효한 발음이 아니므로 최종 문자열은 비어 있지 않게 되는 것이다. 따라서 이"yee"가 유효한 발음의 조합이 아니라는 것을 알 수 있다.

 

문자열에 중복된 발음이 포함되어 있는 경우를 생각해 보자. "wyeoo" 문자열에서 "ye" 발음을 찾아 "-"로 치환하면 "w-oo"가 된다. 따라서 그 다음 탐색에서 "woo" 와 matching에 실패하므로 정답으로 카운트 되지 않는다. 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/120956

프로그래머스