프로그래머스-옹알이 (1)-120956

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/120956

*본 게시물은 비상업적,비영리적 용도로 작성하였습니다.

문제 설명

이 문제는 "aya", "ye", "woo", "ma" 발음을 최대 한번씩 조합해 발음할 수 있는 아기가 주어진 배열(babbling)의 단어를 사용할 수 있는지 물어보는 문제이다.

내가 푼 방식

StringBuilder를 이용했다.

String은 불변객체이기때문에 변경이 불가능하므로
각 문자열의 내용을 변경할 수 있는 StringBuilder를 활용했다.

1.첫번째 시도 [실패]

문자열 wyeoo 케이스에서 실패했다.
원래는 각 문자열 케이스마다 아기가 말할 수 있는 단어를 모두 비교했고
해당 단어가 문자열 케이스에 존재하면 제거를 했다.
결과적으로 내용이 비어있으면 말할 수 있는 단어로만 구성되었다고 판단했다.

ex)
사용가능한 언어 : { "aya", "ye", "woo", "ma" }

wyeoo -> ye가 존재하는가? yes!! 좋아 그럼 해당 부분을 remove!
woo -> woo가 존재하는가? yes!! 좋아 그럼 이 단어는 가능해!

하지만, 추가된 요구사항을 보면 중간에 있는 단어를 없애는 등의 처리는 인정하지 않는다고 하였다 ㅠㅠ.

2.두번째 시도 [성공]

이번에는 중간의 단어를 제거하는게 아니라
무조건 처음 시작하는 단어만 매칭이 되면 삭제하는 방법을 고려했고
아래와 같은 코드를 작성해 테스트를 통과했다.

class Solution {
    
    public int solution(String[] babbling) {
        
        String[] words = new String[] {"aya" , "ye" , "woo" , "ma"} ; 
        int answer = 0;
        
        for(String str : babbling) {           
            if(isSpeakableWord(words, str)) {
                answer += 1 ; 
            }      
        }             
        
        return answer;
    }
    
    
    public boolean isSpeakableWord(String[] words , String str) {
        
        StringBuilder sb = new StringBuilder(str); 
        
        //비교하려는 단어 횟수만큼 반복문 시도 (여기서는 4개가 고정되어있음)
        //words = {"aya" , "ye" , "woo" , "ma" }
        for(int i = 0 ; i<words.length; i++) {  
			
            //내부 반복문이 한번 더 실행 (여기서도 4개가 고정되어있음)
            //이중 반복문이지만 테스트 개수가 적어 완전탐색을 이용

			for(String word : words) { 

				//해당 문자열이 존재하는지 체크 
                int index = sb.indexOf(word); 
                
                //★문자열이 처음 위치해야만 삭제하도록 했음
                if(index == 0) {
                    sb.delete(0 , word.length()); 
                }
            }
        }
        
        return sb.length() == 0 ? true : false; 
    }
    
}

GPT에게 코드리뷰 요청하기

위 해결방식을 좀 더 최적화하고 싶어 GPT에게 이런 요청을 보냈다.

위 코드를 시니어개발자 관점에서 코드리뷰를 해줘
그리고 최적화된 방법이 있다면 이를 설명해줘

그랬더니 아래와 같은 소스코드와 개선점을 출력해주었다.

[개선된 코드]

private boolean isSpeakableWord(String[] words, String str) {
    Set<String> speakableWords = new HashSet<>(Arrays.asList(words));
    StringBuilder sb = new StringBuilder(str);

    int index = 0;
    while (index < sb.length()) {
        boolean found = false;
        for (String word : speakableWords) {
            if (sb.substring(index).startsWith(word)) {
                sb.delete(index, index + word.length());
                found = true;
                break;
            }
        }
        if (!found) {
            index++;
        }
    }

    return sb.length() == 0;
}

[궁금증 및 배운점]

Q) 왜 HashSet을 사용해서 String[] 배열을 HashSet으로 만든거지?

