SpecialStringAgain

[dlehdanakf]

Special String Again

• 문제 바로가기
• 해커랭크는 참 볼때마다 영어로 서론이 길어서 문제를 파악하기가 어렵다. 그래도 이 문제는 아래 두 조건만 보면 문제 풀이가 가능하므로 조금 수월했다 ㅋ
• 주어진 문자열 S에 대해 아래 조건을 만족하는 substring의 개수를 구하는 문제.
  • aaaa 같이 모든 문자가 동일한 부분문자열
  • bab 같은 팰린드롬 부분문자열, 단 가운데 중심 문자는 딱 한 글자여야하며 나머지 문자는 동일해야한다.
• 이 문제를 풀이함에 있어 처음 실수했던 것은 두 번째 조건을 잘못 이해했던 것
• 팰린드롬 문자열을 찾는데 cbbabbc 같이 세 가지 문자가 나타나도 팰린드롬으로 인정하는 문제로 이해했다. 이 부분을 어떻게 이해하느냐에 따라서 문제를 접근하는 방식이 완전히 달라지게되는데, 나는 처음 오해한 상황에서 문제를 풀이할 방법으로 BFS 탐색을 생각했었다.
• a 문자열을 기준으로 a 양 옆을 먼저 탐색한다. bab, bbabb, cbbabbc 같이 탐색 범위를 점점 넓혀나간다. 어려운 방법이다.
• 아마 주어진 문제가 문자열 S에 대해 팰린드롬인 모든 부분문자열을 찾으라는 내용이었다면 위 방법으로 푸는게 맞을 것이다.

풀이과정

• 아무튼, 이 문제를 풀 때 두 절차를 거치면 된다
• 먼저 주어진 문자열을 문자 + 빈도를 기록하는 배열로 바꾼다. 예를들어 aaab 일 경우 (a, 3), (b, 1)인 식이다.
• a, aa, aaa 모두 모두 1번 조건에 부합하는 부분문자열이다. 따라서 (a, 3)에 대한 나열할 수 있는 경우의 수를 구한다.
• 경우의 수 구하는 공식 : (n * (n+1)) / 2
• 다음으로 팰린드롬을 찾는데, 앞서 만들어둔 배열을 세 쌍씩 뽑아서 가운데 항목이 1 이고 양 옆 항목이 같은 문자일 경우 두 문자의 빈도 중 작은 값을 정답에 더한다.
• 처음 문제를 풀었을 때 가운데 카운트가 1이고 양 옆 문자열이 같으며, 카운트까지 동일할 경우 정답 += 카운트 해버렸더니 오답이 발생했다. 그 이유는 aaba 형식을 때 (a, 2), (b, 1), (a, 1) 이 되어 a 문자열에 대한 카운트 2와 1이 동일하지 않으므로 aba를 찾을 수 없다는 예외케이스를 만들었기 때문이다.

function substrCount(n, s) {
    const arr = [];
    let str = [...s, '$'], [t] = str, c = 1;    // 문자열 끝에 $ 기호를 삽입, 맨 끝 문자까지 카운트를 용이하게 만든다.
    for(let i = 1; i < str.length; i++) {
        if(str[i] !== t) {
            arr.push({ t, c });
            t = str[i], c = 1;
        } else {
            c += 1;
        }
    }

    let answer = arr.reduce((acc, { c }) => acc + (c * (c+1)) / 2, 0);
    for(let i = 0; i < arr.length - 2; i++) {
        const { t: t0, c: c0 } = arr[i];
        const { t: t1, c: c1 } = arr[i+1];
        const { t: t2, c: c2 } = arr[i+2];
        if(t0 === t2 && c1 === 1) {
            answer += Math.min(c0, c2);
        }
    }

    return answer;
}