[Java][백준] #10799 - 쇠막대기

배수연·2024년 5월 30일

Java 백준 알고리즘

algorithm

목록 보기

35/45

🔗 백준 10799 - 쇠막대기

문제

알고리즘 분류

자료구조
스택

IDEA

스택은 써도, 쓰지 않아도 된다.
아래 풀이는 스택을 사용하지 않은 풀이이나, count를 증감하는 대신 스택에 넣고 빼면서 스택의 사이즈를 가지고 계산하여도 성립할 것 같다.

1. '('가 입력되면 막대 갯수(count)++

2. 레이저를 마주하면 res += count, count--,

레이저인지 판별하려면 이전에 입력된 문자(prev)를 저장해야한다.
입력된 문자가 ')' && 이전에 입력된 문자가 '(' 라면 레이저이다.
'(' 가 입력되면 count(막대 갯수)가 증가되는데, 레이저에 포함된 '(' 는 막대 갯수를 의미하는 것이 아니므로 바로 이전에 입력된 count를 다시 감소시킨다 (count--)

3. 막대의 끝을 의미하는 ')' - 즉 레이저가 아닌 ')'가 입력되면 res++, count--

막대가 끝났다는 것은 한 조각이 생겼음을 의미한다.(res++)
막대가 끝났으므로 이 다음에 레이저가 있어도 해당 막대를 조각내지 않는다. 따라서 막대갯수(count)를 감소시킨다.

풀이

1. 입력

String으로 받아 charAt함수를 이용해 문자로 쪼갬

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int count = 0; int res = 0;
        char prev = '0';

2. 막대의 시작과 끝 혹은 레이저인지 판별하여 결과값 누적

        for(int i = 0; i<input.length(); i++ ){
            char c = input.charAt(i);
            if (c == '('){ // case 1 (막대의 시작)
                count ++;
            }
            else if (c == ')') {
                if (prev == '(') { // case 2 (레이저)
                    count--;
                    res+= count;
                }
                else { // case 3 (막대의 끝)
                    res++;
                    count--;
                }
            }
            prev = c; // 조건문 검증이 끝난 후 저장해주어야 함
        }

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int count = 0; int res = 0;
        char prev = '0';
        for(int i = 0; i<input.length(); i++ ){
            char c = input.charAt(i);
            if (c == '('){ // case 1
                count ++;
            }
            else if (c == ')') {
                if (prev == '(') { // case 2 (레이저)
                    count--;
                    res+= count;
                }
                else { // case 3 (막대의 끝)
                    res++;
                    count--;
                }
            }
            prev = c; // 조건문 검증이 끝난 후 저장해주어야 함
        }
        System.out.println(res);
    }
}