[PGM_12973] 짝지어 제거하기 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
Stack

 연속되는 문자열을 짝지어서 제거해주는 문제이다. 처음에 문제를 해결할 때 subString을 사용해서 붙이고 모든 문자열을 돌아도 괜찮다고 생각이 되어 그렇게 문제를 해결하였다. 그러나 효율성에서 점수를 받지 못하여, 새로운 방법을 고안하다가 스택을 사용해서 문제를 해결하게 되었다. (스택을 사용한게 효율이 더 좋은 이유는 String의 작업이 생각보다 많은 시간이 걸리기 때문이다.)

 

문자 두개를 확인하고 문자가 같으면 버리고, 다르면 스택에 넣는 방법으로 구현하였다.

1. 스택이 비어있는지 확인하고, 비어있으면 문자 하나를 넣어주고 다음 문자로 넘어간다.
2. 만약 스택이 비어있지 않다면, 그 문자를 꺼내고 지금 배열에서 포인트되어있는 문자와 비교한다.
   • 만약 같으면 다시 스택에 넣지 않고 다음 문자로 넘어간다.
   • 만약 다르면 다시 스택에 순서대로 넣어준다.(스택에 있던 문자를 먼저 넣고 그 다음 문자를 넣어준다.
3. 모든 문자를 확인할 때 까지 1번과 2번을 반복 시행한다.
4. 모든 문자를 확인하였다면 결과를 리턴한다.
   • 스택이 비어있으면 1
   • 스택이 비어있지 않으면 0

 

구현코드

package pgm_12973;

import java.util.Stack;

public class Solution {
    public int solution(String s) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if(stack.isEmpty()){
                stack.add(s.charAt(i)-'0');
                continue;
            }

            int front = stack.pop();
            int back = s.charAt(i) -'0';

            if(front == back)
                continue;
            stack.add(front);
            stack.add(back);
        }

        if (stack.isEmpty())
            return 1;
        return 0;
    }
}

 

시간복잡도

모든 문자열을 한번씩 확인하기 때문에 문자열의 크기 n이 된다. $O(n)$

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)