자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Stack,Queue_쇠막대기_Stack)

 

 

5. 쇠막대기

 

예시 입력 1 

()(((()())(())()))(())

예시 출력 1

17

예시 입력 2 

(((()(()()))(())()))(()())

예시 출력 2

24

 

 

문제를 이해하는 것이 중요했다.

개인적으로 이렇게 길고 그림이 나오면 읽는데 집중이 안되는데, 이것도 연습이 필요하겠지

코드상으로는 간단한데, 어떻게 풀지 생각해낼 수 있느냐가 중요하다

 

 

스택을 생성하고 여는 괄호를 만나면 무조건 push 해야합니다.

그리고 닫는 괄호를 만나면 1) 레이저의 쌍으로 닫는 괄호 2) 막대기의 끝을 알리는 괄호 2가지중에 어떤거인지 판단해야합니다.

어떻게 판단하냐면, 바로 앞에꺼가 여는 괄호라면 레이저입니다. 그때 막대기를 자르는 겁니다.

그게 아니라면 그냥 막대기입니다. 

다시 말해서,닫는 괄호를 만났을때 스택의 상단이 여는 괄호라면 레이저 짝궁입니다. 그때 해당하는 짝궁을 pop합니다.

pop하고 남은 여는 괄호는 막대기껍니다. 레이저가 가운데를 쐈을때, 스택에 남은 막대기 3개를 토막냅니다.

그리고 다시 레이저 괄호()를 만나면 쏘게 되고, 스택의 사이즈를 answer에 누적하면 됩니다.

다시 닫는 괄호를 만나면 앞이 여는 괄호가 아니라서 레이저가 아닌 막대기의 끝을 의미합니다.

그래서 막대기의 여는 괄호를 pop시켜버리고 , 막대기 끝에 있는 1개를 더해줍니다.

 

 

강의 풀이(Time: 157ms Memory: 27MB)

• 레이저를 만나면 짝궁 pop하고 스택 사이즈 누적해주기
• 막대기 끝을 만나면 pop하고 1 누적해주기

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public int solution(String str) {
        int answer = 0;
        // 괄호를 집어넣기 위해 스택 생성
        Stack<Character> stack = new Stack<>();
        // 탐색할때 for each안쓴 이유 : 닫는 괄호일때 앞에 인덱스가 여는 괄호인지 확인이 어려우므로
        for (int i = 0; i < str.length(); i++) {
        	// 여는 괄호일때는 push
            if (str.charAt(i) == '(') stack.push('(');
            // 닫는 괄호일때 2가지 판단
            else {
            	// 먼저 꺼내고
                stack.pop();
                // 이전 인덱스가 여는 괄호면 레이저
                if (str.charAt(i-1) == '(') answer += stack.size();
                // 아니면 막대기의 끝
                else answer++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        System.out.println(T.solution(str));
    }
}