JavaScript로 문자 출현 빈도에 따라 문자열을 '('와 ')'로 변환하는 방법

문제 개요

JavaScript 함수를 작성해야 합니다. 이 함수는 문자열 str을 첫 번째이자 유일한 인수로 받습니다.

함수는 입력 문자열을 기반으로 새로운 문자열을 생성해야 하며, 새 문자열의 각 문자는 다음 규칙에 따라 결정됩니다.

해당 문자가 원본 문자열에서 한 번만 등장하면 '('
해당 문자가 원본 문자열에서 두 번 이상 등장하면 ')'

또한 대소문자는 구분하지 않고 처리해야 합니다. 즉, 'S'와 's'는 같은 문자로 취급합니다.

예시

함수에 대한 입력이 다음과 같다면 −

입력

const str = 'Success';

출력

const output = ')())())';

'Success'라는 단어에서 대소문자를 무시하면 's'는 세 번, 'u'와 'e'는 한 번씩, 'c'는 두 번 등장합니다. 따라서 's'와 'c' 위치에는 ')'가, 'u'와 'e' 위치에는 '('가 들어가게 됩니다.

풀이 접근 방식

이 문제는 두 단계로 해결할 수 있습니다.

빈도 계산: 먼저 문자열을 모두 소문자로 변환한 뒤, 각 문자가 몇 번 등장하는지 해시 객체에 저장합니다.
결과 생성: 다시 문자열을 순회하면서 각 문자의 빈도가 1보다 크면 ')', 그렇지 않으면 '('를 결과 문자열에 추가합니다.

구현 코드

다음은 전체 코드입니다 −

const str = 'Success';
const mapString = (str = '') => {
    const mainStr = str.toLowerCase();
    const hash = {};
    let res = '';
    // 각 문자의 등장 횟수를 계산
    for (let char of mainStr) {
        hash[char] = ~~hash[char] + 1;
    }
    // 빈도에 따라 '(' 또는 ')' 생성
    for (let char of mainStr) {
        if (hash[char] > 1) {
            res += ')';
        } else {
            res += '(';
        }
    }
    return res;
};
console.log(mapString(str));

코드 설명

toLowerCase() 메서드로 입력 문자열을 소문자로 통일하여 대소문자를 무시합니다.
~~hash[char] + 1은 객체에 없는 키(undefined)를 0으로 변환한 후 1을 더하는 축약형 표현입니다.
두 번째 반복문에서 각 문자의 빈도를 확인하여 결과 문자열을 만듭니다.

출력 결과

)())())

콘솔에 위와 같은 결과가 출력되며, 이는 예상한 출력과 일치합니다.

시간 복잡도

이 알고리즘은 문자열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 해시 객체 때문에 공간 복잡도 역시 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다.