[프로그래머스] 괄호 회전하기 (Java)

카테고리

자료구조

나만의 카테고리

자료구조 - Stack

문제 링크

programmers.co.kr/learn/courses/30/lessons/76502

코딩테스트 연습 - 괄호 회전하기

요점

• Stack을 사용하여 올바른 괄호를 판단하는 로직을 구현할 수 있다.

참고 지식

• Java Stack

풀이 (Java)

import java.util.*;

class Solution {
    private int answer = 0;
    
    public int solution(String s) {
        Stack<String> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            stack.clear();
            s = s.substring(1, s.length()) + s.charAt(0);
            
            for (int j = 0; j < s.length(); j++) {
            	// String targetString = "" + s.charAt(j); 사용시 시간이 평균 10%정도 늦어진다.
                String targetString = s.substring(j, j+1);
                
                if (stack.empty()) {
                    stack.push(targetString);
                    continue;
                }
                
                if (")".equals(targetString)) {
                    if ("(".equals(stack.peek())) stack.pop();
                    continue;
                } else if ("}".equals(targetString)) {
                    if ("{".equals(stack.peek())) stack.pop();
                    continue;
                } else if ("]".equals(targetString)) {
                    if ("[".equals(stack.peek())) stack.pop();
                    continue;
                }
                
                stack.push(targetString);
            }
            
            if (stack.empty()) {
                answer++;
            }
        }
        
        return answer;
    }
}

올바른 괄호를 판단하는 문제가 나온다면 Stack을 사용하는 방법이 가장 먼저 떠오릅니다. 그래서 문제를 이해하고 로직을 떠올리는데 오랜시간이 걸리지 않은거 같습니다. 로직 전체는 간단합니다.

• 모든 문자에 대해서 아래 내용을 반복한다.
• 문자열의 맨 앞 문자를 뒤로 보낸다.
• 위에서 생성된 새로운 문자열에 대해 올바른 괄호를 판단한다.
• 올바르다면 answer를 1 증가시킨다.

결과는 성공적이지만 어떻게 하면 효율성을 더 높일 수 있을까 고민하다가 targetString을 뽑아낼 때 + 방식과 substring을 이용하는 방식 중에 어떤게 더 나을지 궁금했습니다.

 

+ (내부적 StringBuilder) 사용

+ 사용

String.substring() 사용

substring 사용

위에서 보듯이 공간효율적으로는 거의 차이가 없지만 시간효율적으로는 그래도 의미적인 차이가 있습니다. substring 내부에서는 배열로 변환해서 처리하고 + 는 내부적으로 StringBuilder를 사용합니다. 그래서 배열 할당이 더 오래 걸릴 줄 알았는데 아니였네요 ㅎㅎ

---

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!