[프로그래머스] 올바른 괄호 / Java

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

- "()()" 또는 "(())()"는 올바른 괄호입니다.

- ")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

"(" 또는 ")"로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

제한사항

- 문자열 s의 길이 100,000 이하의 자연수

- 문자열 s는 "(" 또는 ")" 로만 이루어져 있습니다.

 

 

테스트 케이스

 

풀이

성공 코드 바로가기

 

실패 코드 1

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        String[] strArr = s.split("");
        int flag = 0;
        for(String str : strArr){
            flag += str.equals("(") ? 1 : -1;
            if(flag < 0){
                answer = false;
                return answer;
            }
        }
                
        if(flag != 0) {
            answer = false;
        }
        return answer;
    }
}

실패코드1 결과

 

 모든 테스트는 통과했지만 효율성 테스트 2개 모두 통과하지 못했다. 고민을 해본 결과 잘못된 괄호로 만들어진 문자열이면서 길이가 100,000일 때 계속 for 문을 반복하고 있기 때문이 아닐까라고 생각했다. 그래서 for문을 빼고 만들 수 있지 않을까 하고 생각해서 코드 2를 작성했다.

 

 

실패 코드 2

class Solution {
    boolean solution(String s) {
        int len = s.length();
        
        if(len % 2 != 0){ 
            return false;
        }
        if(s.substring(0,1).equals(")") || s.substring(len-1).equals("(")) { 
            return false;
        }
        if(len - s.replace(")","").length() != len/2){
            return false;
        }
        if(len - s.replace("(","").length() != len/2){
            return false;
        }
        String[] strArr = s.split("");
        int flag = 0;
        for(String str : strArr){
            flag += str.equals("(") ? 1 : -1;
            if(flag < 0){
                return false;
            }
        }
        
        
        return true;
    }
}

실패코드2 결과

 

 잘못된 괄호를 가진 긴 문자열을 앞부분에서 잡아주니 효율성 2번은 통과할 수 있었다. 아무리 생각을 해봐도 모르겠어서 구글에 효율성 테스트 관련해서 찾아봤는데.. 아예 접근 방식을 바꿔보라는 글을 보고 뇌를 빼보자 하고 생각했다. 그렇게 탄생한 실패 코드 3...

 

 

실패 코드 3

class Solution {
    boolean solution(String s) {
        int len = s.length();
        
        for(int i=0; i<len; i++){
            String str = s.replace("()", "");
            if(str.equals("")){
                return true;
            }
            s = str;
        }
                        
        if(!s.equals("")) {
            return false;
        }
        return true;
    }
}

실패코드3 결과

 정말 생각 없이 코딩했더니 실패 코드 1과 다를 게 없는 코드가 만들어졌다.. 이제와 보니 할 말이 없다..

 

 

 

성공 코드 1

class Solution {
    boolean solution(String s) {
        int len = s.length();
        
        if(len % 2 != 0){ 
            return false;
        }
        if(s.substring(0,1).equals(")") || s.substring(len-1).equals("(")) { 
            return false;
        }
        if(len - s.replace(")","").length() != len/2){
            return false;
        }
        if(len - s.replace("(","").length() != len/2){
            return false;
        }
                
        int flag = 0;
        for(int i=0; i<len; i++){
            flag += s.charAt(i) == ')' ? -1 : 1;
            if(flag < 0){
                return false;
            }
        }
        
        
        return true;
    }
}

성공 결과

 정확성 테스트, 효율성 테스트에서 가장 높은 점수를 받은 실패 코드 2를 바꿔보자는 생각이 들어서 계속 고민했다. 

그러다 보니 저번에 다른 문제를 풀 때 String을 Char형 array로 만들었던 게 생각났다. 문자열 하나하나를 잘라서 비교하는 건데 굳이 String 형으로 비교할 필요가 있을까 라는 생각이 들었다. 생각은 들었지만 설마 고작 이거 하나로..라는 생각으로 했는데.. 됐다..

 

 

후기

 문제를 처음 읽었을 때 그렇게 어렵지 않게 느껴졌는데 설마 효율성 테스트 때문에 코드를 3번이나 바꿀지 몰랐다. 평소에 개발을 하면서 메모리, 속도, 효율성은 거의 고려하지 않아서 타입은 익숙한 String, int를 남발했는데.. 이 문제로 인해서 생각이 바뀌었다.

 오늘의 느낀 점은 대학생 C언어 수업 시간에 강교수님께서 하셨던 말씀으로 마무리해야지.

 큰 수를 사용하지 않는 프로그램의 경우(ex. 계산기) int보다 byte, short 타입의 변수를 사용하는 게 적합할 수 있다. 현재엔 메모리가 충분해서 괜찮지만 메모리가 부족했던 옛날에는 타입 하나하나가 크게 작용했다.  

 

---

 

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

프로그래머스