https://www.acmicpc.net/problem/6198
문제
도시에는 N개의 빌딩이 있다.
빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.
i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.
i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.
그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.
예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우
=
= =
= - =
= = = -> 관리인이 보는 방향
= - = = =
= = = = = =
10 3 7 4 12 2 -> 빌딩의 높이
[1][2][3][4][5][6] -> 빌딩의 번호
- 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
- 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
- 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
- 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.
따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.
입력
- 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
- 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)
출력
- 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.
예제 입력1
6
10
3
7
4
12
2
예제 출력1
5
풀이 1
i번째 탑 높이와 i+1, i+2, ..., 탑 높이와 비교를 해서 i번째 탑 높이보다 작은 탑들을 헤아리면 될 것이라고 생각했다.
코드 - 오답
namespace 스택
{
internal class BOJ2504_괄호의_값
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
Stack<char> stack1 = new Stack<char>();
Stack<int> stack2 = new Stack<int>();
bool isCorrect = false;
int preNum = 0;
int result = 0;
string input = sr.ReadLine();
for(int i = 0; i < input.Length; i++)
{
if (input[i] == '(' || input[i] == '[')
{
stack1.Push(input[i]);
}
else
{
// 올바른 괄호이면
if (stack1.Peek() == '(' && input[i] == ')')
{
char pre = stack1.Pop();
if (isCorrect)
{
result += preNum * stack2.Pop();
preNum = 1;
isCorrect = false;
continue;
}
if (stack1.Peek() == '(' || stack1.Peek() == '[')
{
if (stack1.Peek() == '(')
{
stack2.Push(2);
if (input[i+1] != ')' || input[i+1] != ']')
{
if(pre == '(')
{
preNum = 2;
result += preNum;
}
else if(pre == '[')
{
preNum = 3;
result += preNum;
}
}
}
else if (stack1.Peek() == '[')
{
stack2.Push(3);
}
}
else
{
if (pre == '(')
{
preNum = 2;
result += preNum;
}
else if (pre == '[')
{
preNum = 3;
result += preNum;
}
}
isCorrect = true;
}
else if(stack1.Peek() == '[' && input[i] == ']')
{
char pre = stack1.Pop();
if (isCorrect)
{
result += preNum * stack2.Pop();
preNum = 1;
isCorrect = false;
continue;
}
if (stack1.Peek() == '(' || stack1.Peek() == '[')
{
if (stack1.Peek() == '(')
{
stack2.Push(2);
if (input[i + 1] != ')' || input[i + 1] != ']')
{
if (pre == '(')
{
preNum = 2;
result += preNum;
}
else if (pre == '[')
{
preNum = 3;
result += preNum;
}
}
}
else if (stack1.Peek() == '[')
{
stack2.Push(3);
}
}
else
{
if (pre == '(')
{
preNum = 2;
result += preNum;
}
else if (pre == '[')
{
preNum = 3;
result += preNum;
}
}
isCorrect = true;
}
}
}
sw.WriteLine(result);
sw.Close();
sr.Close();
}
}
}
오답이다.
위 코드는 시간 복잡도가 O(N^2)이다. 이중 for문의 연산 횟수를 헤아려보면 평균 N^2/2가 나온다.
상수를 다 떼면 시간 복잡도는 O(N^2)이다.
문제에서 제한시간은 1초다. N은 최대 80,000이다. 80,000을 제곱하면 6,400,000,000이다.
컴퓨터는 1초에 3억~5억 번의 연산을 한다. 64억이면 1초를 초과한다. 따라서 O(N^2) 풀이는 오답이다.
코드 2 - 오답
namespace 스택
{
internal class BOJ6198_옥상_정원_꾸미기
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
Stack<int> stack = new Stack<int>();
int N = int.Parse(sr.ReadLine());
int[] heightArray = new int[N];
for(int i = 0; i < N; i++)
{
heightArray[i] = int.Parse(sr.ReadLine());
}
int answer = 0;
int currentHeight = 0;
for(int i = N-1; i > 0; i--)
{
if(i == N - 1)
{
stack.Push(heightArray[i]);
continue;
}
currentHeight = heightArray[i];
while(stack.Count > 0 && stack.Peek() < currentHeight)
{
answer++;
//stack.Pop();
}
stack.Push(currentHeight);
}
sw.WriteLine(answer);
sw.Close();
sr.Close();
}
}
}
스택을 이용해서 어떻게 해결해보려 했지만 잘 풀리지 않았다.
코드 3 - 정답
namespace 스택
{
internal class BOJ6198_옥상_정원_꾸미기_바킹독
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
int n = int.Parse(sr.ReadLine());
Stack<int> stack = new Stack<int>();
long answer = 0;
for(int i = 0; i < n; i++)
{
int curHeight = int.Parse(sr.ReadLine());
// 바라보는 탑이 없는지 확인
while(stack.Count > 0 && stack.Peek() <= curHeight)
{
stack.Pop();
}
answer += stack.Count;
stack.Push(curHeight);
}
sw.WriteLine(answer);
sw.Close();
sr.Close();
}
}
}
정답 코드를 봤다.
이 풀이는 "나를 볼 수 있는 빌딩이 있는가"로 문제를 풀이했다.
나는 "빌딩에서 오른쪽으로 몇 개를 볼 수 있는가"로 문제를 풀었는데, 이 풀이는 나와 반대로 생각하고 풀었다.
관점을 뒤집는 것만으로도 문제를 풀 수도 있음에 신기했다. 앞으로 문제를 풀면서 유연하게 생각을 전환할 수 있도록 노력해야겠다.
복습1 (5/2)
복습1 풀이
i번째 빌딩이 볼 수 있는 빌딩의 개수를 세아리는 문제다.
arr[i]와 arr[i+1], arr[i+2], ...을 비교하고, arr[i+1]과 arr[i+2], arr[i+3], ...을 비교하면 될 것 같긴한데.
이렇게 하면 시간복잡도는 아마도 O(N^2)이 나온다.
이 문제에서 N은 최대 80,000이다.
80,000의 제곱은 6,400,000,000. 64억이다. 컴퓨터는 1초에 3억~5억 연산을 한다. 1초를 초과하니 O(N^2)으로 풀면 안된다.
저번에 어떻게 풀었나 생각을 해봤다.
"i번째 빌딩이 볼 수 있는 곳" 이렇게 풀었더니 막혔다.
반대로 생각해보면 어떨까. "몇번째 빌딩이 나를 볼 수 있을까"
arr[i]번 빌딩을 몇번째 빌딩이 볼 수 있을까로 접근해보자. arr[i]번째 빌딩보다 앞에 있는 빌딩들은 어떻게 관리할까?
먼저 들어온 것을 체크하려면 스택 자료구조가 적합하다. 스택을 이용해서 문제를 풀어보자.
입력으로 들어오는 빌딩의 높이를 스택에 넣으면서 넣으려는 빌딩 높이와 현재 스택에 있는 이전 빌딩의 높이와 비교하면서 높이를 비교해서 나를 볼 수 있는 빌딩의 개수를 세아리면 된다.
복습1 코드 - 정답
using System.Text;
namespace 스택
{
internal class BOJ6198_옥상정원_복습1
{
static StreamReader sr = new StreamReader(Console.OpenStandardInput());
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
static StringBuilder sb = new StringBuilder();
static void Main(string[] args)
{
int answer = 0;
int N = int.Parse(sr.ReadLine());
Stack<int> stack = new Stack<int>();
for(int i = 0; i < N; i++)
{
int num = int.Parse(sr.ReadLine());
while(stack.Count > 0 && stack.Peek() <= num)
{
stack.Pop();
}
// 높이 num빌딩은 x번째 빌딩이 볼 수 있다.
answer += stack.Count;
stack.Push(num);
}
sb.Append(answer);
sw.WriteLine(sb.ToString());
sw.Close();
sr.Close();
}
}
}
'자료구조, 코딩테스트 > 스택(Stack)' 카테고리의 다른 글
| [코딩테스트] Programmers - 올바른 괄호 (성공) (0) | 2026.04.29 |
|---|---|
| [코딩테스트] BOJ 17298 - 오큰수(실패) (0) | 2026.04.22 |
| [코딩테스트] BOJ 2493 - 탑 (실패) (0) | 2026.04.20 |
| [코딩테스트] BOJ 1874 - 스택 수열 (성공) (0) | 2026.04.16 |
| [코딩테스트] BOJ 2504 - 괄호의 값 (실패) (0) | 2026.04.13 |