A)
(1) HashSet자료형은 배열과 달리 중복을 제거하고(Set) 빠른 검색을 가능하게 한다(Hash).
(2) 데이터가 중복이 없음을 가시적으로 보여줄 수 있다.
(3) 집합 계산이 가능하다.

[집합계산 코드 예]

Set<Integer> set1 = new HashSet<>();
set1.add(1); // ..add(2) ..add(3)   // set1 = {1,2,3}  

Set<Integer> set2 = new HashSet<>(); 
set2.add(3); // ..add(4) ..add(5)   // set2 = {3,4,5} 

//교집합 계산하기 
Set<Integer> intersection = new HashSet<>(set1); 
intersection.retainAll(set2); // {3}만 남아 출력 (retainAll : 교집합)

.. addAll은 합집합으로 {1,2,3,4,5}
.. removeAll은 차집합으로 {1,2} 출력 

DB에서도 union , intersect , minus 연산으로 데이터 집합을 집합연산할 수 있는데 자바에서도 이를 가능하게 하는 연산이 있다는 점이 새로웠다.

소스 코드를 분석해보니 startWith와 substring이 눈에 띄었다.

int index = 0;

while (index < sb.length()) {
    
    boolean found = false;
    
    //while( 0 < 5 ) 
    //예) wyeoo 일 경우 
    //sb.substring(0).startWith("aya") ? 아니다! 다음반복
    //sb.substring(0).startWith("ye") ?  아니다! 다음반복
    //sb.substring(0).startWith("woo") ?  아니다! 다음반복
    //sb.substring(0).startWith("ma") ? 아니다! 반복끝 
    //found 가 false 이므로 !found 는 true , index++ 처리가 된다.
	
    //while (1 < 5)
    //예) wyeoo 일 경우     
    //sb.substring(1).startWith("aya") ? 아니다! 다음반복
    //sb.substring(1).startWith("ye") ?  맞다!! found = true

	//while(1 <5) 
    //★여기서 처음부터 찾는게 아니라 문자열 처리를 한 
    //  그다음 시점부터 비교를 한다. 

	//예) woo 일 경우 
    //sb.substring(1).startWith("woo") ?  아니다! 다음반복
    //sb.substring(1).startWith("ma") ? 아니다! 다음반복 
    //sb.substring(1).startWith("woo") ?  아니다! 다음반복
    //sb.substring(1).startWith("ma") ? 아니다! 다음반복 
    
    
    for (String word : speakableWords) {
        if (sb.substring(index).startsWith(word)) {
            sb.delete(index, index + word.length());
            found = true;
            break;
        }
    }
    if (!found) {
        index++;
    }
}

이 부분은 잘 기억해놓고 써먹어야겠다.
처음부터 다시 비교를 하는게 아니라
처리한 시점의 인덱스부터 다시 비교를 하는 방식을 기억해놓아야겠다.

3. 다른 사람의 풀이

다음과 같이 문제를 풀이하신 분들이 있었다.

class Solution {
    public int solution(String[] babbling) {
        int answer = 0;
        for(int i=0; i<babbling.length; i++){
            if(babbling[i].matches("^(aya(?!aya)|ye(?!ye)|woo(?!woo)|ma(?!ma))+$")){
                answer++;
            }
        }
        return answer;
    }
}

와..정규식을 사용한다는 아이디어를 정말 참신한 것 같다.
^(aya(?!aya)|ye(?!ye)|woo(?!woo)|ma(?!ma))+$

정규식을 분석해보면
^는 정규식의 시작
aya(?!aya) 는 aya를 매칭하되 그 뒤에는 aya가 아닐경우만 매칭 (ayabb 등 가능)
이를 | 연산으로 케이스를 지정하고
+기호는 이전 패턴이 한 번 이상 반복됨을 의미한다.(만약 +가 없으면 aya만 매칭됨)
$는 정규식의 끝을 의미

문제를 푸는 데 있어 새로운 시각으로 풀이하는 것을 보면 정말 신기하고 대단한 것 같다.
앞으로도 더 정진해야겠다!