[알고리즘 스터디 2주 차(2)] 올바른 괄호

 

 

나의 로직 (70% + 구글링 30%)

• 시작과 끝이 ()이 아니면 다 false
• true인 값들은 배열에 담아서 반복문 돌리기 
• 배열에 담긴 값들을 조건 검사하기

package programmers;

public class Level2_12729 {
    class Solution {
        boolean solution(String s) {
            boolean answer = true;

            int open = 0;
            if(s.charAt(0)==')') return false;

            for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='('){
                    open++;
                }else{
                    if(open<=0) return false;
                    open--;
                }
            }

            if(open!=0)return false;
            return answer;
        }
    }
}

 

풀이 1

Stack 이용

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        
        final int len = s.length();
        Stack <String> stack = new Stack<>();
        
        for(int i=0;i<len;i++){
            String p = s.substring(i,i+1);
            
            if(p.equals("(")){
                stack.push(p);
            }else if(p.equals(")")){
                if(stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

 

String a = "A"; object

char b = 'b'; primitive(2byte int)

 

"A". equals("B")  vs 'a' == 'b' < 속도는 당연히 이게 빠르다.

 

 

풀이 2

substring 대신 charAt으로 변경해보자

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        
        final int len = s.length();
        Stack <Character> stack = new Stack<>();
        
        for(int i=0;i<len;i++){
            char p = s.charAt(i);
            
            if(p=='('){
                stack.push(p);
            }else {
                if(stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

 

풀이 3-1

Stack을 사용할 필요가 없는 이유

위의 풀이로는 스택에 '('만 들어간다. 왜?

')'일 경우 pop 되어서 지워지기 때문이다.

즉, pop으로 나온 결과물을 활용하지 않기 때문에 굳이 Stack을 사용할 필요가 없게 된다.

 

따라서 기존의 Stack이 있던 자리에 int count를 선언하고, count의 값에 따라 0일 경우 true를 아니면 false를 반환하는 로직으로 변경해도 같은 결과가 나온다.

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        
        final int len = s.length();
        int count = 0; 
        
        for(int i=0;i<len;i++){
            char p = s.charAt(i);
            
            if(p=='('){
                count++; // 열린 괄호일 때 count 증가
            }else {
                if(count == 0) return false; // 닫힌 괄호부터 시작했다면 count가 0이기 때문에 fasle를 반환
                count--; // 닫힌 괄호일 때 count 감소
            }
        }
        return count == 0;
    }
}

 

풀이 3-2

for-each문을 사용했을 때

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        
        final int len = s.length();
        int count = 0;
        
        for(char p : s.toCharArray()){

            if(p=='('){
                count++;
            }else {
                if(count == 0) return false;
                count--;
            }
        }
        return count == 0;
    }
}

 

 

풀이 4

else 쓰지 마라!

OOP 연습, 클린코드를 공부할 때 언급된다고 한다.

else를 쓰지 않는 것만으로도 기존의 코드에 비해 가독성이 좋아졌다.

 

=> 코드를 잘 만드는 방법

=> 추천 책 : 클린코드, 이펙티브 자바(어떻게 하면 자바스럽게 짜는 걸까?)

class Solution {
    boolean solution(String s) {

        int count = 0;
        
        for(char p : s.toCharArray()){

            if(p=='('){
                count++;
                continue;
            }
            
            if(count == 0) return false;
            count--;
        
        }
        return count == 0;
    }
}

 

왼쪽 : Stack  O, String (풀이1) 오른쪽 : Stack X, Char (풀이 4)

 

풀이 1과 풀이 4 모두 정답으로 인정되지만, 효율성을 비교하면 정말 많은 성능 차이가 난다는 것을 알 수 있다.

 

 

자료구조

Stack

따로 정리하여 포스팅 할 예정! 

 

Array

값을 여러개를 다루기 위해 사용함

장 : 인덱스만 있으면 빠르게 검색 가능

단 : 하지만, 크기 조절이 불가능함

 

List

연달아서 있지 않아도 하나처럼 사용할 수 있는 방법!

장 : 멀리 떨어져 있어도 값이 늘어나거나 줄어들 수 있다.

단 : 링크가 엉망으로 되어있으면 많은 비용이 듦 (인덱스로 값을 뽑아오는 것은 느리다)

 

둘 다를 만족 할 수 있는 방법

Array와 List를 섞어서 만든 개념이 바로 Hash 함수! 

Hash값 == 인덱스 

Hash값만 알면 빠르게 찾을 수 있다.

Key 값이 있고 value가 여기에 Mapping 된다.

 

 

배운 점

- 한 글자 뗄 때는 String으로 떼는 것보다 char로 떼는 것이 훨씬 더 좋다. 불필요한 연산이 줄어들기 때문이다.

 

- Object를 primitive로 바꿨을 뿐인데도 성능면에서 상당히 많은 차이가 난다.

 

- 이 문제 풀이를 찾아봤을 때 Stack을 사용한 풀이법이 대부분이라서 기가 죽었는데 (?) 풀이 방법은 많으니까 기죽지 말고 내가 할 수 있고 소화 가능한 범위에서 차근차근 풀어보자

 

- 클린 코드를 위해 노력하자

불필요한 것 쓰지 말고

간결하게 유지하고

읽기 쉽게 만들자

변수 이름 잘 짓자