알고리즘 Stack 공부하기와 나의 고찰

정의

Stack.. 말그대로 스택, 위에 얹듯이 차곡 차곡 올리는 형태와 특징을 가진 자료구조를 의미.

 

Stack이라는 의미 때문에 직관적으로 의미는 1초만에 이해 될 것이다.

---

동작

동작은 3단계로 나뉜다

 

쌓기 -> push

빼기 -> pop

읽기 -> peek

 

동작도 매우 간단하다.

---

고찰

웹서비스를 위한 코드에서는 Stack이 유용할지도 모르겠다. 간단하니깐

그런데 알고리즘 문제를 푸는데, Stack을 쓴다?

그건 효율적이지 못할 가능성이 크다.

 

예시문제를 주겠다

문제 설명

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

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

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

public class Problem15 {
    public static void main(String[] args) {
        String s ="(())()";
        boolean answer=true;
        int sum = 0;
        for (int i = 0; i <s.length(); i++) {
            if(s.charAt(i)=='('){
                sum =sum+1;
            }
            else{
                sum = sum -1;
                if(sum<0){
                    answer=false;
                    break;}
            }
        }
        if(sum!=0){
            answer=false;
        }
        System.out.println(answer);
    }
}

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        boolean answer = true;  
        String res = "YES";
        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    st.push(1);
                } else if (s.charAt(i) == ')') {
                    if (st.isEmpty()) {
                        answer = false;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }

            if(!st.isEmpty()) {

                answer = false;

            }

            System.out.println(res);
return answer;
    }   

}

윗코드는 stack 없이, 아랫코드는 stack을 사용해서 푼 답안지이다..

Stack이라는 컬렉션을 사용하라고 억지로 조건을 준다면 넣고 풀겠지만..

나라면 쓰지 않고 푸는게, 낫다고 생각이 든다.

왜냐하면, 알고리즘테스트는 얼마나 빠르게 코드를 작성하는지, 속도가 빠른지로 점수가 메겨지기 때문이다..

 

우아하고 세련된 코드를 쓰고 싶은건 누구나 같지만, 같은 로직임에도 stream을 사용하면 효율성 테스트에 빈번하게 떨어지는것이 알고리즘 테스트이므로..