백준 10799번 <쇠막대기>

백준 알고리즘 10779번

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

10799번: 쇠막대기

---

10779번

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 쇠막대기의 왼쪽 끝은 ( 로 오른쪽 끝은 ) 로 표현한다. 
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. () 는 레이저를 의미한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 

잘려진 쇠막대기의 총 갯수를 구하여라.

 

입력으로 괄호 문자열이 들어온다.

 

출력으로 해당 괄호 문자열을 가지고 잘려진 쇠막대기의 개수를 구해서 출력하면 된다.

---

문제 해결

이 문제는 stack으로 해결할 수 있다.

() 문자열이 레이저를 의미하기 때문에 다른 괄호 문자열 속에 레이저가 몇 개있는지 구해서 잘려진 쇠막대기의 개수를 구할 수 있다. 만약 괄호 문자열 속에 레이저가 n개 있다면 n+1개로 쇠막대기가 잘려진다.

 

해당 문제를 보고 "괄호의 값" 문제가 생각났다. 

닫는 괄호를 만날 때, 레이저의 개수를 세서 해당 쇠막대기가 몇 개로 잘리는지 구할 수 있다. 

()를 만나면 숫자 1을 넣어주었다. stack에서 숫자가 연속으로 있다면 해당 숫자를 모두 더해주었다. 그렇게 한다면 각 쇠막대기가 만나는 레이저의 개수를 모두 셀 수 있다.

---

코드 1

import sys
input = sys.stdin.readline
parens = input()
stack = []
answer = 0
for c in parens:
  if c == '(':
    stack.append('(')
  elif c == ')':
    if len(stack) == 0:
      break
    else:
      if stack[-1] == '(':
        stack.pop()
        stack.append(1)
      elif type(stack[-1]) == int:
        temp = 0
        while len(stack) != 0:
          if type(stack[-1]) == int:
            temp += stack.pop()
          else:
            break
        if temp == 0:
          break
        else:
          answer += temp + 1
          if len(stack) == 0:
            break
          else:
            stack.pop()
            stack.append(temp)
print(answer)

---

코드 2

이전에 푼 코드도 있길래 한 번 봤다.

똑같이 stack을 이용하여 풀었는데 해당 코드는 Java로 작성하였으며, 레이저의 개수를 세지 않고 막대기의 수를 샜다.

 

• 여는 괄호는 stack에 넣는다.
• 닫는 괄호일 때는 stack에서 pop 한다.
  • 만약 앞의 문자가 여는 괄호라면 레이저이므로 잘린 막대기의 수를 센다. 잘린 막대기의 수는 stack의 크기이다.
  • 그렇지 않다면 어떤 쇠막대기의 끝인 것 이므로 막대기의 수는 1개가 추가된다.

 

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		Stack stack = new Stack();
		Scanner sc = new Scanner(System.in);
		
		String text = sc.next();
		int sum = 0;
		for(int i = 0; i < text.length(); i++) {
			if(text.charAt(i) == '(') {
				stack.push(text.charAt(i));
			}
			if(text.charAt(i) == ')') {
				stack.pop();
				if(text.charAt(i - 1) == '(') {
					sum += stack.size();
				}else {
					sum++;
				}
			}
			
		}
		System.out.println(sum);
		
	}

}

---

결과

---

중간에 컴파일 에러는 파이썬 코드를 자바로 내서,,, ㅋㅋㅋㅋㅋㅋㅋㅋ