짝지어 제거하기

---

🔗 🔗 짝지어 제거하기

문제 설명

---

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한 사항

---

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

입출력 예

---

입출력 예 설명

---

입출력 예 #1

위의 예시와 같습니다.

입출력 예 #2

문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

풀이

---

처음엔 while을 통한 반복문과 charAt 메서드로 접근했는데, 동작은 잘 됐으나 너무 느렸다.

곰곰히 생각해보다가 문득 Level 1의 🔗 크레인 인형뽑기 게임 (64061)와 매우 유사하다는 것을 깨달았다.

위 문제는 동일한 인형을 연속해서 뽑았을 경우, 해당 인형을 삭제하는 동작이 포함되어 있다.

위 문제의 인형을 문자열로 바꿔 생각해보면 매우 유사함을 알 수 있다.

Stack에 문자열을 하나씩 담으며, 담기 전에 가장 마지막에 삽입된 요소를 꺼내 비교한다.

만약 동일하다면, 같은 문자열이 두 번 반복됐다는 의미이므로 삽입없이 스택에서 마지막 요소를 제거한다.

아니라면, 그냥 삽입하면 된다.

예시: baabaa

1. 스택에 아무것도 없으므로 b를 삽입한다.
2. 다음 문자 a와 스택의 최근 데이터 b를 비교한다.
   1. 같지 않으므로 a를 삽입한다.
3. 다음 문자 a와 스택의 최근 데이터 a를 비교한다.
   1. 같으므로 스택의 최근 데이터 a를 삭제한다.
4. 다음 문자 b와 스택의 최근 데이터 b를 비교한다.
   1. 같으므로 스택의 최근 데이터 b를 삭제한다.
5. 스택에 아무것도 없으므로 다음 문자 a를 삽입한다.
6. 다음 문자 a와 스택의 최근 데이터 a를 비교한다.
   1. 같으므로 스택의 최근 데이터 a를 삭제한다.
7. 스택이 비었을 경우 1, 아닐 경우 0을 반환한다.

두 문자가 연속할 경우로 제한되어 있기 때문에, 세 자리 이상의 연속된 문자는 고려할 필요 없다.

코드

---

JAVA
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Stack;

/**
 * 짝지어 제거하기 클래스
 *
 * @author RWB
 * @since 2021.12.28 Tue 17:38:51
 */
class Solution
{
	/**
	 * 해답 반환 메서드
	 *
	 * @param s: [String] 문자열
	 *
	 * @return [int] 해답
	 */
	public int solution(String s)
	{
		Stack<Character> stack = new Stack<>();
		
		for (char c : s.toCharArray())
		{
			// 스택이 비었을 경우
			if (stack.isEmpty())
			{
				stack.add(c);
			}
			
			// 아닐 경우
			else
			{
				// 글씨가 서로 붙어있을 경우
				if (c == stack.peek())
				{
					stack.pop();
				}
				
				// 아닐 경우
				else
				{
					stack.add(c);
				}
			}
		}
		
		return stack.isEmpty() ? 1 : 0;
	}
}