https://leetcode.com/problems/removing-stars-from-a-string/submissions/1298687817/
1. 문제 및 접근
2390. Removing Stars From a String
String이 주어지면 그 안에 있는 *가 들어온 만큼 왼쪽 char를 지우기
순서가 중요하다 * 나오면 바로 왼쪽 꺼 지워주기
전부 다 유효하다.
Input: s = "leet**cod*e"
Output: "lecoe"
왼쪽이니까 stack에 넣으면서 *이 나오면 다음 인덱스로 가면 될 듯
Note:
- The input will be generated such that the operation is always possible.
- It can be shown that the resulting string will always be unique.
Constraints:
- 1 <= s.length <= 10^5
- s consists of lowercase English letters and stars *.
- The operation above can be performed on s.
2. 잘못 풀이
while (!stack.isEmpty()) { // isEmpty ?
int star = 0;
if(stack.peek() == '*') {
while (stack.peek() == '*') {
char n = stack.pop();
star++;
}
for (int i = 0; i < star; i++) {
stack.pop();
}}
else deque.addFirst(stack.pop());
}
*이 들어오면 들어온만큼 횟수를 세어주고, 뒤에서부터 지워도 되는 줄 알고
stack에서 *을 만나면, *이 이어지는 횟수동안 세고 뒤에서부터 지워줬다.
ex) s = [abb*cdfg*****x*]
1. [abb*cdfg*****x*]
- stack의 첫 * 하나에 대응하는 x를 뒤에서 부터 지움
- [abb*cdfg*****x*] -> [abb*cdfg*****]
2. [abb*cdfg*****]
- 뒤에서 센 *이 5개니까 대응하는 [b*cdfg]를 지움
- [abb*cdfg*****] -> [abb]
result = [abb] (틀린 답이다)
문제에서 요구하는 것은 *을 앞에서부터 만나자 마자 왼쪽을 지워줘야 한다.
1. [abb*cdfg*****x*]
- 첫 *에 대응하는 왼쪽 [b]를 지움
- [abb*cdfg*****x*] -> [abcdfg*****x*]
2. [abcdfg*****x*]
- 두 번째 * 5개에 대응하는 왼쪽 [bcdfg]를 지움
- [abcdfg*****x*] -> [ax*]
3. [ax*]
- 세 번째 * 하나에 대응하는 왼쪽 [x]를 지움
- [ax*] -> [a]
result = [a]
3. 풀이
public class RemovingStarsFromAString정답 {
// 2390. Removing Stars From a String
// String이 주어지면 그 안에 있는 *가 들어온 만큼 왼쪽 char를 지우기
// 순서가 중요하다 * 나오면 바로 왼쪽 꺼 지워주기
// 전부 다 유효하다.
// Input: s = "leet**cod*e"
//Output: "lecoe"
//왼쪽이니까 stack에 넣으면서 *이 나오면 다음 인덱스로 가면 될 듯
// 100000이 들어오고,
public static void main(String[] args) {
String s = "abb*cdfg*****x*";
String s1 = "leet**cod*e";
RemovingStarsFromAString정답 main = new RemovingStarsFromAString정답();
System.out.println(main.removeStars(s1));
}
public String removeStars(String s) {
Deque<Character> deque = new LinkedList<>();
StringBuilder sb = new StringBuilder();
int length = s.length();
for (int i = 0; i < length; i++) {
char current = s.charAt(i);
if (current == '*') {
deque.removeLast();
} else deque.add(current);
}
while (!deque.isEmpty()) {
sb.append(deque.removeFirst());
}
return sb.toString();
}
}
3-1. deque와 StringBuilder
stack으로 풀어도 되지만, 나중에 StringBuilder에 담기 쉽게 deque로 풀어야 겠다고 생각했다.
deque에 대한 포스팅은 이미 있으니 pass
99클럽 코테 스터디 17일차 TIL 구명보트 feat. deque
3-2. s의 요소를 deque에 추가
너무 간단하다.
현재 char(i)가 " 라면 ?
deque에서 마지막 요소를 지워준다.
가능한 이유는 문제에서 모든 작업은 가능하게 주어진다고 했기 때문에 따로 없는 요소를 뺄 예외처리 안해도 된다.
현재 char(i)가 " 아니라면 ?
deque에 앞에서 부터 추가
3-3. deque의 요소를 StringBuilder에 추가
추가 후 String으로 반환하면 끝
4. 마무리
문제를 잘못 읽고 이해했는데, 오늘은 미들러 문제인가 싶을 정도로 너무 쉬웠다.
요새 너무 편하게 하려고 deque에만 손이 가는데.. 의도적으로 다른 자료구조도 계속 써야겠더라
아니 근데 leetcode에서 내 코드의 시간 복잡도와 공간 복잡도를 계산해주는 기능이 있더라 ?
짜식 욕만 했는데 진짜 오늘부터 칭찬 +1 해준다.
계산이 직관적으로 힘들 때 보고 좀 더 시간이나 공간 복잡도를 줄이는 방법을 보안해봐야겠다
이번은 둘 다 O(N)이라 다른 코드를 참조하기 보다 다른 문제를 하나 더 풀어봐야겠네
'알고리즘' 카테고리의 다른 글
99클럽 코테 스터디 39일차 TIL Reduce Array Size to The Half (0) | 2024.06.27 |
---|---|
99클럽 코테 스터디 38일차 TIL Seat Reservation Manager feat.Heap (0) | 2024.06.26 |
99클럽 코테 스터디 35일차 TIL Flatten Nested List Iterator (0) | 2024.06.24 |
99클럽 코테 스터디 34일차 TIL Find the Winner of the Circular Game (0) | 2024.06.23 |
99클럽 코테 스터디 33일차 TIL Reordered Power of 2 (0) | 2024.06.22 |