[프로그래머스/Java] 문자열 나누기

문제 설명

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

프로그래머스

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

• 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
• 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
• s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
• 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.

문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

제한 사항

• 1 ≤ s의 길이 ≤ 10,000
• s는 영어 소문자로만 이루어져 있습니다.

입출력 예

s	result
"banana"	3
"abracadabra"	6
"aaabbaccccabba"	3

입출력 예 설명

입출력 예 #1

• s = "banana"인 경우 ba - na - na와 같이 분해됩니다.

입출력 예 #2

• s = "abracadabra"인 경우 ab - ra - ca - da - br - a와 같이 분해됩니다.

입출력 예 #3

• s = "aaabbaccccabba"인 경우 aaabbacc - ccab - ba와 같이 분해됩니다.

 

내가 작성한 코드

class Solution {
    public int solution(String s) {
        // 분해한 문자열 개수
        int answer = 0;
        
        // 첫 번째 문자와 같은 문자 개수, 다른 문자 개수
        int same = 0, diff = 0;
        // 가장 첫 번째 문자
        char first = s.charAt(0);
        
        // 문자열 확인
        for (int i = 0; i < s.length(); i++) {
            // 문자가 첫 번째 문자와 같을 경우 same 1 증가
            if (s.charAt(i) == first) {
                same++;
            } else {  // 아닐 경우 diff 1 증가
                diff++;
            }
            
            // same과 diff가 같을 경우
            if (same == diff) {
                // answer 1 증가
                answer++;
                // 만약 i+1이 s의 길이보다 작을 경우
                if (i+1 < s.length()) {
                    // 가장 첫 번째 문자를 i+1번째 문자로 설정
                    first = s.charAt(i + 1);
                }
                // 초기화
                same = 0;
                diff = 0;
            }
        }
        
        // same 또는 diff가 0이 아닐 경우 answer 1 증가
        if (same != 0 || diff != 0) {
            answer++;
        }
        
        // 분해한 문자열 개수 반환
        return answer;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, 문자열을 일정한 규칙에 따라 나누는 문제라는 점을 파악했다. 단순히 임의로 잘라내는 것이 아니라, 첫 글자와 같은 문자의 개수와 다른 문자의 개수가 같아질 때 끊는 방식으로 분리해야 한다는 조건이 있었다. 따라서 단순히 substring으로 잘라서 확인하는 것보다는, 문자열을 앞에서부터 순차적으로 탐색하면서 같은 글자와 다른 글자의 개수를 카운트하는 방식이 더 효율적이라고 판단했다.

조건을 분석해 보면, 새로운 구간이 시작될 때 기준이 되는 문자를 하나 정해야 하고, 이후 문자를 탐색하면서 기준 문자와 같으면 same 카운트를, 다르면 diff 카운트를 증가시키면 된다. 그러다가 same과 diff가 같아지는 순간 하나의 구간이 완성되므로 문자열을 끊고, 그다음 문자부터 다시 새로운 기준을 세워 반복한다. 만약 탐색이 끝났는데 same과 diff가 아직 같지 않다면, 마지막 남은 부분도 하나의 구간으로 처리해야 한다.

이 과정을 구현하기 위해 문자열을 순차적으로 확인하는 반복문을 사용하고, 특정 위치의 문자를 확인할 때는 charAt() 메서드를 활용하는 것이 적절하다고 판단했다. 결국 전체 문자열을 한 번만 순회하면서 규칙대로 분리할 수 있기 때문에, 시간 복잡도는 O(n)으로 충분히 효율적인 풀이가 가능하다고 생각했다.