8주차. 스택,큐 (중복 문자 제거)

21. 중복 문자 제거

https://leetcode.com/problems/remove-duplicate-letters/

Remove Duplicate Letters - LeetCode

📌문제
중복된 문자를 제외하고 사전식 순서로 나열하라

- 예제1
  📝입력

Input: s = "cbacdcbc"

  💻출력

Output: "acdb"

 - 예제2

  📝입력

Input: s = "bcabc"

  💻출력

Output: "abc"

    
📌풀이(컬렉션 활용)

6ms, 42.6mb

class Solution {
    public String removeDuplicateLetters(String s) {
        int cnt = s.length();
        Set<Character> set = new HashSet<>(); // 검사 유무
        Map<Character, Integer> map = new HashMap<>(); // 글자가 총 몇번 나왔는지
        Stack<Character> stack = new Stack<>(); // 정답을 담을 스택

        // 글자가 몇번 나왔는지 등록
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }

        for(char c: s.toCharArray()){
            // 글자 하나씩 검사할 때마다 map에서 개수를 뺌. 검사를 했으니까
            map.put(c, map.get(c)-1);
            if(set.contains(c)) continue; // 이미 검사를 끝낸 글자면 다음으로

            // 사전식으로 정렬해야 하기 때문에 앞으로 더 나올 문자인지, 이 문자가 지금 검사하려는 문자보다 큰 문자인지 확인.(사전식 정렬을 위해)
            while(!stack.isEmpty() && stack.peek() > c && map.get(stack.peek()) > 0){
                set.remove(stack.pop()); // 검사를 끝냄. stack에서도 뺌.
            }
            stack.push(c);
            set.add(c);
        }

        StringBuilder sb = new StringBuilder();
        while(stack.size() > 0){
            sb.insert(0, stack.pop());
        }
        return sb.toString();
    }
}

 

설명은 주석에 있는 그대로.

RunTime시간이 하위권이여서 풀이가 잘못됐다 생각하고, 다른 사람 답지를 찾아보았다. 

📌풀이(스택)

3ms, 41.5 MB

public String removeDuplicateLetters(String s) {
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++){
            lastIndex[s.charAt(i) - 'a'] = i; // 문자의 마지막 인덱스를 넣는다.
        }
        
        boolean[] seen = new boolean[26]; // keep track seen
        Stack<Integer> st = new Stack();
        
        for (int i = 0; i < s.length(); i++) {
            int curr = s.charAt(i) - 'a';
            if (seen[curr]) continue;
            while (!st.isEmpty() && st.peek() > curr && i < lastIndex[st.peek()]){
                seen[st.pop()] = false; // pop out and mark unseen
            }
            st.push(curr); // add into stack
            seen[curr] = true; // mark seen
        }

        StringBuilder sb = new StringBuilder();
        while (!st.isEmpty())
            sb.append((char) (st.pop() + 'a'));
        return sb.reverse().toString();
    }

-