📖 목차
👆 링크
🤞 문제
👌 코드
🖖 풀이
🖐 Git gist 주소
📌 링크
https://programmers.co.kr/learn/courses/30/lessons/12973
📝 문제
소문자 알파벳으로만 이루어진 문자열 s가 있다. s에서 연달아 이어지는 같은 알파벳 두 개를 찾아 제거한 뒤, 앞 뒤로 이어붙인다. 이 과정을 s가 모두 소멸할때까지 반복한다.
만약 s를 제거할 수 있다면 1을, 제거할 수 없다면 0을 리턴한다.
💡 예를 들어, 문자열
s=baabaa라면
b aa baa → bb aa → aa →의 순서로 문자열을 모두 제거할 수 있으므로1을 리턴한다.
💻 코드
package programmers_12973_PairAndRemove;
import java.util.*;
public class Solution2 {
public int solution(String s){
Deque<Character> str = new LinkedList<>();
for(char ch : s.toCharArray()) {
if(!str.isEmpty() && str.peek() == ch) str.pollFirst();
else str.addFirst(ch);
}
return str.isEmpty() ? 1 : 0;
}
}
✍ 풀이
👉 문자열 s 에서 한 문자씩 다음 문자와 비교하며 같은지 체크한다.
👉 같다면 해당 두 문자를 제거하며 위 과정을 반복한다.
이 문제 역시 시간복잡도를 잘 계산해야 하는 문제이다.
처음에 같은 두 문자를 제거해야 한다는 생각에 이중반복문으로 풀었다가 시간초과가 나며 터지는 결과를 낳았다(...) ▼
package programmers_12973_PairAndRemove;
import java.util.*;
class Solution{
static List<Character> str = new LinkedList<>();
public int solution(String s){
// baabaa
// b aa baa → bb aa → aa →
initStr(s); // 문자열을 List구조인 str에 넣는다.
boolean flag; //
while(!str.isEmpty()) {
flag = false;
for(int i = 0; i < str.size(); i++) {
if(i == str.size() - 1) break;
if(str.get(i) == str.get(i + 1)) {
flag = true;
/*
str.remove(i);
str.remove(i + 1);*/
str.remove(i + 1);
str.remove(i);
}
}
if(flag == false) return 0;
}
return 1;
}
private void initStr(String s) {
for(int i = 0; i < s.length(); i++) {
str.add(s.charAt(i));
}
}
} for문으로 문자열 s의 문자 하나하나씩 다음 문자와 비교했고, 만약 같을 경우에는 해당 문자 두 개를 list에서 제거했다.
굳이 list로 푼 이유는 해당 엘리먼트만 콕 찝어 제거할 수 있고, 또 무엇보다 두 문자를 비교할 때 Stack과 Queue는 하나를 꺼내야 하기 때문이었다.
하지만 제거해야 한다는 고정관념에 박혀 이렇게 직관적으로 풀 경우, 시간복잡도 때문에 문제를 통과할 수 없게 된다.
💡
while문=O(N),for문=O(N),ArrayList::remove=O(N)
→ 총O(N^3)의 시간 복잡도를 가지기 때문에,s의 최대 길이인100만일 경우 터지게 된다.
❓ 그렇다면 대체 어떻게 for문을 쓰지 않고 문자를 비교할 수 있을까?
❓ 또한 O(N)의 시간복잡도를 가지는 remove를 쓰지않고도 문자를 제거하는 방법은 무엇일까?
❓ 마지막으로, 비교 과정에서 만약 문자가 제거됐다면 새로운 문자열을 검사해야 한다. 이러한 반복을 while문을 쓰지 않고 어떻게 구현해야 할까?
1. for문을 사용하지 않고 문자 비교
문자열 s = baabaa 이 있고, 해당 문자열 내에 같은 문자가 연속하는지 확인하기 위해서는 for문으로 문자 하나하나씩 비교해보는 수밖에 없다.
2. remove()를 사용하지 않고 요소 제거하기
보통 나는 습관적으로 다음과 같은 for문을 짜곤 한다.
for(int i = 0; i < s.length; i++) { if(s.charAt(i) == s.charAt(i + 1) { ...
하지만 그렇게 되면 비교할 때 반사적으로 if(s.charAt(i) == s.charAt(i + 1) 이렇게 짜고 있는 내 모습을 발견하게 된다(...)
여기서 i번째 인덱스와 i+1번째 인덱스를 콕 찝어 제거해야 한다는 강박관념(?)에 싸여 list객체의 remove밖에 떠올릴 수 밖에 없는 몸이 되어버린다.
때문에, 아래와 같은 방식의 for문으로 비교하면 remove()를 사용하지 않고도 문자를 비교할 수 있다.
Stack<Character> stack = new Stack<>(); stack.push(0); //stack이 비어있으면 처음에 비교가 불가능하므로 알파벳이 아닌 임의의 문자를 넣어준다. for(char ch : s.toCharArray()){ if(!stack.isEmpty() && stack.peek() == ch){ ...
3. while문을 사용하지 않고 어떻게 반복할 수 있을까?
stack.push(0)을 하는 이유는 stack이 비어있으면 처음부터 비교가 불가하기 때문이었다. 하지만 굳이 이런 작업을 하지 않아도 된다.
Stack<Character> stack = new Stack<>(); for(char ch : s.toCharArray()){ if(!stack.isEmpty() && stack.peek() == ch) stack.pop(); else stack.push(ch); ...
처음 stack은 비어있지만, 그렇기 때문에 stack의 맨 첫번째 요소는 ch와 같지 않으므로 else문을 사용해 stack에 문자를 넣어주면 된다.
else stack.push(ch); 이 한 줄을 추가할 경우, while()을 사용하지 않고도 반복할 수 있다.
💡 즉, ①
stack이 비어있거나 ② 두 문자가 같지 않을 때stack에 문자를 넣어줌으로써,stack.push(0)같은 이런 헛짓거리도 하지 않아도 된다.
또, 변경이 빈번히 일어나는 문자열을 실시간으로 비교가 가능해지니while()문을 쓸 필요도 없어진다.
👉 설명
stack이 비지 않은 상태에서 스택에 담긴 이전 문자와, ch에 담긴 그 다음 문자가 같을 경우에만 이전 문자를 제거해준다.
이후, stack은 다시 비게 되고 else문에 따라 다음 문자가 stack에 담긴다. ch는 현 stack에 담긴 문자의 다음에 있는 문자가 된다.
💡 stack에는 서로 같지 않은 문자를 넣는다.
이러한 과정을 반복하며 for문이 끝난 뒤에, stack이 비어있으면 1, 비어있지 않으면 0을 리턴하면 된다.
만약 비교 대상을 stack이 아닌 list로 했다면 새롭게 갱신된 list를 while()문으로 반복해가며 비교했어야 한다.
하지만, stack은 추가와 삭제가 실시간으로 이루어질 수 있기 때문에 while()문을 쓰지 않고도 문제를 풀 수 있다.
💡 즉,
s=baabaa일 때stack이나queue를 사용하지 않을 경우
1회 :b (aa) baa
2회 :(bb) aa
3회 :(aa)
총 반복문을 세 번 돌려야 하지만, stack이나 queue를 사용할 경우에는
1회 -
②(b ①(aa) b) ③(aa)
인덱스 0부터 5까지 반복문을 한 번만 돌 수 있다.
👩💻 Git gist 주소
https://gist.github.com/ysyS2ysy/48bdf1143bb93200f0625f0dd2d90a90
