문제 출처
문제 출처 : 옹알이(2)
문제 이해하기
"aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음인 경우만 counting 해주고, 그 외 단어가 연속해서 나온다거나 네 가지 발음을 제외한 단어가 나온 경우는 counting 하지 않는다.
주요 조건 이해하기 ⭐️
문제를 이해하는건 굉장히 쉬웠다. 하지만 어떤 방법으로 풀어야 하는지에만 1시간 정도를 소비했고, 1시간이 지났음에도 풀이법이 생각나지 않았다.
우선 고민했었던 내용들을 나열해보면
이 문제를 읽고 가장 먼저 생각했던 내용은 '완전탐색'이였다.
뜬금없이 완전탐색이 나온 이유는 지문에 나와있는 단어 중 '조합'이라는 단어가 눈에 들어왔고 "aya", "ye", "woo", "ma" 네 가지 단어로 생성할 수 있는 단어들을 다 만들고 입력으로 들어온 babbling 배열을 하나씩 순회해서 맞는 경우만 체크하면 되지 않을까? 라는 생각을 했었다.
완전탐색 중 백트레킹 기법으로 시도하려고 했으나, 재귀적으로 호출할 때 종료조건이 명확하게 있어야 한다. 하지만 이 문제는 종료조건이 명확하게 있지 않아 재귀적으로 호출하기가 난감했다. (결국 이 방법은 패스)
그 다음으로 생각했던 내용은 contains 메소드를 사용하는 방법이였다.
babbling 원소를 하나씩 순회하면서 만약 "aya", "ye", "woo", "ma" 네 가지 발음중 하나라도 포함되어 있다면 babbling[i]에서 발음에 해당하는 부분만 삭제 시킨 후 남은 부분은 다시 순회하는 방식으로 처리하려고 했으나 String에서 재공해주는 delete와 관련된 기능들은 인덱스 기준으로 삭제하기 때문에 이 마저도 구현하기가 뭔가 애매했다. (그냥 구현력이 부족했다고 말해,,)
마지막으로 생각했던 방법은 알파벳 갯수만큼 int형 배열을 선언한 후 "aya", "ye", "woo", "ma" 네 가지 발음의 알파벳 하나하나를 카운팅한다.
babbling 배열을 순회하면서 babbling[i] 각각의 원소를 마찬가지로 알파벳 갯수만 카운팅하여 서로의 빈도수가 같다면 answer를 증가시켜주는 로직이다.
하지만 이 경우도 반례가 존재하기 때문에 결국 실패했다
"aya" -> a = 2, y = 1
"yaa" -> a = 2, y = 1
결국 풀지 못하고 다른 사람의 풀이를 참조하였다.
너무 어렵게 고민해서 그런지, 다른 사람의 풀이가 굉장히 쉽게 다가왔다.
- 먼저 연속된 발음이 있는지 체크하는 if문을 만들어준다.
- 연속된 발음이 아닌 경우에서 발음이 가능한 단어들은 " " 공백으로 만들어준다.
- 마지막으로 " "로 만들어준 원소들을 ""로 바꿔준다
- ""로 바꿔준 원소들은 길이가 0이기 때문에 0인 값들만 counting 해준다.
여기서 " " 공백과 "" 빈문자열로 구분지어서 만들어주는 이유는 만약 공백이 아니라 빈문자열로 바로 치환시킬 경우 남은 양옆의 글자들이 서로 붙어버려서 엉뚱한 값이 삭제될 수 있다.
예를 들어 "ymae" 이라는 문자열이 있을 때
replace("ma", "") 치환할 경우
"ymae" -> "ye"로 변경되어 발음이 가능한 단어가 되어버린다.
하지만 replace("ma", " ") 이렇게 하면
"ymae" -> "y e" 이렇게 되서 이 다음에 "ye" 를 체크할 때 제외된다.
제출 코드
class Solution {
public int solution(String[] babbling) {
int answer = 0;
for (int i = 0; i < babbling.length; i++) {
if(babbling[i].contains("ayaaya") || babbling[i].contains("yeye") || babbling[i].contains("woowoo") || babbling[i].contains("mama")) {
continue;
}
babbling[i] = babbling[i].replace("aya", " ");
babbling[i] = babbling[i].replace("ye", " ");
babbling[i] = babbling[i].replace("woo", " ");
babbling[i] = babbling[i].replace("ma", " ");
babbling[i] = babbling[i].replace(" ", "");
if (babbling[i].length() == 0) {
answer++;
}
}
return answer;
}
}