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

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

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력

s - 임의의 문자열

 

출력

result - 분리되지 않은 문자열의 첫문자와 나머지 문자의 개수가 같을 때 분리된 문자열의 수

 

제한사항

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

풀이

이 문제는 어떻게 푸는 지 보다도 어떻게 구현하는지 고민하는 문제였다. 어떻게 하면 가시성 있게 결과를 낼 수 있을까 고민했다. 먼저 첫글자와 횟수를 담는 공간을 어떤 자료형을 사용해서 구현할지 고민했다. Map을 사용하니 키 값에 name이 들어가지 않았다. 자동으로 변수로 지정돼서 undefined가 나와서 그런 거 같았다. 그래서 Map과의 객체의 조건을 생각해 보았다.

 

객체는 프로토타입 체인이 있고, 키는 반드시 문자열과 심볼, 그리고 프로퍼티 순서가 보장되어 있지 않다 등의 단점이 있다. 이게 문제에서 거슬리는 조건인가 생각해봤더니 아니었다. 그래서 객체를 사용하여 첫글자와 횟수를 담았고. 이해하기 쉽도록 나머지 수를 담는 공간 역시 객체로 나타냈다.

 

문자열을 최소한 한 번 순회해야 해서 for ...of문을 활용하였다. 인덱스가 쓰이지 않을 줄 알았다. for...of문을 활용해서 블록을 만들고 첫글자와 횟수를 담는 공간에 값이 없다면 첫글자를 새로 갱신하고 그 다음부터는 첫글자와 나머지 글자의 횟수를 차례대로 세어 첫글자 횟수와 나머지 글자 횟수가 같으면 분리된 문자열의 수 result를 1 증가시켰다. (코드에서는 answer로 표기하였다.) 

이렇게 코드를 짜니 실패하는 케이스가 떴다.

 

마지막 남은 글자를 고려하지 않았다. 마지막의 분리된 문자열에서 첫글자의 횟수와 나머지 횟수가 같지 않은 상태에서 끝난다면 분리된 문자열의 횟수를 1 증가시켜야 했다. 따라서 인덱스를 다루는 for문으로 바꾸고 첫 if문과 마지막 if 문에 새로운 조건을 추가시켜 마무리했다. 

 

시간 복잡도는 문자열 s를 한 번 순회하므로 O(n)이다.

공간 복잡도는 답을 담는 변수, 첫글자와 횟수 담는 객체, 나머지 수를 담는 객체, 문자열 s이므로 O(n) 문자열의 크기이다.

코드

function solution(s) {
    var answer = 0;
    const first = {name:'', count: 0};
    const rest = {count: 0};
    
    for (let i=0; i<s.length; i++) {
        if (!first.name && i!==s.length-1) {
            first.name = s[i];
            first.count = 1;
            continue;
        }
        if (first.name===s[i]) first.count++;
        else rest.count++;
        if (first.count===rest.count){
            answer++;
            first.name = '';
            first.count = 0;
            rest.count = 0;
        } else if (i === s.length -1) {
            answer++;
        }
    }
    return answer;
}

 

 

다른 사람의 방법으로 보니 count를 +1, -1 이런 식으로 만들어 코드를 최소화시켰다. 좋은 방법이다. 연습해 봐야겠다.