[알고리즘] 옹알이 2

// guidelines

1. Always include reasons for choosing certain approach/technology/framework/technique, etc.

2. Before writing a code, summarize the plan in 3 lines, including but not limited to:

- What data structures are we using?

- Time / Space complexity

- What are the edge cases?

 

3. Always leave reasons for failures to find patterns in mistakes. It is helpful in recognizing my weaknesses.

4. Don't cling to a problem that takes more than 30 minutes to solve. Check the answer first, and come back to days later.

  4-1. After you understood the answer, make it yours.

5. When you solved a problem without knowking how you did it, and it occurs repeatedly, it's time to take a step back and grind on one problem. 

Problem

머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ babbling의 길이 ≤ 1001 ≤ babbling[i]의 길이 ≤ 30문자열은 알파벳 소문자로만 이루어져 있습니다.

My Solution

class Solution {
    public int solution(String[] babbling) {
        int answer = 0;
        String[] possibles = {"aya", "ye", "woo", "ma"};
        for(String word : babbling) {
            if(canSpeak(possibles, word)) {
                answer++;
                System.out.println(word);   
            }
        }
        return answer;
    }
    
    private boolean canSpeak(String[] possibles, String word) {
        String recent="";
        StringBuilder sb = new StringBuilder(word);
        
        for (int i = 0; i < possibles.length; i++) {
            if(sb.indexOf(possibles[i]) == 0) {
                if(possibles[i].equals(recent)) {
                    return false;
                }
                sb.delete(0, possibles[i].length());
                recent = possibles[i];
                i = -1; // 옹알이 루프의 처음으로 돌아감
                if(sb.length() <= 0) {
                    return true; // 마지막까지 발음 가능하면 true 반환
                }
            }
        }
        
        return false; // 일치하는 게 없음
    }
}

 

키 아이디어

문자열의 앞(index 0)부터 greedy하게 발음 단위를 하나씩 매칭해 잘라내는 방식입니다. 4가지 발음을 순회하면서 현재 sb의 맨 앞과 일치하는 발음을 찾으면 잘라내고, 루프를 처음으로 되돌립니다(i = -1). 최종적으로 sb가 빈 문자열이 되면 발음 가능한 단어로 판정합니다.

장점

문자열을 앞에서부터 소비하는 방식이라 직관적이고, possibles 배열을 파라미터로 받아 확장성을 고려한 설계가 돋보입니다. StringBuilder를 사용해 문자열을 직접 수정하므로, 매번 새 String 객체를 생성하지 않습니다.

단점

i = -1 후 루프가 i++로 0이 되어 다시 처음부터 순회하는 구조라 의도를 파악하기 어렵습니다. sb를 직접 변이(mutate)시키기 때문에 함수 실행 중 중간 상태가 오염되면 디버깅이 어렵고, 발음이 매칭될 때마다 항상 possibles 4개를 처음부터 다시 순회하므로 불필요한 반복이 발생합니다.

자료구조

StringBuilder 하나로 입력 단어를 관리하고, String 배열로 발음 목록을 관리합니다. 별도의 복잡한 자료구조는 사용하지 않습니다.

시간 복잡도

• n = babbling 배열의 길이, L = 단어의 최대 길이, k = 발음 종류 수(4)
• 단어 하나에 대해: 발음 하나를 매칭할 때마다 k번 순회하고, 최대 L/min_len 번 매칭이 발생합니다.
• 전체: O(n × L × k), 제약조건 내에서는 사실상 O(1)에 가깝습니다.

공간 복잡도

각 단어마다 StringBuilder 하나를 생성하므로 **O(L)**입니다.

 

---

Example (Key Idea: )

class Solution {
    private static final String[] UNITS = {"aya", "ye", "woo", "ma"};

    public int solution(String[] babbling) {
        int answer = 0;
        for (String word : babbling) {
            if (canSpeak(word)) answer++;
        }
        return answer;
    }

    private boolean canSpeak(String word) {
        int idx = 0;
        String prev = "";
        while (idx < word.length()) {
            boolean matched = false;
            for (String unit : UNITS) {
                if (word.startsWith(unit, idx)) {
                    if (unit.equals(prev)) return false; // 연속 발음 금지
                    idx += unit.length();
                    prev = unit;
                    matched = true;
                    break;
                }
            }
            if (!matched) return false; // 매칭되는 발음 없음
        }
        return true;
    }
}

 

내 풀이 vs 최적 풀이 비교

항목	내 풀이	최적 풀이
핵심 방식	StringBuilder 직접 삭제 + i = -1 리셋	인덱스 포인터(idx) 전진
가독성	i = -1 트릭으로 직관성 떨어짐	while + break로 흐름이 명확
문자열 변이	있음 (sb 직접 수정)	없음 (원본 유지, 인덱스만 이동)
조기 종료	연속 발음 감지 시 즉시 return false	동일
시간 복잡도	O(n × L × k)	O(n × L × k)
공간 복잡도	O(L) - StringBuilder 생성	O(1) - 인덱스 변수만 사용

 

개선 사항

i = -1 대신 while 루프를 사용하세요. for문에서 i = -1로 인덱스를 리셋하는 방식은 작동은 하지만, 코드를 처음 보는 사람이 의도를 파악하기 어렵고 실수하기 쉽습니다. while (idx < word.length()) 구조로 바꾸면 "앞에서부터 소비한다"는 의도가 훨씬 명확해집니다.

StringBuilder 대신 인덱스 포인터를 사용하세요. 원본 문자열을 건드리지 않고 int idx만 앞으로 전진시키면, 공간 복잡도가 O(L) → O(1)로 줄고 코드도 더 간결해집니다. String.startsWith(prefix, offset) 메서드를 활용하면 indexOf 없이도 현재 위치에서 매칭 여부를 O(k_len)에 확인할 수 있습니다.

UNITS를 static final로 선언하세요. 현재는 canSpeak가 호출될 때마다 possibles 배열이 파라미터로 전달되지만, 이 문제에서는 발음 목록이 고정되어 있으므로 클래스 상수로 두는 것이 더 명확합니다.

---

Lessons Learned

 

하 어렵다. 이게 Lv1이라고??
인덱스 포인터를 사용하는 법은 처음 알았다. 길이만큼 전진하는 방식이 StingBuilder에서 일일이 삭제하는 방식보다 메모리 공간이 더 절약된다.
startsWith() 메서드도 처음 본 게 아닌데, 문자열 쪽 메서드를 더 공부해야겠다.
돌고돌아 기본이다.

 

My Github Repository for Solution Code

[level 1] Title: 옹알이 (2), Time: 2.21 ms, Memory: 78.9 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@54593e7

 

Problem Source

프로그래머스