개발 일기

프로그래머스 레벨 2 짝지어 제거하기 (JAVA) 본문

알고리즘/programmers

프로그래머스 레벨 2 짝지어 제거하기 (JAVA)

dev-jo 2021. 7. 10. 22:59

이번에는 2 레벨에 도전해 보았다

 

 

푼 문제!

 

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

 

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

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙

programmers.co.kr

 

 

모든 코드는 GitHub 에 올려놓았다.

 

이 문제는 Stack을 이용해야 한다고 들어서

 

Stack을 어떻게 이용해야 풀 수 있을지에만 생각하다가  ( Stack 처음 써본다.. )

 

쉬운 거를 놓치고 말았다

 

간단하게!

 

0번째 index부터 값을 추가해가며 비교해 주면 된다.

 

ex) baabaa 라면

 

0번째부터

 

Stack에 b를 넣고 다음 a값과 비교하고

 

같지 않다면 Stack에 a를 추가

 

같다면 pop으로 현재 들어있는 b를 제거해준다

 

이거는 Stack 말고 ArrayList , LinkedList , StringBuilder로 풀 수 있다

 

처음에는 StringBuilder로 풀다가 시간 초과가 나서 못 풀었지만 문제의 접근을 다르게 하면

 

Stack 말고도 다른 거로도 풀 수 있는 문제다.

 

모든 방식의 코드를 올려놓겠다..

 

Stack

   //Stack
    public static int solution(String s) {

        Stack<String> stringStack = new Stack<>();
        for(int i=0; i<s.length(); i++) {

            if(!stringStack.isEmpty()) { // 스택이 비어있지 않으면
                if(stringStack.peek().equals(String.valueOf(s.charAt(i)))) { // 첫 값은 0번쨰 index 값이 들감  0 , 1 비교  -> 0 1 같다면 둘다 삭제해야함 스택에서 0 번만 삭제시켜줌
                    stringStack.pop();
                    continue;
                }
            }

            stringStack.push(String.valueOf(s.charAt(i))); // 값넣어주기

        }

        return stringStack.size() == 0 ? 1 : 0;
    }

 

 

LinkedList

//LinkedList
    public static int solution2(String s) {

        LinkedList<String> stringLinkedList = new LinkedList<>();
        for(int i=0; i<s.length(); i++) {

            if(!stringLinkedList.isEmpty()) {
                if(stringLinkedList.get(stringLinkedList.size() -1).equals(String.valueOf(s.charAt(i)))) {
                    stringLinkedList.remove(stringLinkedList.size() -1);
                    continue;
                }
            }

            stringLinkedList.add(String.valueOf(s.charAt(i)));
        }

        return stringLinkedList.size() == 0 ? 1 : 0;

    }

 

ArrayList

 

//ArrayList
    public static int solution3(String s) {

        ArrayList<String> arrayList = new ArrayList<>();
        for(int i=0; i<s.length(); i++) {

            if(!arrayList.isEmpty()) {
                if(arrayList.get(arrayList.size() -1).equals(String.valueOf(s.charAt(i)))) {
                    arrayList.remove(arrayList.size() -1);
                    continue;
                }
            }

            arrayList.add(String.valueOf(s.charAt(i)));
        }

        return arrayList.size() == 0 ? 1 : 0;

    }

 

StringBuilder

 

//builder
    public static int solution4(String s) {

        StringBuilder builder = new StringBuilder();

        for(int i=0; i<s.length(); i++) {

            if(builder.length() != 0) {
                if(builder.charAt(builder.length() -1) == s.charAt(i)) {
                    builder.deleteCharAt(builder.length() -1);
                    continue;
                }
            }

            builder.append(s.charAt(i));

        }

        return builder.length() == 0 ? 1: 0;
    }

 

 

놀랍게도.. StringBuilder가 속도가 제일 빨랐다..

 

 

스택 테스트

 

StringBuilder 의 테스트

 

 

문제의 접근을 다양하게 할 수 있는 사고를 길러야겠다..