21. 중복 문자 제거
https://leetcode.com/problems/remove-duplicate-letters/
Remove Duplicate Letters - LeetCode
Can you solve this real interview question? Remove Duplicate Letters - Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible re
leetcode.com
📌문제
중복된 문자를 제외하고 사전식 순서로 나열하라
- 예제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();
}
-
'Algorithm > PTUStudy' 카테고리의 다른 글
8주차. 10866 덱 (0) | 2023.03.30 |
---|---|
8주차. 스택, 큐(일일 온도) (0) | 2023.03.30 |
8주차. 스택, 큐(유효한 괄호) (0) | 2023.03.30 |
6-7주차 연결 리스트(홀짝 연결리스트) (0) | 2023.02.16 |
6-7주차 연결 리스트(페어의 노드 스왑) (0) | 2023.02.16 |
21. 중복 문자 제거
https://leetcode.com/problems/remove-duplicate-letters/
Remove Duplicate Letters - LeetCode
Can you solve this real interview question? Remove Duplicate Letters - Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible re
leetcode.com
📌문제
중복된 문자를 제외하고 사전식 순서로 나열하라
- 예제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();
}
-
'Algorithm > PTUStudy' 카테고리의 다른 글
8주차. 10866 덱 (0) | 2023.03.30 |
---|---|
8주차. 스택, 큐(일일 온도) (0) | 2023.03.30 |
8주차. 스택, 큐(유효한 괄호) (0) | 2023.03.30 |
6-7주차 연결 리스트(홀짝 연결리스트) (0) | 2023.02.16 |
6-7주차 연결 리스트(페어의 노드 스왑) (0) | 2023.02.16 |