[프로그래머스-lv2 2017팁스타운]짝지어 제거하기

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

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

import java.util.*;
class Solution{
    public int solution(String s){
        int answer = 0;
        
        Stack <Character> stack = new Stack<>(); 
        
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            if(stack.isEmpty()){ //스택 비었으면 무조건 push
                stack.push(ch);
                continue;
            }
            
            if(stack.peek()==ch){ //마지막에 삽입한 글자와 같다면
                stack.pop(); // 스택pop
            }
            else{ // 마지막에 삽입한 글자와 다르다면
                stack.push(ch); //스택 push
            }
 
        }

        return stack.size()==0 ? 1 : 0;
    }
}

소요시간 : 10분

 

IDE 없이 푼 문제 중 유일하게 오타나 문법 오류 없이 통과했습니다ㅎㅎ

 

문자열의 길이가 1,000,000이하의 자연수이기 때문에

O(n^2)이면 무조건 터집니다! 

스택을 이용해서 O(n)으로 풀 수 있습니다.

 

만약 스택이 비어있다면 현재 글자를 push해줍니다.

만약 스택이 비어있지 않다면

   1. 마지막에 삽입한 글자와 현재 글자가 같다면 스택을 pop 해줍니다.

   2. 마지막에 삽입한 글자와 현재 글자가 다르다면 스택에 push 해줍니다.

 

마지막에 스택 사이즈를 확인해서 0이라면 모든 글자가 삭제된 것이기 때문에 1을 출력

스택 사이즈가 0이 아니라면 0을 출력해주면 됩니다.

 

끝~