[프로그래머스] 짝지어 제거하기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

b aa baa → bb aa → aa →

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

2. 입력

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

3. 예제

s	result
baabaa	1
cdcd	0

4. 풀이

이번 문제는 프로그래머스의 올바른괄호 문제와 유사하다.

 

동일한 알파벳이 주어지면 지운다는 것은 ( <- 괄호 다음 ) <- 이괄호이면 문자열에서 괄호를 지우는 것과 같은 것이다.

 

그래서 이번 문제 또한 Stack을 이용하여 문제 풀이가 가능하다.

 

먼저 문자열에서 가장 앞 즉 Index가 0인 문자를 Stack에 넣은 뒤 for문을 통하여 문자열 Index 1부터 문자열 길이만큼 반복을 수행한다.

 

반복을 수행하면서 반복문 i변수에 해당하는 Index의 문자와 현재 Stack의 가장 위에 위치한 문자가 같으면 Stack의 pop을 통해 Stack 최상단 문자를 빼준다.

 

여기서 중요한 것은 만약 Stack이 비어있는 상태이면 현재 문자를 무조건 Stack에 집어 넣어야 하는 것이다.

 

이번에는 반대로 반복문 i변수에 해당하는 Index의 문자가 Stack의 가장 위에 위치한 문자와 다르다면 해당 문자를 Stack에 push 하여 넣어 준다.

 

이렇게 문자열의 길이 만큼 반복문이 종료되면 Stack의 상태를 확인하여 비어 있는 상태면 모든 문자가 짝을 이루어지는 문자인 것이므로 1을 리턴한다.

 

만약 Stack에 문자가 남아 있다면 해당 문자들로 인해 짝을 이루지 못하는 것이므로 0을 리턴한다.

5. 코드

전체 코드는 Git에 있습니다.

if ((s.length() & 1) == 1)
	return 0;
else {
	Stack<String> stack = new Stack<>();
	stack.push(s.substring(0, 1));

	for (int i = 1; i < s.length(); i++) {
		if (!stack.isEmpty() && stack.peek().equals(s.substring(i, i + 1))) stack.pop();
		else stack.push(s.substring(i, i + 1));
	}

	if (stack.isEmpty())
		return 1;
	else
		return 0;
}