[백준] 10799번: 쇠막대기

안녕하세요! 이번에는 백준 10799번 문제를 풀어보겠습니다~

문제

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

쇠막대기를 레이저로 절단한다
쇠막대기는 괄호로 나타낸다
레이저 또한 괄호로 나타낸다

쇠막대기는 아래에서 위로 긴 순서대로 쌓인다

주의해야 할 것

• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다
• 레이저는 인접한 괄호로 나타낸다 "()" + 모든 "()"는 반드시 레이저를 표현한다
• 쇠막대기의 왼쪽 끝은 "(" 오른쪽 끝은 ")"로 표현된다

문제에 나와있는 사진을 보면 이해하기 편하다

이 경우 쇠막대기들은 총 17개의 조각으로 잘린다.

알고리즘

문제를 보자마자 든 생각은 "(" 다음에 ")"이 오는지 확인해야겠다!
"()"가 오는 경우가 아니라면 "("의 개수를 다 세고 잘린 경우를 생각하면 될 것 같다

푸는 방법에는 여러가지가 있겠지만 할 수 있는 방법에 스택이 있겠다는 생각이 들었다
근데 스택이 아니라 그냥 문자열로 받고 한 문자씩 확인하는 방법도 있겠다 싶었다

그래서 두가지 방법으로 다 풀어보려고 한다

코드

문자열로 활용하는 경우

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		
		// 여는 괄호 '('의 개수를 세는 변수 par, 전체 파이프의 개수를 세는 result
		int par = 0;
		int result = 0;
		
		// 문자열의 문자를 하나씩 읽는 for문
		for (int i=0 ; i<str.length(); i++) {
			// 만약 여는 괄호가 있다면 바로 옆에 닫는 괄호가 있는지 확인
			if (str.charAt(i) == '(') {
				// 바로 닫힐 경우 레이저이기 때문에 par의 개수 만큼 (여는 괄호의 개수만큼 쇠파이프가 생김)
				if (str.charAt(i+1) == ')') {
					result += par;
					// 닫히는 괄호는 이미 확인했으므로 i의 값 증가
					i++;
				}
				// 바로 닫히지 않았다면 이는 쇠파이프를 의미하므로 par와 result 1씩 증가
				else {
					par++;
					result++;
				}
			}
			// 쇠파이프가 끝났다는 의미이므로 여는 괄호의 개수를 줄임
			else if (str.charAt(i) == ')') {
				par--;
			}
				
		}
		System.out.println(result);
	}

}

스택을 활용하는 경우

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Baekjoon10799_Stack {

   public static void main(String[] args) throws IOException{
      // TODO Auto-generated method stub
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
      String str = br.readLine();
      
      int result = 0;
      Stack<Character> stack = new Stack<>();
      
      for (int i=0 ; i<str.length() ; i++) {
         if (str.charAt(i) == '(') {
            if (str.charAt(i+1) == ')') {
               result += stack.size();
               i++;
            }
            else {
               stack.push('(');
            }
         }
         else {
            stack.pop();
            result++;
         }
      }
      System.out.println(result);
   }
}

++ 사실 쓰기는 했는데 이게 제 자바에서 Stack import 오류가 뜨네요.. 그래서 프로그램이 잘 돌아가는지 확인이 안 됩니다 ㅠ
해결하려고 끙끙댔는데 잘 안 돼서 다음에 다시 해결 후 수정하도록 하겠습니다

마무리

갑자기 스택 import 이슈로 마무리가 좀 엉성하게 되었지만...
여러가지 방법으로 코딩이 가능하다는 거 ㅎㅎ
제가 한 방법들 말고도 아마 더 많을수도 있어요!
한 번씩 꼭 시도해보시는 걸 추천드립니다

그럼 전 이만!!

** 오류 발생 시 댓글 부탁드려용