백준 10799번 쇠막대기 Java

: ) YOUNG·2024년 3월 31일
1

알고리즘

목록 보기
346/417
post-thumbnail

백준 10799번
https://www.acmicpc.net/problem/10799

문제



생각하기


  • 괄호에 관련된 문제이다.

  • 안 풀던 유형의 문제여서 생각보다 어려웠다

  • 좋은 문제인 것 같다.



동작


        for (int i = 0; i < N; i++) {
            char ch = chArr[i];

            if (ch == '(') {
                list.offerLast(ch);
            } else if(ch == '1') {
                ans += list.size();
            } else {
                list.pollLast();
                ans++;
            }
        }

list에서 '('로 저장된다. ['(', '(', '('] 라는 표시는 현재 진행중인 쇠막대기가 3개 있다는 뜻이다.
중간에 레이저가 나오면서 쇠막대기가 언제 끝날지 모르는 상태이다.

그래서 if(ch == '1')의 경우에 모르는 상태지만 일단 레이저에 잘리는게 확정됨으로써

list.size()에 있는 개수들이 확정으로 잘리게 됨으로 ans += list.size()가 된다.

그리고 if(ch == ')')의 경우 쇠막대기가 하나 끝나므로 잘린 쇠막대기의 끝부분 + 1을 해주면 된다. 그래서 ans++

결과


코드



import java.io.*;
import java.util.LinkedList;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static char[] chArr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int ans = 0;
        int N = chArr.length;
        LinkedList<Character> list = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            char ch = chArr[i];

            if (ch == '(') {
                list.offerLast(ch);
            } else if(ch == '1') {
                ans += list.size();
            } else {
                list.pollLast();
                ans++;
            }
        }

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        chArr = br.readLine().replace("()", "1").toCharArray();
    } // End of input()
} // End of Main class

0개의 댓글