자바 - 프로그래머스 / 짝지어 제거하기

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

프로그래머스

LV 2

 

구현 방법

문자열의 길이 : 1,000,000이하의 자연수 조건을 통해 시간 복잡도를 고려하여 구현해야 한다.

 

<시간 초과 경우>

ArrayList로 구현 할 경우, remove() 함수가 O(n)의 시간 복잡도를 가지고, 두 짝을 찾는데에도 O(n)을 가지므로 

총 O(n^2)의 시간복잡도를 가지게 된다. 이런 경우, 시간초과가 발생한다.

또한 LinkedList로 구현 할 경우, remove() 함수는 O(1)을 가지지만 get()함수가 O(n)의 시간 복잡도를 가진다.  따라서 두 짝을 찾는 시간복잡도 O(n)까지 하여 총 O(n^2)의 시간복잡도를 가지게 된다. 이 경우 또한 시간초과가 발생한다.

 

<올바른 구현 - stack>

문자 두개가 같은 경우에는 stack에 넣지 않고, 다른 경우 stack에 값을 넣는다. 그 후 stack의 가장 위의 값과 현재 비교할 문자열의 문자를 비교하여 같은 경우 pop, 다른 경우 stack에 push 하여 구현한다.

이 경우, stack의 push와 pop은 O(1)의 시간 복잡도를 가지므로, 시간복잡도는 문자열의 문자를 하나씩 꺼낼 때의 O(n)만 가지게 된다.

 

코드

ArrayList 구현 - 시간 초과

import java.util.List;
import java.util.ArrayList;

class Solution
{
    public int solution(String s)
    {
        
        List<Character> sList = new ArrayList<Character>();
        
        for(char c : s.toCharArray()) {
            sList.add(c);
        }
        
        int start = 0;
        int end = 1;
        while(end < sList.size()) {
        
            if (sList.get(start) == sList.get(end)) {
                sList.remove(end);
                sList.remove(start);
                start = 0;
                end = 1;

            } else {
                start++;
                end++;
            }
        }
        
        
        if(sList.isEmpty())
            return 1;
        else
            return 0;
    }
}

 

stack 구현 

import java.util.Stack;

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

 

느낀 점

큰 범위는 시간 복잡도 계산 필수!

 

참고 블로그

https://www.grepiu.com/post/9

GrepIU