5-1 올바른 괄호

유태형·2022년 5월 24일

Java 알고리즘 프로그래머스

알고리즘 - Java

목록 보기

11/32

출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다.

문제

문제 분석

괄호가 알맞은 순서와 갯수를 가지고 있는지 확인하는 문제입니다. 검사하는 동안 (가 항상 더 많거나 같아야 하며, 마지막은 항상 (와 )의 갯수가 일치해야 합니다.
)가 더 많을 경우 괄호가 열리지도 않았는데 닫힌게 존재한다는 의미이므로, 바로 뒤에 (가 추가적으로 더 있어도 올바른 괄호가 아닙니다.

풀이

내가 풀었던 풀이

import java.util.*;

class Solution {
    boolean solution(String s) {
        // 시작은 (와 )의 갯수가 같다고 가정 == 0
        int answer = 0;
        //문자열에 존재하는 괄호들을 각각 배열의 요소로 저장
        Queue<String> queue = new LinkedList<>(Arrays.asList(s.split("")));
        //Queue에 존재하는 모든 괄호 비교할때 까지
        while(!queue.isEmpty()){
            // "("나오면 +1 ")"나오면 -1
            if(queue.poll().equals("(")) answer++;
            else answer--;
            //앞에서 부터 차례로 제거하면서 괄호비교, )가 (보다 먼저나오면 false이므로
            // -1되면(")"가 "("보다 많은 시점이 있다면) 무조건 false
            if(answer < 0)
                return false;
            // 짝이 없는 '('수가 큐에 남은 요소수보다 더 많을 때 false
            if(answer > queue.size())
                return false;
        }
        return answer == 0 ? true : false;
    }
}

런타임에 오류를 발생시키거나 연산이 잘못된 알고리즘은 아니지만, 효율성이 떨어지던 알고리즘입니다. 채점결과 효요율성 테스트가 2개다 시간초과났습니다.
아마 추측컨데 문자열을 String배열로 만드는 과정에서 시간을 많이 소비했던 것 같습니다.
하지만 int answer로 +1 과 -1을 하며 괄호의 갯수를 비교하는건 상당히 좋은 아이디어 같았습니다.

강의에서의 풀이

import java.util.*;

class Solution {
    boolean solution(String s) {
        int stack = 0;
        //한 단어씩(char)
        for(char c : s.toCharArray()){
            if(c == '(') stack++; //'('면 +1
            else{ //')'면
                if(stack == 0) return false; //'('보다 먼저 나왔다면 거짓
                stack--; //-1
            }
        }
        return stack == 0; //'('와 ')'의 갯수가 동일한지
    }
}

Queue 컬렉션을 사용하지 않고 문자열.toCharArray()로 문자 배열을 이용하였습니다. 저의 풀이중 int answer방법이 괜찮은 방법이 맞았는지 강의에서도 +1 -1을 하여 갯수를 비교하였습니다.
문자열 -> 문자열 배열은 시간초과가 났었지만, 문자열 -> 문자 배열은 상당히 빠른 연산속도를 보여주었습니다. 가능하면 String.split("") 보다는 String.toCharArray()를 이용하여야 겠습니다.