[Level2] 짝지어 제거하기 답안 및 풀이

◇ 문제 설명

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

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

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

 

◇ 제한 조건

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

 

◇ 입출력 예시

s	result
baabaa	1
cdcd	0

 

◇ 입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

 

◇ 초기 내용

※ [출처] 프로그래머스-코딩테스트 연습-문제명

※ 초기 내용을 참고하여 문제에 맞는 코드를 작성하세요.

class Solution {
    public String solution(String s) {
        String answer = "";
        return answer;
    }
}

 

---

◇ 풀이 과정

문제는 Stack알고리즘을 이용하여 구현하였다.

1. Stack객체를 Character형으로 하나 생성한다.
2. Stack객체에 s의 첫번째 문자를 저장한다.(반복문을 1부터 시작할 것이기 때문)
3. 반복문을 1부터 s의 길이만큼 반복한다(i)
   1. 만약, Stack객체에 저장된 값이 하나도 없다면 객체에 s.charAt(i)값을 추가한다.
   2. 저장된 값이 있다면, Stack객체의 마지막값과 현재 s.charAt(i)를 비교한다
   3. 비교한 값이 같다면 같은 알파벳이므로 Stack객체의 마지막 값을 삭제한다.
   4. 비교한값이 다르다면 현재 s.charAt(i)를 Stack객체에 저장한다.
4. 위의 내용을 모두 반복 한 후, Stack객체에 남은 값이 0이라면 answer에 1을 저장하고
   0이 아니라면 모두다 짝지어진것이 아니므로 answer에 0을 저장후 반환한다.

 

◇  참고 사항

첫번째, Stack

• 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 Last In First Out(LIFO) 구조이다.
• java.util.Stack 패키지를 import 해야 사용이 가능하다.
• Stack<WrapperType> 변수명 = new Stack<>();의 형식으로 선언한다.
• 주요 메서드
  

  메서드명	사용방법	설명
  push	stack.push(value)	stack에 value를 추가
  pop	stack.pop()	stack에 마지막에 추가된 값을 반환 후 삭제
  clear	stack.clear()	stack의 모든 값을 삭제
  peek	stack.peek()	stack에 마지막에 추가된 값을 반환
  size	stack.size()	stack에 들어간 값의 개수를 반환
  empty	stack.empty()	stack이 비어있는지 확인

   

◇ 답안

import java.util.Stack;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        
        //Character를 담을 Stack객체 생성
        Stack<Character> stack = new Stack<>();
        
        //stack에 s의 첫번째 값 추가
        stack.add(s.charAt(0));
        
        //1~s.length()까지 반복문 실행
        for(int i = 1; i<s.length(); i++){
        	//만약, stack의 크기가 0이라면
            if(stack.size()==0){
            	//현재 문자(s.charAt(i))를 stack에 저장
                stack.push(s.charAt(i));
            }else{
            	//만약, stack의 마지막 값과 현재 값(s.charAt(i))이 같다면
                if(stack.peek()==s.charAt(i)){
                	//같은 알파벳이 2개 붙어있는 것이므로 짝지어 제거하기 위해
                    //pop메서드 사용
                    stack.pop();    
                }else{
                	//값이 다르다면 stack에 현재 값(s.charAt(i)) 추가
                    stack.push(s.charAt(i));
                }
            }
        }
        
        //반복문이 종료된 후, stack의 크기가 0보다 크다면
        if(stack.size()!=0){
        	//모두 짝지어진것이 아니므로 answer을 0으로 저장
            answer = 0;
        }else{
        	//모두 짝지어져 stack의 크기가 0이라면 answer을 1로 저장
            answer = 1;
        }
        
        return answer;
    }
}

 

◇ 실행결과

짝지어 제거하기 실행결과

 

◇ 출처

https://programmers.co.kr/learn/challenges

코딩테스트 연습