짝지어 제거하기

문제 이름 및 링크

짝지어 제거하기

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

 

출제 사이트

프로그래머스

 

문제유형 및 난이도

문제유형: 스택

난이도: Level2

 

코드 설명

문제를 보고 한 번의 순회에 끝내야 시간복잡도 내에 결과를 낼 수 있겠다 생각하였습니다.

고민해보니 애니팡 게임 처럼 같은걸 만나자마자 팡하고 터져서 없어지게하면 되지 않을까라는 생각을 했습니다.

스택을 이용하면 해당 아이디어가 구현되겠다라는 생각을 하게 되었습니다.

 

만약 스택이 비어 있으면 문자를 넣고 스택에 값이 있다면 제일 위의 값이 넣으려는 문자와 같은지 확인한 다음 같다면 삭제하는 알고리즘을 생각했습니다.

 

 

그 결과 나온 코드는 아래와 같습니다.

 

import java.util.*;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(stack.size()==0) stack.push(c);
            else {
                if(stack.peek()==c) stack.pop();
                else stack.push(c);
            }
        }
        return stack.size()==0 ? 1:0;
    }
}

 

한 번에 정확도와 효율성 검사 모두 통과하는 건 너무 기분이 좋습니다.