Sherlock and the Valid String

[dlehdanakf]

Sherlock and the Valid String

• 문제 바로가기
• 문자열 S가 주어질 때 S를 구성하는 모든 알파벳이 동일한 빈도로 출현하는지 체크하는 메소드를 작성하는 문제
• 단, 한 문자열에 대해서만 딱 한번 제거가 가능하다.
• 예를 들어 aaa 문자열은 당연 통과되지만, aabbb 같은 경우도 b를 하나 제거하면 모든 알파벳의 출현 빈도가 동일하므로 통과 가능하다.

풀이과정

• 일단 빈도수를 체크한다는 조건이 보이면 자연스럽게 Map을 사용해야한다는 느낌이 팍팍 든다.
• Map을 선언하고 각 알파벳 별 빈도수를 기록한 다음 "빈도수"만 배열로 뽑아온다.
• 배열 속 원소의 빈도가 모두 같은지 파악하기 위해 Set 객체에 넣어보고 Set.prototype.size 값이 1이면 그냥 YES!
• 빈도의 종류가 2일 경우 문제가 조금 복잡해지지만 3 이상일 경우 더 볼것 없이 NO를 반환하면 된다. 세 가지 이상의 빈도가 있을 경우, 예를 들어 [3,2,1] 일 경우 1을 제거해도 여전히 [3,2]가 남는다. aaabbc 일 때 c를 제거해도 여전히 aaabb라는 것.
• 2일 경우에는 aabbb 처럼 어떤 문자열 하나를 제거했을 때 빈도를 동일하게 맞출 수 있는지 파악하면 된다.

function isValid(s) {
    const obj = new Map;
    for(const e of s) {
        obj.set(e, (obj.get(e) || 0) + 1);
    }

    const _v = [...obj.values()], _s = new Set(_v);
    if(_s.size === 1) {
        return 'YES';
    } else if(_s.size === 2) {
        const min = Math.min(..._s), max = Math.max(..._s);
        if(max - min === 1 && _v.filter(e => e === max).length === 1) return 'YES';
        return 'NO';
    }

    return 'NO';
}

오답내용

• 하지만 위 코드를 입력했을 때 몇몇 테스트 케이스가 통과되지 않았다.
• 엣지케이스가 있을 것 같아서 몇분을 고민해봤지만 도무지 떠오르지 않았는데, aabbb 말고 다른 문제가 있었다
• aabbc 형태가 있었던것. 빈도가 높은 문자열을 하나 제거할 생각만 하느라 딱 하나만 출현한 문자를 제거하는 경우를 생각 못했었다.
• 조건문을 하나 추가하자 모든 테스트 케이스를 통과할 수 있었다.

function isValid(s) {
    const obj = new Map;
    for(const e of s) {
        obj.set(e, (obj.get(e) || 0) + 1);
    }

    const _v = [...obj.values()], _s = new Set(_v);
    if(_s.size === 1) {
        return 'YES';
    } else if(_s.size === 2) {
        const min = Math.min(..._s), max = Math.max(..._s);
        if(max - min === 1 && _v.filter(e => e === max).length === 1) return 'YES';
        if(min === 1 && _v.filter(e => e === min).length === 1) return 'YES';
        return 'NO';
    }

    return 'NO';
}