프로그래머스(JAVA) - level2(짝지어 제거하기)

문제정리

문자열 S에서 같은 알파벳이 2개 붙어있는 짝을 찾고, 제거한 뒤 앞뒤로 문자열을 이어 붙인다.
성공적으로 수행할 수 있으면 1, 아닐 경우 0

처음 작성한 코드

class Solution {
    public int solution(String s) {
        while (!s.equals("")) {
            String[] str = s.split("");
            for (int i = 0; i < str.length - 1; i++) {
                if (str[i].equals(str[i + 1])) {
                    s = "";
                    for (int j = 0; j < str.length ; j++) {
                        if (i == j) {
                            j++;
                            continue;
                        }
                        s += str[j];
                    }
                    break;
                }
                if(i == str.length -2){
                    if(!s.equals("")){
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
}

 

코드를 평소와 같이 익숙한 형태와 문법으로 해결하려고 했으나

 

시간초과..... 아무리 다르게 생각을 해도 다른 해결법이 생각이 나지않아 구글링해서 다른 사람들 코드 참고해봄..;;

하긴 반복문이 삼중으로 있으니 시간이 오래 걸릴수밖에..반복문말고도 다른 해결책으로 생각을 바꿔야할듯

최종코드

class Solution {
    public int solution(String s) {
        int answer = 0;
        Stack<Character> stack = new Stack<>(); // 스택 생성 (문자 저장)

        for(char c : s.toCharArray()){ // 문자열의 각 문자를 하나씩 확인
            if(stack.size()>0 && stack.peek() == c){ // 스택이 비어있지 않고, 스택의 맨 위 문자가 현재 문자와 같다면 true
                stack.pop(); // 스택의 맨 위 문자 제거 
            }else{
                stack.push(c); // 쌍을 이루지 않으면 현재 문자를 스택에 추가 
            }
        }
        if(stack.isEmpty()){ // 반복문 종료 후 스택이 비어 있으면 
            return 1; // 문자열이 완전히 제거되어있음을 표시 
        }
        return answer; // 기본값 0 반환
    }
}

 

시간은

 

Stack이란?

Stack은 데이터를 쌓아 올리는 자료구조

LIFO (Lask In, First Out) -> 나중에 들어간 데이터가 먼저 나온다.

• push : 스택에 데이터를 추가
• pop : 스택의 가장 위 데이터를 꺼냄
• peek : 스택의 가장 위 데이터를 확인 (꺼내지는 않음)