문제
문제링크
스택을 활용한 문제입니다. 저번엔 못풀었는데, 머리 말짱한 상태로 오랜만에 보니까 바로 풀리네요 ㅎㅎ. 여러분들도 머리가 너무 과열됐다면 좀 식히고 다음날 보시거나 해보세요 😂
풀이
접근 방법
먼저 스택을 왜 써야할까요? 그 이유는 한 글자씩 넣으면서 피크만 검사해서 빼주면 매우 편하기 때문입니다.
🚨 다른 방법 (실패)
문자열을 계속 검사하는 방법을 생각해봅시다. 문자열 돌면서 폭발 문자열 찾고 삭제시키고, 또 검사해서 새로 생긴 폭발 문자열 찾고 삭제시키고...
다음과 같은 예시를 생각해보세요.
- 문자열 : aaaaaabbbbbb
- 폭발 문자열 : ab
가운데서 ab를 지우고 다시 검사하면서 또 가운대 생긴 ab 지우고... 시간 복잡도가 O(n^2)이 걸린답니다.
핵심 원리
스택 사용 방법
스택을 사용하면 넣을 때마다 피크에서 타겟 문자열의 길이만큼만 검사해주면 됩니다. 순서는 다음과 같습니다.
- 스택에 문자를 넣는다
- 만약 타겟 문자열의 시작 문자와 같고, 스택에 들어가 있는 문자의 갯수가 타겟 문자열보다 크거나 같다면, 검사한다.
- 검사를 진행해 타겟 문자열이라면 빼준다.
- 반복
정말 간단하죠? 예시를 그림으로 보겠습니다.
문자열 : mirkovC4nizCC44
폭발 문자열 : C4
🚨주의 : 실제 구현부에선 폭발 문자열을 거꾸로 뒤집은 것의 첫번째 문자로 체크합니다. 실제 스택에 들어갈 때는 거꾸로 들어가니까요.
그리고 키노트에 소문자로 넣어도 대문자로 들어가서 참고하고 봐주세요 ㅠㅠ 죄송합니다.
문자열에서 m하나만 넣은 상태 입니다. 폭발 문자열의 첫번째 문자(거꾸로 뒤집은)인 '4'가 아니고, 스택의 크기도 폭발 문자열의 크기인 2보다 작기 때문에, 계속 진행합니다. 건너 뛰어서 조건에 맞는 '4'가 들어갔을 때 까지 가보겠습니다.
peek가 4로 저희가 찾는 문자입니다. 검사를 진행하며 폭발 문자열의 길이인 2만큼 pop 해봅니다.
전 StringBuilder에 append해서 붙였습니다. 폭발 문자열과 같은 문자열 이므로, 다시 스택에 넣지 않습니다. 이제 다음 C로 가보겠습니다.
4가 피크에 들어왔습니다. 꺼내볼께요.
폭발 문자열과 같으므로, 다시 스택에 넣지 않습니다.
남은 4를 넣어보면 피크가 4C이므로 또 제거해줍니다.
최종적으로 스택에 다음의 문자열이 남습니다. 이걸 차례대로 pop해서 꺼낸 뒤에 마찬가지로 StringBuilder에 붙여서 뒤집으면 정답이 되겠죠?
아래는 전체 코드 입니다. 주석을 참고 부탁드립니다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Character> stack = new Stack<>();
String str = br.readLine();
StringBuilder reversedTarget = new StringBuilder(br.readLine()).reverse();
// System.out.println("str = " + str);
// System.out.println("reversedTarget = " + reversedTarget.toString());
for (int i = 0; i < str.length(); i++) {
// 스택에 문자 추가
stack.add(str.charAt(i));
boom(stack, reversedTarget);
}
StringBuilder answer = new StringBuilder();
while (!stack.isEmpty()) {
answer.append(stack.pop());
}
if (answer.length() == 0) {
System.out.println("FRULA");
} else {
System.out.println(answer.reverse().toString());
}
}
private static void boom(Stack<Character> stack, StringBuilder reversedTarget) {
// 스택의 사이즈가 타겟길이보다 크거나 같고, 타겟 문자열의 첫번째 문자랑 같다면 검사
if (stack.size() >= reversedTarget.length() && stack.peek() == reversedTarget.charAt(0)) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < reversedTarget.length(); i++) {
sb.append(stack.pop());
}
// 서로 다르다면 다시 스택에 넣음
if (!(sb.toString().equals(reversedTarget.toString()))) {
for (int j = sb.length() - 1; j >= 0; j--) {
stack.add(sb.charAt(j));
}
}
}
}
}
마치며
다시 알고리즘 공부를 시작하며 시간 복잡도와 쉽게 설명하기 위해 그림을 최대한 잘 그리려고 노력하고 있습니다. 아이패드를 살까 고민 중인데, 가난한 취준생이라 참고 한땀한땀 트랙패드와 키노트로 그리고 있습니다... 양해부탁드려요 😂
꾸준하게 공부합시다!! 긴 글 읽어주셔서 감사합니다.
Reference
내 머리속
