https://www.acmicpc.net/problem/10799
문제
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
- 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
- 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
- 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
입력
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.
출력
잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.
예제 입력1
()(((()())(())()))(())
예제 출력1
17
예제 입력2
(((()(()()))(())()))(()())
예제 출력2
24
풀이
수식의 괄호 쌍 활용 문제다.
'('를 스택에 넣는다. 그러다가 ')'를 만나면 직전 괄호가 '('이면 레이저 괄호, 아니라면 그냥 닫힌 괄호다.
레이저 괄호인 경우 스택에서 '('를 pop하고, 스택에 저장된 원소들의 개수가 레이저로 잘려질 막대기의 개수가 된다.
닫힌 괄호인 경우 스택에서 '('를 pop하고, 막대기가 1개 나온다.
코드 (오답)
internal class BOJ10799_쇠막대기
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
Stack<char> stack = new Stack<char>();
int subValue = 0;
int result = 0;
string input = sr.ReadLine();
foreach(char c in input)
{
if(c == '(')
{
stack.Push(c);
}
else if (c == ')')
{
// 바로 앞에 (이면
if(stack.Peek() == '(')
{
if(stack.Count < 1)
{
subValue += 1;
continue;
}
subValue += 1;
//stack.Pop();
result += (stack.Count - subValue);
}
}
//if (c == '(')
// stack.Push(c);
//else if(c == ')')
//{
// // 레이저 O
// if(stack.Peek() == '(')
// {
// //subValue += 1;
// stack.Pop();
// result += (stack.Count);
// }
// // 레이저 X
// else
// {
// stack.Pop();
// result += 1;
// }
//}
}
sw.WriteLine(result);
sw.Close();
sr.Close();
}
}
문제
일치하는 괄호라면 '('을 스택에서 pop한다.
그러면 직전 괄호가 '('이든 상관없이 어쨌든 '('을 스택에서 pop하므로 결국 모든 경우의 수에서 레이저 조건문을 실행하게 되고 잘못된 결과가 나온다.
원인
pop을 해서 문제가 나타나고 있으므로 pop을 하지말고 push만 해서 문제를 풀어보자.
해결 X
현재 괄호와 직전 괄호가 일치하는 경우를 모두 세아려서 결과값을 계산해봤지만 오답이다.
코드2 (정답)
internal class BOJ10799_쇠막대기
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
Stack<char> stack = new Stack<char>();
int subValue = 0;
int result = 0;
string input = sr.ReadLine();
for(int i = 0; i < input.Length; i++)
{
if (input[i] == '(')
{
stack.Push(input[i]);
}
else if (input[i] == ')')
{
if (i >= 1 && input[i - 1] == '(')
{
stack.Pop();
result += stack.Count;
}
else
{
stack.Pop();
result += 1;
}
}
}
sw.WriteLine(result);
sw.Close();
sr.Close();
}
}
원인
스택에서 모든 처리(pop, 직전 괄호와 일치하는지 확인)를 했던 것이 문제였다.
해결
foreach를 for문으로 바꿔서 직전 괄호와 현재 괄호를 비교할 수 있도록 수정했다.
복습1 풀이 (6/6)
[문제]
쇠막대기를 레이저로 절단하려 함.
효율적인 작업을 위해 쇠막대기를 아래에서 위로 겹쳐 놓는다.
레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다.
쇠막대기는 다음 조건을 만족한다.
- 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
- 쇠막대기를 다른 쇠막대기 위에 놓을 때, 완전히 포함되도록 놓는다.
- 끝점이 겹치지 않게 한다.
- 쇠막대기를 자르는 레이저는 적어도 한개 존재
- 레이저는 쇠막대기 양 끝점과 겹치지 않는다.
레이저는 ()으로 표현한다.
쇠막대기의 왼쪽 끝은 (, 오른쪽 끝은 )이다.
쇠막대기와 레이저 배치를 나타내는 괄호 표현이 주어졌을 때,
잘려진 쇠막대기 조각의 총 개수를 구하라.
[입력]
쇠막대기와 레이저 배치 표현이 공백없이 주어진다.
[출력]
잘려진 조각 총 개수 출력
[풀이]
어떻게 풀지 전혀 감이 안 온다.
수식의 괄호쌍 알고리즘을 사용해서 레이저 개수는 헤아려 볼 수는 있는데
이걸로 뭘 어떻게 해야할지 모르겠다.
잘 모를 땐 직접 손으로 그려가며 규칙을 찾아보면 된다.
손으로 직접 그려가며 규칙을 찾았다.
레이저이면 레이저를 쏜다. 레이저를 쏘면 (의 갯수가 잘린 쇠막대기 수이다.
닫는 괄호이면, 쇠막대기 개수를 +1하고, 열린 괄호를 회수한다. (pop)
열린 괄호이면, 스택에 넣는다. (push)
- 레이저이면
- 잘린 쇠막대기 수 += 스택.Count
- 여는 괄호면
- 스택.Push
- 닫힌 괄호면
- 스택.Pop()
- 잘린 쇠막대기 수 += 1
문자열을 처음부터 끝까지 검사하므로, O(N)이 걸린다.
N은 최대 100,000이므로, 1초 내로 풀린다. 이 풀이로 코드를 짜자.
코드 - 정답
class Solution
{
public static bool IsRaser(char c1, char c2)
{
if(c1 == '(' && c2 == ')')
return true;
return false;
}
static void Main(string[] args)
{
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StreamReader sr = new StreamReader(Console.OpenStandardInput());
string input = sr.ReadLine();
Stack<char> stack = new Stack<char>();
int result = 0;
for(int i = 0; i < input.Length; i++)
{
if(i < input.Length - 1 && IsRaser(input[i], input[i+1])
{
result += stack.Count;
i = i + 1;
if(i >= input.Length)
break;
continue;
}
if(input[i] == '(')
stack.Push(input[i]);
else if(input[i] == ')')
{
stack.Pop();
result += 1;
}
}
sw.WriteLine(result);
sr.Close();
sw.Close();
}
}
다른 사람 코드
#include <string>
#include <vector>
using namespace std;
int solution(string arrangement) {
int pipe_count = 0;
int answer = 0;
for (int i = 0; i < arrangement.size(); i++) {
if (arrangement[i] == '(') {
if (arrangement[i + 1] == ')') {
answer += pipe_count;
i++;
} else pipe_count++;
} else if (arrangement[i] == ')') {
answer++;
pipe_count--;
}
}
return answer;
}
스택을 사용하지 않은 코드다.
여는 괄호는 굳이 스택에 넣지 않아도 된다. 여는 괄호가 몇개 있는가를 알면 되니, 여는 괄호의 개수를 헤아려주기만 하면 된다.
cf) 프로그래머스 고득점 Kit : 쇠막대기 | Daily Co
프로그래머스 고득점 Kit : 쇠막대기
스택/큐 문제는 문제를 풀수록 잘 모르겠는 것이, ‘왜 이 문제가 스택/큐 문제이지?’ 하는 의문이 든다. 스택이나 큐 자료구조를 사용하지 않아도 풀 수 있고, 또 실제로 그렇게 풀고있으니까
dailyco.github.io
'자료구조, 코딩테스트 > 스택(Stack)' 카테고리의 다른 글
| [코딩테스트] BOJ 1874 - 스택 수열 (성공) (0) | 2026.04.16 |
|---|---|
| [코딩테스트] BOJ 2504 - 괄호의 값 (실패) (0) | 2026.04.13 |
| [코딩테스트] 스택(Stack) 활용 - 수식의 괄호 쌍 (0) | 2026.04.12 |
| [코딩테스트] BOJ 10773 - 제로 (성공) (0) | 2026.04.09 |
| [코딩테스트] BOJ 10828 - 스택 (성공) (0) | 2026.04.09 |