짝지어 제거하기

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

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

 

처음엔 String을 ArrayList로 변환 후 끝에서 부터 문자열을 삭제하는 방법을 사용했다.

요소를 삭제한 후에는 인덱스를 다시 설정해주어야 하기 때문에 i+2를 해주었다.

    private static int solution1(String s) //효율성 통과X
    {
        ArrayList<Character> arr = new ArrayList<>();
        for (int i = 0; i < s.length(); i++)
        {
            arr.add(s.charAt(i));
        }

        for (int i = arr.size()-1; i > 0; i--)
        {
            if (arr.get(i).equals(arr.get(i-1)))
            {
                arr.remove(i);
                arr.remove(i-1);
                i = Math.min(i+2, arr.size());
            }
        }

        return arr.isEmpty() ? 1 : 0;
    }

코드를 제출했고 당연히 효율성에서 통과를 못했다.

문자열 길이가 최대 1,000,000인데 n제곱으로 풀 생각을 하다니 ㅋㅋㅋㅋㅋ

 

원본 데이터를 그대로 사용해야 효율성에 통과하겠다 싶었고 인형뽑기 문제처럼 Stack으로 풀면 될 것 같았다.

결과는 정확성과 효율성 모두 통과되었다.

    private static int solution2(String s) //효율성 통과
    {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++)
        {
            if (stack.isEmpty())
            {
                stack.push(s.charAt(i));
            } else {
                if (stack.peek() == s.charAt(i))
                {
                    stack.pop();
                } else {
                    stack.push(s.charAt(i));
                }
            }
        }
        return stack.isEmpty() ? 1 : 0;
    }