[프로그래머스 / kotlin] 문자열 나누기 / Queue 활용

문제 설명

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.
먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.
문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

 

입출력 예

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

 

 

처음 시도

처음엔 문제에서 힌트를 못 읽고 문제가 하라는 대로... 조건 하나하나 비교하고 문자열 자르고 다시 조건 확인하는 방식대로 했다.

아래와 같음.

이렇게 풀면서도 다른 방법이 있을 거 같았는데 뭘 써야할지 감이 안 왔다...

class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0
        var temp = s
        
        if(temp.length == 1) return 1
        
        while(temp.length > 0) {
            val x = temp[0]
            var sameCount = 0
            var notSameCount = 0
            
            for(i in 0 until temp.length) {
                if(temp[i] == x) sameCount++
                else notSameCount++
                
                if(sameCount == notSameCount) {
                    answer++
                    temp = temp.slice(i+1 until temp.length)
                    break
                }
                if(sameCount + notSameCount == temp.length) return answer + 1
                if(i == temp.length - 1) {
                    temp = temp.slice(1 until temp.length)
                }
            }
            if(temp.length == 1){
                answer++
                break
            }
        }
        
        return answer
    }
}

 

최종 코드

다른 사람 풀이를 보니 Queue를 활용해서 아래처럼 코드를 간단히 짤 수 있었다.

이 문제 어디서 Queue에 대한 힌트를 찾을 수 있는지 고민했는데

"왼쪽부터 오른쪽으로 읽음"+"조건 만족 시 문자열 자르고 그 뒤부터 시작"<이게 FIFO를 연상시켜서 Queue로 이어지는 가장 큰 힌트인 거 같았다...

import java.util.*

class Solution {
    fun solution(s: String): Int {
        var answer: Int = 0
        val q = LinkedList<Char>()
        
        s.forEach {
            if(q.isEmpty()) {
                answer++
                q.push(it)
            } else if(q.peek() == it) {
                q.push(it)
            } else q.pop()
        }
        
        return answer
    }
}

 

문제 많이 풀어봤다고 생각했는데, 문제 읽고 1차원적으로 짜는 게 아닌 문제 속에 숨겨진 힌트 찾는 건 아직 부족한 거 같다. 더 많이 풀어보자..아자!!