[LeetCode] 316. Remove Duplicate letters (javascript)

먼저 각 문자의 총 등장 개수를 저장한다

stack에 b, c, a 가 들어오고 또 b, c가 들어올 때 (b, c, a ,b, c 예제)

a가 들어오는 순간 stack에 이미 들어있던 b, c는 뒤에 또 등장하므로 (cnt>0) 이므로 나중에 다시 stack에 넣어주면 

되므로 stack에서 없애고 a를 집어넣는다. 

뒤에 다시 등장하는 b, c는 cnt==0이므로 또 뒤에 등장하는 b,c가 없어 더 이상 스택에서 제거할 수 없고

지금 사용한다고 보면 된다. 

 

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
    
    const cnt={} // 각 문자가 등장하는 개수 저장하는 객체
    for(let i=0;i<s.length;i+=1){
        if(!cnt[s[i]]){
            cnt[s[i]]=1;
        }else{
            cnt[s[i]]+=1;
        }
    }
       
    const checked={}; // 해당 문자가 체크되었는지 
    const stack=[];
    for(let i=0;i<s.length;i+=1){
        cnt[s[i]]-=1; //한 번 등장하면 등장 가능한 갯수 줄여준다
        if(checked[s[i]])continue; // 이미 stack에 있는 수라면 지나가기 
        while(stack && stack[stack.length-1]>s[i] && cnt[stack[stack.length-1]]>0){
         //현재의 수가 이미 stack에 있는 문자보다 사전적으로 더 빠른 수이고 stack에 있는 문자가
         //굳이 지금 쓰이지 않고 나중에 다시 등장할 수 있다면 
            checked[stack[stack.length-1]]=0; //stack체크에서 삭제해준다. 
            stack.pop(); //마지막 문자 삭제 
        }
        stack.push(s[i]); //현재 문자 넣기
        checked[s[i]]=1; //현재 문자는 stack에 들어있게 되었다 
    }
    return stack.join('')
};