[백준] 10799 쇠막대기 자바

[백준] 10799 쇠막대기 자바

https://www.acmicpc.net/problem/10799

설명을 위해 앞 부분만 보세요.

저는 처음에 단순히 인덱스로 접근해서 마지막 ' ( '로 돌아갔더니 메모리초과가 나서 stack으로 풀었습니다.

일단 stack구조를 활용하는 문제입니다. ' ( ' 모양은 모두 push하고,

갈색으로 빗금친 괄호의 뜻은 ' ) ' 모양이 왔을 때에 이전의 ' ( '를 pop한다는 의미입니다.

레이저가 지나가는 빨간선,녹색선의 왼쪽을 기준으로 막대의 갯수를 세는 것이 핵심입니다.

레이저가 지나가면 위의 사진처럼 막대가 조각나고, 그것의 갯수는 stack에 쌓아둔 ' ( '의 갯수입니다. (stack size)

보라색처럼 이후에 ' ) '모양이 나오면 하나의 막대가 끝나는 것이기 때문에 단순히 +1을 해주면 됩니다.

주의할 점은 ' ( '을 push할 때에 인덱스 값으로 넣어주어야 아래의 코드처럼 레이저를 구분할 수 있습니다.

단순히 풀면 풀리긴 하지만 에러나고, 정답풀이를 보면 이해할 수 있지만 떠올리기는 힘든 문제였다고 생각합니다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class 쇠막대기 { static String str; static Stack stk = new Stack(); static int sum = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); str = br.readLine(); Stack s = new Stack<>(); for (int x = 0; x < str.length(); x++) { char next = str.charAt(x); if(next == ')' && s.peek() == x-1) { s.pop(); sum+=s.size(); } else if(next == '(') s.add(x); else if(next == ')') { s.pop(); sum ++; } } System.out.println(sum); } }

from http://rootcoder.tistory.com/34 by ccl(A) rewrite - 2021-12-27 02:28:38