[프로그래머스] 짝지어 제거하기 (Java)

🔗 문제 링크

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

👨🏻‍💻 ArrayList로 작성한 코드 (효율성 테스트 실패)

import java.util.*;
class Solution {
    public int solution(String s) {

        List<Character> list = new ArrayList<>();
        for (char i : s.toCharArray())
            list.add(i);
        
        boolean isChanged = true;
        
        while (isChanged) {
            isChanged = false;
            for (int i=0; i< list.size()-1; i++){
                if (list.get(i) == list.get(i+1)){
                    list.remove(i);
                    list.remove(i); 
                    // i번째 데이터를 삭제하면 i+1이 i번째로 바뀌기 때문에 i를 두번 제거
                    isChanged = true;
                }
            }
        }
        
        if (list.size() == 0)
            return 1;
        return 0;

    }
}

👨🏻‍💻 StringBuilder로 작성한 코드 (효율성 테스트 실패)

import java.util.*;
class Solution {
    public int solution(String s) {

        StringBuffer str = new StringBuffer(s);
        
        
        boolean isChanged = true;
        
        while (isChanged) {
            isChanged = false;
            for (int i=0; i< str.length()-1; i++){
                if (str.charAt(i) == str.charAt(i+1)){
                    str.delete(i, i+2); 
                    isChanged = true;
                }
            }
        }
        
        if (str.length() == 0)
            return 1;
        return 0;

    }
}

👨🏻‍💻 Stack으로 작성한 코드 (테스트 성공)

import java.util.*;
class Solution {
    public int solution(String s) {

        Stack<Character> stack = new Stack<>();
        for (char i: s.toCharArray()) {
            if ((stack.size() >= 1) && (stack.peek() == i))
                stack.pop();
            else 
                stack.push(i);
        }

        if (stack.size() == 0)
            return 1;
        
        return 0;

    }   
}

📝 결론

초기 문제를 풀 때 String타입의 문자열을 character타입으로 하나씩 ArrayList에 넣은 뒤에 for문을 돌려가며 같은 i번째와 i+1번째의 수가 같으면 두 데이터를 삭제하는 방법으로 문제를 풀었다. 하지만 효율성 실패가 나와 StringBuilder방법으로도 변환하여 풀어봤으나 효율성 실패로 동일한 결과가 나왔다.

효율성이 낮게 나온 이유는 크게 2가지로 볼 수 있었다.

• 첫번째 이유로는 ArrayList의 경우 초기나 중간값을 remove할 경우 그 공간을 채우기 위해 내부적으로 뒤에 위치한 데이터들이 한칸씩 당겨지게되는 낭비가 발생한다는 사실이다. (StringBuilder의 delete()메서드가 동작을 하였을 때 내부적으로 어떻게 동작하는지는 잘 모르겠으나 코드 결과를 보았을때 ArrayList와 비슷한 것 같았다.)
• 두번째 이유는 for문에서 모든 문자열 비교를 하며 중복 문자들을 삭제하는 작업을 변경이 없을 때까지 while문으로 반복하여 수없이 많은 연산을 하게되는 낭비가 발생하게된다.

그래서 새로 생각한 방법은 stack이다.
데이터를 먼저 넣고 for문을 시행하는 것이 아닌 data가 들어갈 때마다 최상단에 위치한 data와 넣으려는 data를 비교하고 pop 또는 push를 수행하는 방법을 하였더니 코드가 무사히 통과되었다.

Stack stack = new Stack<>();
stack.peek(); -> 최상단 값 return
stack.push(data) -> data를 추가
stack.pop() -> 최상단 data를 삭제
stack.clear(); -> stack 초기화