[LeetCode] 3223. Minimum Length of String After Operations

3223. Minimum Length of String After Operations

문제 링크

문제 이해하기 및 풀이

문자열 s가 주어진다.
주어진 문자열 s에 대해 아래의 과정을 계속 반복할 수 있다.
1. 문자열의 인덱스 i를 선택한다. 단, 아래의 조건을 만족해야 한다.
    - 인덱스 i의 왼쪽에 s[i]와 같은 문자가 1개 이상 존재해야 한다.
    - 인덱스 i의 오른쪽에 s[i]와 같은 문자가 1개 이상 존재해야 한다.
2. 인덱스 i의 가장 가까운 왼쪽에 있는 s[i]와 같은 문자를 삭제한다.
3. 인덱스 i의 가장 가까운 오른쪽에 있는 s[i]와 같은 문자를 삭제한다.

위 과정을 반복했을 때, 얻을 수 있는 s의 최소 길이를 반환하라.

위 조건을 읽으며 문자의 순서나 위치는 사실 상관없다는 특징을 발견했다.
a를 예로 들면 1번,2번,3번 index에 있던지, 5번,6번,7번 index에 있던지 상관없이 결국 최소 길이는 1로 반환될 것이다.
그래서 처음에는 알파벳을 key로 가지는 HashMap을 생성해서 index 번호를 Array 형태로 저장하려고 생각했다.
그 이후로 어떻게 반복하면 좋을까 생각하다가, 재귀를 사용했다.(아이디어를 구현하기에 가장 적합한 형태라고 생각했다.)
각각의 Map을 순회하며 array를 넣고, 그 길이가 3개 미만인 경우까지 위 규칙을 반복한다. (재귀)
그래서 알파벳마다 몇 개의 알파벳이 남는지 계산한 뒤 더하면 s의 최소 길이를 구할 수 있었다.




추가적으로 기존 로직은 빈 배열임에도 알파벳 체크가 이루어진다.
이를 최적화하기 위해 value가 없으면 빈 배열을, 있으면 기존 배열을 반환하는 getOrDefault라는 함수를 만들어 Map을 초기화하는 과정을 생략했다.

코드

/**
 * @param {string} s
 * @return {number}
 */
var minimumLength = function(s) {
    const stringMap = new Map();
    for(let i = 0 ; i < 26 ; i++) {
        stringMap.set(String.fromCharCode("a".charCodeAt(0)+i), []);
    }

    for(let i = 0 ; i < s.length ; i++) {
        stringMap.get(s[i]).push(i);
    }

    let result = 0;
    for(entry of stringMap) {
        result += checkArrayWithCondition(entry[1]);
    }
    return result;
};

var checkArrayWithCondition = function(array) {
    if(array.length === 0) {
        return 0;
    }

    if(array.length >= 3) {
        array.pop();
        array.shift();
        return checkArrayWithCondition(array);
    } else if(array.length < 3) {
        return array.length;
    } 
}

조금이나마 개선된 코드

/**
 * @param {string} s
 * @return {number}
 */
var minimumLength = function(s) {
    const stringMap = new Map();

    for(let i = 0 ; i < s.length ; i++) {
        getOrDefault(stringMap,s[i]).push(i);
    }

    let result = 0;
    for(entry of stringMap) {
        result += checkArrayWithCondition(entry[1]);
    }
    return result;
};

var checkArrayWithCondition = function(array) {
    if(array.length === 0) {
        return 0;
    }

    if(array.length >= 3) {
        array.pop();
        array.shift();
        return checkArrayWithCondition(array);
    } else if(array.length < 3) {
        return array.length;
    } 
}

var getOrDefault = function(map, key) {
    const item = map.get(key);
    if(item) {
        return item;
    }
    map.set(key,[]);
    return map.get(key);
}