[JAVA] 프로그래머스 - 짝지어 제거하기

문제내용

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

코딩테스트 연습 - 짝지어 제거하기

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

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

b aa baa → bb aa → aa →

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

제한사항

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

---

문제 접근 방법

문제를 요약하자면 문자열 s가 주어졌을때 s에서 aa,bb,cc.. 등등 붙어있는 알파벳이 같은 알파벳이라면 제거하는 방식이다. 또 반환값은 문자열이 모두 제거 된다면 1을 반환하고 아니면 0을 반환하면 되는 문제이다.

 

이 문제를 풀면서 느낀건 구현자체는 쉽다. 하지만 얼마나 효율적인 코드를 작성하느냐가 어려운 문제였다고 생각한다.

나는 이문제를 풀면서 3가지 방식으로 풀어봤고 3가지 중 2가지는 효율성면에서 탈락, 그리고 마지막에서야 정답이 됐다.

 

내가 풀었더니 방식을 말해보겠다.

• 첫번째 풀이(틀림)
  StringBuilder(sb)와 while문을 이용해 구현했고, while문의 종료조건은 sb.length > 0 일때 혹은 몇번째 인덱스를 확인하고 있는지 나타낼 변수 idx가 idx > sb.length-2 로 정의했다. 그리고 idx를 하나씩 증가시키면서 sb.charAt(idx)==sb.chart(idx+1) 을 확인해서 문자를 하나씩 지워가고 지운다면 idx를 0으로 다시 초기화시키는 방식이였다.
  정확성은 맞지만 효율적으로 볼때 매우 안좋다. 왜냐면 만약 문자를 지우게 된다면 다시 0번째 문자부터 탐색해야 하기 때문에 좋지 않은 코드이다.
  
  
• 두번째 풀이(틀림, 개선)
  첫번째 풀이때 다시 0번째부터 탐색하는것을 막기위해 스택 자료구조를 이용했다.
  방법은 sb의 첫번째 문자와 스택의 top과 비교를하고 같다면 스택의 pop을 이용, 다르다면 push를 이용해 스택의 크기를 변화시켰다. 그리고 sb의 첫번째 문자는 같든 다르든 지워주고 이번 while문의 종료조건 역시 sb.length>0일때로 정의했다.
  이렇게 while문을 빠져나왔을때 스택이 비어있다면 문자열이 모두 제거된것, 아니라면 모두 제거된건 아니라는 의미로 해석해 반환값을 줬다.
  
  
• 세번째 풀이(정답)
  일단 두번째 풀이까지 개선된건 맞지만 위의 풀이역시 효율성에서 탈락하고 만다. 위에서 탈락한 이유를 생각해보면 StringBuilder객체를 생성하고 할당된 문자열을 계속해서 지우면서 문자열을 가변시키는 과정 때문이라 생각했다. 그래서 스택과 주어진 문자열만 이용해야겠다는 생각을 했고 답은 생각보다 간단했다.문자열을 문자배열로 바꾸는 함수를 이용해 0번째~마지막까지 문자를 체크하며 가는데 이때 스택에 문자를 넣는 기준은 두번째 풀이와 똑같이 top과 비교하며 pop, push를 했다
  마지막도 마찬가지로 스택이 비었을때와 아닐때로 구분하여 반환값을 결정했다.

솔직히 이렇게 말로만 해서 알아듣기는 힘들거라 생각한다.(내가 말을 잘하는것도 아니기때문에 ㅠㅠ..)

 

세번째 풀이에대해 예를 들어 설명해보겠다. 문자열이 문제에서 주어진 s = "baabaa" 라고 할때char[] t = s.s.toCharArray();  ,  Stack<Character> st = new Stack<Character>(); 으로 정의하겠다.

 

0번째 문자일때 t[0] = b , st.peek() = nullt[0] 과 st.peek() 비교  -> push -> 결과 : st = [b];

 

1번째 문자일때 t[1] = a , st.peek() = bt[1] 과 st.peek() 비교 -> push -> 결과 : st = [b, a];

 

2번째 문자일때 t[2] = a , st.peek() = at[2] 와 st.peek() 비교 -> pop -> 결과 : st = [b];

 

3번째 문자일때 t[3] = b , st.peek() = bt[3] 와 st.peek() 비교 -> pop -> 결과 : st = [];

 

4번째 문자일때 t[4] = a , st.peek() = null

t[4] 와 st.peek() 비교 -> push -> 결과 : st = [a];

 

5번째 문자일때 t[5] = a , st.peek() = a

t[5] 와 st.peek() 비교 -> pop -> 결과 : st = [];

 

위와 같은 과정을 거치게되고 문자열 baabaa는 결국 모두 제거되게 된다.

그리고 참고로 peek()값을 null을 반환할수 없기 때문에 !st.isEmpty 조건을 필요로 하게된다. 

 

자세한 내용은 풀이를 보고 생각해보자.

 

---

풀이

import java.util.Stack;

public class Solution {
	public static int solution(String s) {
		int answer = -1;
		Stack<Character> st = new Stack<Character>();//스택 생성

		/* toCharArray()를 사용해 문자열을 char 배열로 넣어준다.
		 * 문자 배열의 0번째~마지막까지 스택의 top과 비교하여 같다면 pop을
		 * 다르다면 push를 해준다.
		 */
		for(char t:s.toCharArray()) {
			if(!st.isEmpty() && st.peek()==t) {st.pop();}
			else {st.push(t);}
		}
		
		//스택 비어있으면 모두 제거된것, 다른경우는 모두 제거된거 아님.
		if(st.isEmpty()) {answer=1;}
		else {answer=0;}
		return answer;
	}
}

 

---

마치며

이번 문제는 앞서 말했듯 구현보다는 얼마나 효율적으로 코드를 작성하느냐가 어려운 문제라고 생각한다. 단순하게 생각하고 문제를 쉽게 바라보는건 좋지만 더 효율적으로 하기위해선 어떻게 해야하는지 충분한 고민을해 보는게 좋을꺼라 생각한다.

그리고 설명 잘못했는데 뭐,, 코드를 보면 설명에 비해 간단하기 때문에 모두 알아볼꺼라 생각한다.