문제

https://school.programmers.co.kr/learn/courses/30/lessons/12973

---

입력

• 문자열 s

---

출력

• 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 return

---

풀이

제한조건

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

접근방법

단순 구현(Stack 응용)

단순 Stack을 사용한 유사 문제가 많다.
https://www.acmicpc.net/problem/9012
https://www.acmicpc.net/problem/9935

Stack을 통해 현재 문자와 이전 문자가 같다면 제거하는 방식으로 수행하면 된다.
왜 Stack을 이용하면 풀이가 가능한지 그림으로 이해해보자.

예시
baabaa라는 문자열이 있다고 생각해보자.

처음에는 Stack이 비어있다.
문자열의 맨 처음 b 문자에서 stack이 비어있으므로 채운다.

그 다음 문자열인 a을 보자. stack에 내용물이 있지만, 현재 문자열과 일치하지 않는다.
따라서 제거되지 않고 그대로 stack에 쌓인다.

3번째 문자열인 a를 보자.
stack의 top에 동일한 문자열이 있다.
문제의 조건에 따라 제거될 수 있으므로 제거하고 다음 스텝으로 넘어간다.

동일하게 계속 반복해보자.
문자열의 마지막에 도달했을때, Stack에 남아있는 문자열이 있다면 모두 제거하지 못한것이므로 0을 반환하고

Stack이 비어있다면, 모두 제거에 성공한것이므로 1을 반환하자.

참고
이 문제는 여러번 반복할 필요없다. 한 번만 확인하면 된다..!

---

코드

import java.util.*;

class Solution {
	public int solution(String s) {
		ArrayDeque<Character> stack = new ArrayDeque();
		for (char c : s.toCharArray()) {
			if (!stack.isEmpty() && stack.peekLast() == c) {
				stack.pollLast();
				continue;
			}
			stack.addLast(c);
		}
		return stack.size() == 0 ? 1 : 0;
	}
}