티스토리 뷰
Problem
You are given a string s, which contains stars *.
In one operation, you can:
- Choose a star in s.
- Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
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.
Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".
Example 2:
Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.
Constraints:
- 1 <= s.length <= 105
- s consists of lowercase English letters and stars *.
- The operation above can be performed on s.
Solution
문자열 s가 주어질 때 *와 가장 가까운 왼쪽 문자를 제거하는 작업을 모두 완료했을 때의 문자를 반환하는 문제입니다.
package io.lcalmsky.leetcode.removing_stars_from_a_string;
import java.util.Stack;
public class Solution {
public String removeStars(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '*') {
stack.pop();
continue;
}
stack.push(c);
}
StringBuilder stringBuilder = new StringBuilder();
while (!stack.isEmpty()) {
Character pop = stack.pop();
stringBuilder.append(pop);
}
return stringBuilder.reverse().toString();
}
}
저는 stack을 이용해 문제를 해결했습니다.
stack에 문자를 하나씩 추가하면서 *일 경우에 기존 문자를 스택에서 제거하게되면 기존 문자열 기준 왼쪽 문자가 제거되게 됩니다.
그리고 stack에 남은 문자열은 역순이 되므로 마지막에 reverse를 이용해 뒤집어주었습니다.
Test
package io.lcalmsky.leetcode.removing_stars_from_a_string;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;
class SolutionTest {
@Test
void testAll() {
assertAll(
() -> test("leet**cod*e", "lecoe"),
() -> test("erase*****", "")
);
}
private void test(String s, String expected) {
// when
Solution solution = new Solution();
String actual = solution.removeStars(s);
// then
assertEquals(expected, actual);
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 2095. Delete the Middle Node of a Linked List (0) | 2023.08.02 |
---|---|
[LeetCode] 735. Asteroid Collision (0) | 2023.08.01 |
[LeetCode] 2352. Equal Row and Column Pairs (0) | 2023.07.30 |
[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element (0) | 2023.07.29 |
[LeetCode] 1004. Max Consecutive Ones III (0) | 2023.07.28 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 함께 자라기 후기
- 헥사고날 아키텍처
- Spring Boot
- @ManyToOne
- 스프링 부트 회원 가입
- 알고리즘
- Spring Boot JPA
- Linux
- JSON
- gRPC
- 클린 아키텍처
- Spring Data JPA
- 함께 자라기
- 스프링 부트 튜토리얼
- leetcode
- Java
- proto3
- spring boot jwt
- r
- spring boot application
- 스프링 부트
- Jackson
- Spring Boot Tutorial
- intellij
- 스프링 부트 애플리케이션
- JPA
- 스프링부트
- QueryDSL
- 스프링 데이터 jpa
- spring boot app
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
글 보관함