[백준 10799] 쇠막대기 - 자바

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

10799번: 쇠막대기

---

1. 풀이

처음에 문제가 이해가 안됐는데, 이해하고 나서는 쉽게 풀이를 할 수 있었습니다.

 

알고리즘 문제도 수학 문제와 똑같이 문제 이해가 먼저 인 듯 싶다.

문제에서 레이저를 쏘는 경우는 '()' 와 같이 인접한 괄호인 경우이다.

 

이 문제의 핵심은 ')'이 나왔을 때, 이것이 레이저인지, 쇠 막대기인지 파악하는 것이다.

• 레이저인 경우, '('의 개수를 계산.
• 쇠 막대기인 경우, +1을 해준다.

레이저인지를 확인하기 위해서는 인접한 괄호의 인덱스를 알아야 하므로, 인덱스르 저장하는 스택을 사용하면 된다.

 

---

2. 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String input = sc.next();
		int result = 0;
		Stack<Integer> stack = new Stack<Integer>();
		
		for(int i = 0; i < input.length(); i++) {
			if(input.charAt(i) == '(')
				stack.push(i);
			else {
				if(stack.pop() == i-1) // 서로 인접한 경우.
					result+=stack.size();
				else // 아닌 경우
					result+=1;
			}
		}
		
		System.out.println(result);
		
		sc.close();
		return;
	}
}

stack을 만들지 않고 int를 사용하여도 풀이가 가능하다.

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


public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new 	OutputStreamWriter(System.out));//선언
        Stack<Character> stack = new Stack<Character>();
        int check = 0;
        int result = 0;

        String input = br.readLine();

        for(int i = 0; i < input.length(); i++){
            if(input.charAt(i) == '(')
                check++;
            else{
                check--;
                if(input.charAt(i-1) == '(')
                    result+=check;
                else
                    result++;
            }
        }

        System.out.println(result);
    }

}