search

spring-comes-to-us / algorithm-comes-to-us

알고리즘 스터디!
0 stars 0 forks source link

[LeetCode] 316. Remove Duplicate Letters #24

Closed IjjS closed 8 months ago

IjjS commented 10 months ago

문제 링크

image

Smallest Lexicographical Order이 헷갈린다면?

 * lexicographical order - 사전식 순서 ~= abc 순 결과를 하나의 단어로 보고 사전에서 먼저 나오는 순서라고 생각하시면 될 것 같네요! ex) "cbacdcbc" => 결과 순서: smaller << **"acdb"** < "adbc" < "adcb" < "bacd" < "badc" < "cadb" < "cbad" << larger
Sehee-Lee-01 commented 9 months ago

316. Remove Duplicate Letters

코드 풀이(1차 실패코드)

 ```java public String removeDuplicateLetters(String s) { Deque q = new LinkedList<>(); boolean[] isContain = new boolean['z' - 'a' + 1]; int[] cnt = new int['z' - 'a' + 1]; for (Character c : s.toCharArray()) { if (!isContain[c - 'a']) { q.add(c); cnt[c - 'a']++; } else { if (q.getLast() < c) { q.add(c); cnt[c - 'a']++; } } } String res = ""; while (!q.isEmpty()) { Character c = q.pollFirst(); if (cnt[c - 'a'] == 1) { res += c; } cnt[c - 'a']--; } return res; } ```

코드 풀이(재귀이용)

 ```java public String removeDuplicateLetters(String s) { Set sortedSet = getSortedString(s); for (char c : sortedSet) { String subStr = s.substring(s.indexOf(c)); if (sortedSet.equals(getSortedString(subStr))) { return c + removeDuplicateLetters(subStr.replaceAll(String.valueOf(c), "")); } } return ""; } private Set getSortedString(String s) { Set res = new TreeSet<>((c1, c2) -> c1 - c2); for (char c : s.toCharArray()) { res.add(c); } return res; } ```

코드 풀이(스택 이용)

 ```java class Solution { public String removeDuplicateLetters(String s) { Map counter = new HashMap<>(); Set seen = new HashSet<>(); Deque stack = new ArrayDeque<>(); char[] chars = s.toCharArray(); setCharCount(chars, counter); for (char c : chars) { counter.put(c, counter.get(c) - 1); if (seen.contains(c)) continue; while (!stack.isEmpty() && stack.peek() > c && counter.get(stack.peek()) > 0) { seen.remove(stack.pop()); } stack.push(c); seen.add(c); } StringBuilder sb = new StringBuilder(); // 그냥 "" 와 + 연산 했을 때보다 1ms 빠름 while (!stack.isEmpty()) { sb.append(stack.pollLast()); } return sb.toString(); } private void setCharCount(char[] chars, Map counter) { for (char c : chars) { counter.put(c, counter.getOrDefault(c, 0) + 1); } } } ```

코멘트

yenzip commented 9 months ago

316. Remove Duplicate Letters

코드 풀이

 ```java class Solution { public String removeDuplicateLetters(String s) { Deque dq = new ArrayDeque<>(); boolean[] alphabet = new boolean[26]; int[] lastIdx = new int[26]; Arrays.fill(lastIdx, -1); for(int i = 0; i < s.length(); i++) { lastIdx[s.charAt(i) - 'a'] = i; } for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(alphabet[c - 'a']) { // 중복 문자 continue; } while(!dq.isEmpty() && c < dq.peekLast() && i < lastIdx[dq.peekLast() - 'a']) { alphabet[dq.pollLast() - 'a'] = false; } alphabet[c - 'a'] = true; dq.offerLast(c); } StringBuilder answer = new StringBuilder(); while(!dq.isEmpty()) { answer.append(dq.pollFirst()); } return answer.toString(); } } ```

코멘트

ASak1104 commented 9 months ago

316. Remove Duplicate Letters

코드 풀이

 ```java class Solution { fun removeDuplicateLetters(s: String): String { if (s.length <= 1) { return s } val mask = getMask(s, 0) var i = 0 var bit = 1 while (bit <= mask) { val c = 'a' + i if (bit and mask == bit) { val start = s.indexOf(c) if (mask == getMask(s, start)) { val next = s.substring(start + 1) .replace(c.toString(), "") return c + removeDuplicateLetters(next) } } bit = 1 shl ++i } return "" } fun getMask(s: String, start: Int): Int { var ret = 0 for (i in start until s.length) { ret = ret or (1 shl (s[i] - 'a')) } return ret } } ```

