2023-04-15 짝지어 제거하기

Summary

프로그래머스 “짝지어 제거하기”

고민이 필요했던 부분

문자열 s 의 길이가 최대 1,000,000 이므로 완전 탐색이 아닌 효율적인 방법이 필요하다. 문자열 s 를 순차적으로 순회한다고 할 때, 현재 돌고 있는 문자와 가장 마지막에 등장한 문자 간의 반복적인 비교가 필요하므로 이를 효율적으로 하기 위해서는 “스택” 을 잘 활용하는 것이 좋겠다고 생각하였다.

해결한 방법

  • 문자열 s 를 순차적으로 순회하면서
    1. 만약 스택 변수 st 가 비어있거나, 가장 최근에 삽입된 문자와 현재 순회하는 문자가 다르다면 현재 문자를 st 에 추가
    2. st 의 가장 마지막 문자와 현재 문자가 같다면 이 둘을 짝지으면 되므로 st 의 가장 마지막 문자를 pop()
    3. 최종적으로, 문자열 s 를 모두 순회했을 때 st 에 들어있는 문자가 있다면 짝지어서 모두 제거하지 못한 것이므로 0을, 비어있다면 모든 수를 짝지은 것이므로 1 을 리턴

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import java.util.Stack;

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

Python

1
2
3
4
5
6
7
8
9

def solution(s):
    st = []
    for ch in s:
        if st and st[-1] == ch:
            st.pop()
        else:
            st.append(ch)

    return 0 if st else 1

comments powered by Disqus