[프로그래머스] (lv.2) 올바른 괄호 (java)

<문제>

https://school.programmers.co.kr/learn/courses/30/lessons/12909

<나의 풀이>

import java.util.Stack;

class Solution {
       static boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        // 1. toCharArray()를 이용하여 forEach로 돌리면 깔끔.
        for (char ch : s.toCharArray()) {
        // 2. 분기 처리의 기준을 ch로 잡아 효율성을 높임.
            if (ch == '(') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;
                else stack.pop();
            }
        }
        return stack.isEmpty();
    }
    }

<실패한 풀이>

import java.util.Stack;

class Solution {
    static boolean solutionTimeOver(String s) {
    // 1. 주어진 문자열이 ) 부터 시작하거나 홀수일 때
        if (s.charAt(0) == ')' || s.length() % 2 != 0)
            return false;
        else {
            Stack<Character> stack = new Stack<>();
            for (char ch : s.toCharArray()) {
                if (stack.isEmpty()) stack.push(ch);
                else if (stack.peek() == '(' && ch == ')') stack.pop();
                else stack.push(ch);
            }
            return stack.isEmpty();
        }
    }
 	}

처음엔 이 코드로 풀었는데 효율성테스트 2번에서 자꾸 걸려서 코드를 리팩토링하고 통과했다.
아무래도 분기처리에서 걸린 것 같다.
s의 길이가 100,000 까지라서 분기처리가 많으면 불리한가.. 싶다.
사실 두 코드 다 시간복잡도는 O(n)인데 .. ㅠ 그래서 분기문을 바꿔줬더니 통과했다.
분기문을 너무 많이 타면 불리하구나. 분기문을 더 효율적으로 짜도록 개선해나가야겠다.

<다른사람 풀이>

import java.util.Stack;

class Solution {
    static boolean solution(String str) {
        int cntUnpair = 0;
        for (char ch : str.toCharArray()) {
            cntUnpair += ch == '(' ? 1 : -1;	// 아 삼항연산자!
            if (cntUnpair < 0) return false;
        }
        return cntUnpair == 0;
    }
 	}

질문하기에서 발견한 좋은 풀이
질문 내용 또한 효율성테스트에서 자꾸 틀린다는 내용이었다.
Stack에 '(' 하나의 문자만 누적된다면 자료구조를 사용하지 않고 int변수에 갯수만 +/- 시키는 것이 유리하다고 조언해주셨다.
코드의 구조도 깔끔하고 배울 점이 많아서 첨부.

import java.util.Stack;

class Solution {
    static boolean solution(String str) {
        boolean answer = false;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            }
            if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                break;
            }
        }
        if (count == 0) {
            answer = true;
        }

        return answer;
    }

 	}

이 풀이는 stack을 쓰지 않고 cnt로만 풀어서 좋은 아이디어라 가져왔다.

<핵심 개념>

Stack인가..?

<피드백>

한 가지 풀이에만 매몰되지 말자. 보통 괄호 문제같은 경우엔 stack을 이용한 경우가 많아서 이번에도 그렇게 풀었지만 손에 익은 풀이가 언제나 해답이 되는 건 아니란 걸 깨달았다.
게다가 다른사람의 풀이에 두 번째 처럼 stack을 사용하지 않고도 풀 수 있는 방법은 많으니
다른 사람의 풀이를 참고하며 더 좋은 코드를 짤 수 있도록 노력하자.

삼항연산자.. 맛깔나게 써보도록