프로그래머스 / 짝지어 제거하기(Java)

문제 설명

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

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

b aa baa → bb aa → aa →

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

제한사항

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

---

입출력 예

 

s	result
baabaa	1
cdcd	0

---

조건 1 : 같은 글자가 연속 될 경우 두 글자 모두 제거한다.

조건 2 : 앞에서 부터 진행한다.

조건 3 : 모두 짝지어 없어질 경우 1 리턴, 아닐 시 0 리턴

 

내가 생각한 해결 방법

Stack에 넣은 후 가장 위에 있는 원소와 다음 원소를 비교하여 같으면 가장 위의 원소를 제거하고 다를 경우 다음  삽입한다. 

 

처음에는 받은 문자열을 Split 함수를 사용하여 문자 배열에 담아서 비교하려 했다. 

	public static  int solution(String s)
	{
		Stack<String> st = new Stack<>();
		String[] str = s.split("");
		for(int i=0; i<str.length; i++){
			
			if(st.isEmpty()) {
				st.push(str[i]);
			}else if(st.peek().equals(str[i])) {
				st.pop();
			}else {
				st.push(str[i]);
			}
		}
		
		if(st.isEmpty()) return 1;
		return 0;

	}

 

split 함수를 이용한 문자열 나누기

정확성 테스트는 모두 통과하였지만, 효율성 테스트에서 딱 한 가지 테스트만 통과하지 못하고 시간 초과를 하였다. 

한참 고민하다가 다른 방법으로 문자열을 나눠보려 Stringtokenizer나 substring을 시도했지만 쉽지 않았는데

 

진짜 어이없고 간단한 방법으로 시간을 약 1/2 가까이 시간을 단축하였다. 그것은 배열에 담지 않고 substring을 사용하여 바로바로 비교하는 것

 

	public int solution(String s)
	{
		 Stack<String> st = new Stack<>();
		for(int i=0; i<s.length(); i++){
			
			if(st.isEmpty()) {
				st.push(s.substring(i,i+1));
			}else if(st.peek().equals(s.substring(i,i+1))) {
				st.pop();
			}else {
				st.push(s.substring(i,i+1));
			}
		}
		
		if(st.isEmpty()) return 1;
		return 0;
    }

 

매번 substring으로 자르는 것이 미리 문자 배열에 나눠놓고 비교하는 것보다 훨씬 빠르다. 약 1/2...

 

왜 그럴까? 배열에 담아두는 것이 탐색에 더 효율적이지 않나? 왜?????????? 배열의 뒤쪽에 담긴 원소를 탐색하는 것은 앞에서부터 차례대로 하기 때문에 시간이 더 오래 걸리기 때문인가? 흠 그런 거 같기도 하네

 

 

아시는 분..