[LeetCode]316. Remove Duplicate Letters

Remove Duplicate Letters - LeetCode

문자열 S가 주어질 때, 중복되는 글자를 제거하여, 모든 글자가 한 번씩만 나타나도록 하여라.

결과는 가능한 결과중 가장 smallest한 사전순(lexicographical order)

문제 이해하기

띄어쓰기도 있는걸까???? → constraint(제약조건)을 보니 그건 아님.

소문자 영문으로만 이루어져 있다.

문제를 한 번 잘못이해했음

• 사전순 ? → 그냥 ascii 코드값에 대응하는 배열 만들어서, 존재 여부 확인하고 그냥 출력하면 되는 거 아님?? → 아니었다.
• 순서도 지키면서 사전순으로 가장 작으면서 중복이 없어야한다.

문제 해결하기

순서도 지키면서, 사전순으로 가장 작으면서 중복이 없어야한다.

따라서, Stack과 배열을 사용하기로 하였다.

만들어야 하는 함수

1. 이미 사전순으로 앞에 나오는 글자가 나왔는지 여부를 확인하는 함수 → return boolean

풀지 못했다.

글자의 순서자체는 지켜져야 했다. 예를들어 cbacdcbc에서 선택된 c는 a와 d 사이에 있는 c였다.

글자는 중복되어서는 안되었고, 가능한 경우중, 사전순으로 가장 앞에 위치할 수 있는 문자열을 만들어야 했다.

문제는, 중복된 글자가 있는 경우, 어떤 글자를 선택하는가의 문제였다

어차피 한 개만 존재하는 글자는 무조건 선택하게 된다.

그렇다면 중복되는 글자는? 어느 위치에 있는 글자를 선택해야할까??

• 그런데 생각해보자... "cbacdcbc" 의 맨 앞에서부터 순차적으로 글자에 접근한다면 ?
  • c를 접근했을 때, 이 c 뒤에 c보다 사전순으로 앞서는 글자가 나올지 안 나올지, 나오면 어디에 나올지 , 이런 거를 다 고려하기가 너무 힘들다..
  • 각 글자가 중복되는지에 대한 정보는, 뭐 문자열을 한 번 쭉 순차적으로 탐색을 한 번 하고 나면, 각 글자의 등장 개수정보정도는 알 수 가 있다.
  • 하지만 결국은, 해당 글자에 도달했을 때 그것을 선택할지에 대하여 뒤의 내용까지 고려하며 선택하는 것은 너무 어려웠다. 아무리 조건을 만들어봐도 보이지가 않았다.
• 따라서 일단, 글자를 선택한다.
• 그리고는 순차적으로 다음 글자를 선택할지 말지 결정할 때는, 앞서 선택한 글자 정보를 사용한다.

  • 이 때 이정보는 어떤 정보여야할까?

    사전순 → 현재 글자가, 이미 바로앞에서 선택한 글자보다 “사전순으로 앞” 인 경우

    • 앞의 글자는 치우고, 자기가 앞에 있고 싶을 것.
    • 하지만 주어진 문자열에서 순서는 지켜야함.
    • 또한, 앞의 글자가, 만약 이 뒤에 더이상 없는 글자라면?? 그래서는 안됨. 그래서 그 개수 또한 체크를 해 줘야함.

"cbacdcbc"

이해를 돕기 위해 아래와 같이 그림을 그려보았다.

• 일단 이 과정을 조금 편하게 하기 위해서는 Stack을 사용해 볼 수 있음.
• 그리고 , 각 글자의 개수를 세어놓고, 탐색을 진행함에 따라, 이미 지나간 글자는 개수를 차감시켜야하기에 , 각 알파벳별 개수에 대한 배열도 생성
• 이미 선택된 글자인가를 확인하기 위해 visit이라는 배열도 생성

public String removeDuplicateLetters(String s) {
        int alphaCnt = 26; //'a'-'z'+1
        int[] cnt = new int[alphaCnt]; // 각 알파벳의 개수
        int slen = s.length();
        LinkedList<Character> stack = new LinkedList<>();
        boolean[] visit = new boolean[alphaCnt]; // 이미 stack 에 들어갔던 글자인가?
        StringBuilder sb = new StringBuilder("");
        // 각 알파벳의 개수를 업데이트
        for(int i =0 ; i<slen;i++){
            cnt[s.charAt(i)-'a']++;
        }
        // 각 글자를 stack 에 넣기 시작한다.
        for (int i =0 ; i<slen;i++){
            char ch = s.charAt(i);
            // 개수를 줄인다
            cnt[ch - 'a']--;
            // 기준 : ch 가 이미 등장했었는가?
            if(visit[ch-'a'])continue;
            // stack에 있는 글자중 ch보다 사전순으로 뒤에 등장하는 것이 있는가?
            // 이런거를 할 때는 항상 stack이 empty하진 않은지 확인해야함
            // 이미 stack에 있던 글자를 빼낼 때는, 그 글자가 이 뒤에서도 등장하긴 하는지를 확인해 줘야함.
            while( !stack.isEmpty() && ch < stack.peekLast() && cnt[stack.peekLast()-'a']>0){
                // visit되었던 것을 해제해야한다.
                visit[stack.pollLast()-'a'] = false;
            }
            // 이제 이 글자를 넣어줘야한다.
            stack.add(ch);
            // 방문 여부를 true로 바꾼다.
            visit[ch-'a'] = true;

        }
        // 그러면 이제는 stack에 차례로 꺼내 -> sb에 붙인다.
        for (Character ch : stack) {
            sb.append(ch);
        }
        return sb.toString();
    }