책 보고 다시 풀어봤습니다

 ```java import java.util.ArrayDeque; import java.util.Deque; class Solution { static Deque deque; static int[] lastIndices; static boolean[] visits; static char[] chars; public String removeDuplicateLetters(String s) { init(s); for (int i = 0; i < chars.length; i++) { char c = chars[i]; int index = c - 'a'; if (visits[index]) { continue; } while (isPollable(i, c)) { int pollIndex = deque.pollLast() - 'a'; visits[pollIndex] = false; } visits[index] = true; deque.addLast(c); } StringBuilder sb = new StringBuilder(26); while (!deque.isEmpty()) { sb.append(deque.pollFirst()); } return sb.toString(); } private void init(String s) { deque = new ArrayDeque<>(26); lastIndices = new int[26]; visits = new boolean[26]; chars = s.toCharArray(); for (int i = 0; i < chars.length; i++) { lastIndices[chars[i] - 'a'] = i; } } private boolean isPollable(int i, int c) { return !deque.isEmpty() && deque.peekLast() > c && i < lastIndices[deque.peekLast() - 'a']; } } ```

코멘트

uijin-j commented 9 months ago

316. Remove Duplicate Letters

코드 풀이

 재귀를 이용한 풀이 ```java class Solution { public String removeDuplicateLetters(String s) { for(char c: toSortedSet(s)) { String suffix = s.substring(s.indexOf(c)); if(toSortedSet(s).equals(toSortedSet(suffix))) { return c + removeDuplicateLetters(suffix.replaceAll(String.valueOf(c), "")); } } return ""; } private Set toSortedSet(String s) { Set set = new TreeSet<>((a, b) -> (a == b) ? 0 : a - b); for(char c: s.toCharArray()) { set.add(c); } return set; } } ``` 스택을 이용한 풀이 ```java class Solution { public String removeDuplicateLetters(String s) { Map counts = new HashMap<>(); // 문자 갯수 count Map processed = new HashMap<>(); // 해당 문자가 처리되었는지 Deque stack = new ArrayDeque<>(); for(char c: s.toCharArray()) { counts.put(c, counts.getOrDefault(c, 0) + 1); } for(char c: s.toCharArray()) { counts.put(c, counts.get(c) - 1); if(processed.containsKey(c) && processed.get(c)) { continue; } while(!stack.isEmpty() && stack.peek() > c && counts.get(stack.peek()) > 0) { processed.put(stack.pop(), false); } stack.push(c); processed.put(c, true); } StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()) { sb.append(stack.pop()); } return sb.reverse().toString(); } } ```

코멘트

shoeone96 commented 9 months ago

316. Remove Duplicate Letters

코드 풀이

 ```java class Solution { public String removeDuplicateLetters(String s) { Map counter = new HashMap<>(); Map seen = new HashMap<>(); Deque stack = new ArrayDeque<>(); for(int i = 0; i < s.length(); i++){ counter.put(s.charAt(i), counter.get(s.charAt(i)) == null ? 1 : counter.get(s.charAt(i)) + 1); } for(int i = 0; i < s.length(); i++){ counter.put(s.charAt(i), counter.get(s.charAt(i)) -1); if(seen.get(s.charAt(i)) != null && seen.get(s.charAt(i)) == true){ continue; } while(!stack.isEmpty() && stack.peek() > s.charAt(i) && counter.get(stack.peek()) > 0){ seen.put(stack.pop(), false); } stack.push(s.charAt(i)); seen.put(s.charAt(i), true); } StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()){ sb.append(stack.pollLast()); } return sb.toString(); } } ```

코멘트

IjjS commented 8 months ago

316. Remove Duplicate Letters

코드 풀이

 ```java class Solution { public String removeDuplicateLetters(String s) { int[] counts = new int[26]; boolean[] checked = new boolean[26]; Deque stack = new ArrayDeque<>(); for (char c : s.toCharArray()) counts[c - 'a']++; for (char c : s.toCharArray()) { int index = c - 'a'; counts[index]--; if (checked[index]) continue; checked[index] = true; while (!stack.isEmpty() && stack.peek() > c && counts[stack.peek() - 'a'] != 0) { checked[stack.pop() - 'a'] = false; } stack.push(c); } StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { sb.append(stack.pop()); } return sb.reverse() .toString(); } } ```

코멘트