[프로그래머스] 쇠막대기, 스택(stack) 문제 자바 풀이

안녕하세요 호호만두에요

이번에는 스택을 이용하여 풀 수 있는 문제입니다!!

물론 스택을 이용하지 않을수도 있겠죠??

스택/큐 문제로 분류되었다고 해서 모두 스택, 큐로만 쉽게 풀 수 있는것 아닙니다

 

아무튼!! 문제를 풀어봅시다!!
이 문제는 딱 봤을떄 쉽지 않겠구나 하는 뭔가 압박감이 있는데

문제만 잘 이해하니까 어렵지 않았어요

 

제가 푼 풀이법을 말씀드릴게요

우선 스택을 선언합니다.

그리고 stack에 쌓아갑니다. 단 '(' 문자 일때만 쌓습니다.

하지만 '()'로 바로 뒤에 ')'가 나온다면 쌓지 않습니다.

계속해서 '('만 쌓아가다가 레이저를 만나게 되면(  '()' 를 만남 ) stack에 있는 '('의 개수를 세서 더합니다.( stack의 크기)

')'를 만나면 stack에서 하나를 pop하고 개수를 한개 더 더해줍니다.

이렇게 하면 총 잘린 쇠막대기의 개수를 구할 수 있습니다.

 

예시를 가지고 설명을 드릴게요 예시 input은 "()(((()())(())()))(())" 입니다.

input	stack
()	empty
(	(
(	((
(	(((
()	(((
()	(((
)	((
(	(((
()	(((
)	((
()	((
)	(
)	empty
(	(
()	(
)	empty

진행 flow가 이렇게 되는데요 이렇게 하는 이유는 레이저 즉, ()가 나오면 막대기를 자르게 됩니다

그러니까 레이저를 만나면 (의 개수, 즉 쌓여이는 막대기의 개수 만큼 막대기가 생깁니다.

 

위의 그림을 보게되면 ()레이저를 만나기 전까지 (가 3개 있으므로 막대기가 3개 겹쳐있다는 것을 알 수 있습니다.

그러면 저기서 잘리게 되니까 레이저 뿜어져 나오는 점선 옆을 보면 막대기가 3개가 되었죠???

그러다가 ')'를 만나면 잘리고 남은 끝에 쇠막대기를 추가해줘야 해서 1을 또 더해줍니다

쉽죠??

 

자세한 설명과 코드는 아래 깃허브에서도 보실 수 있습니다.

https://github.com/wlgh325/Programmers_algorithm/tree/master/Level2/%EC%87%A0%EB%A7%89%EB%8C%80%EA%B8%B0

불러오는 중입니다...

<프로그래머스 쇠막대기 스택 자바 코드>

import java.util.Stack;

class Solution{
    static Stack<Character> stack;
    public int solution(String arrangement) {
        int answer = 0; // 잘린 쇠막대기 조각의 총 개수
        stack = new Stack<>();

        // stack 에는 '('만 넣는다
        // '()'가 나오기 전에 있는 '('의 개수 만큼 증가시킨다
        // 그러다가 ')'가 나와 닫히면 +1을 해주고 '('을 없앤다.

        char[] temp = arrangement.toCharArray();

        for (int i = 0; i < temp.length; i++) {
            if(temp[i] == '(' && temp[i+1] == ')'){
                answer += stack.size();
                i+=1;
            }
            else if(temp[i] == '('){
                stack.push(temp[i]);
            }
            else if(temp[i] == ')'){
                stack.pop();
                answer += 1;
            }


        }
        return answer;
    }
}