Today I Learned

처음 푼 투 포인터 문제! <문자열 나누기>

지난 번(이라기엔 이제 좀 많이 지났지만) 알고리즘 스터디 토픽 중에 투 포인터가 있었다. 그 때 지노님 발표를 열심히 듣긴 했지만 실제로 문제를 풀어보진 않았고, 어쩌다보니 완전탐색 같은 문제만 많이 풀게 되었는데 오늘 아침 알고리즘 스터디에서 잠 덜 깬 눈으로 고른 문제가 투 포인터였다. 풀 자신이 없어 못 본 척 할까 하다가 그래도 맛이나 보자 하고 풀어봤는데 의외로 어렵지 않게 풀려서 기뻤다. 사실 요즘 과제에 너무 치여서 알고리즘을 거의 못 건드렸고, 안 풀다 보니 못 풀게 되어서 좀 걱정하던 차에 좋은 문제를 만났다. 그래서 공유한다!

문제와 설명은 아래 이미지와 같다.

알고리즘 문제를 풀다 보면 종종 문제 설명이 필요 이상으로 복잡한 경우를 종종 보게되는데, 아마 내 문해능력이 떨어지는 탓이겠지만 아무튼 그런 문제는 풀 의욕이 사라져 버린다. 그런 점에서 이 문제는 얼핏 어렵게 설명하는 듯 하면서도 읽어보면 나름 뭘 하라는 건지 알 것 같은 좋은 문제라고 생각한다.

투 포인터의 꼴을 찾았는가?

얼마 안 가 깨어질 섣부른 일반화이지만, 이 문제의 뉘앙스에서 투 포인터의 뉘앙스를 읽을 수 있는 부분이 있다.

1. 뭔가 하나를 잡아두고 다른 것들과 비교한다. -> 글자 x
2. 어떤 조건을 만족하면 잡아둔 것을 놓고 다른 것을 잡는다. -> 두 횟수가 같아지고 남은 부분에 반복한다.

나같은 경우 이런 단서를 발견하고 바로 투 포인터의 풀이법을 대입해서 문제를 풀었다. 풀이는 아래와 같다.

function solution(s) {
    let countIdentical = 0;
    let countDifferent = 0;
    let countSubString = 0;
    let left = 0;
    let right = 0;
    
    while(left < s.length) {
        if (s[left] === s[right] ){
            countIdentical++;
        } else {
            countDifferent++;
        }
        if(countIdentical === countDifferent || right === s.length) {
            left = right + 1;
            right = left;
            countIdentical = 0;
            countDifferent = 0;
            countSubString++;
            continue;
        }
        right++;
    }
    
    return countSubString;
}

left 와 right 라고 쓴 부분은 다시 보니 조금 안 맞는 네이밍인 것 같다. 처음부터 시작해서 끝까지 비교하는 거니까 start 와 end 정도로 쓰면 괜찮겠다.

문제를 보자마자 문제 유형부터 보는 게 맞는 방식인가?

헌데 이렇게 풀어보니 수능 수학문제를 풀던 기억이 퍼뜩 떠올랐다. 문제 유형 분석에 급급하다가 정작 문제를 놓치는 경우가 많았다. 오늘처럼 문제를 보자마자 문제 유형부터 찾으려고 하지 말고 일단 문제를 자세히 들여다 보는 편이 좋겠다.

Links

• 문자열 나누기