2021년 8월 2일 월요일 - 벌써 8월이 됐네..
오늘 올려볼 문제는 2493번 탑 라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘은 백준을 둘러보다가 골드문제를 하나 발견해서 가지구 왔다.
슬슬 문제 찾는 레파토리가 떨어져간다...
입력 예제
입력은 매우 단순한 문제이다.
풀이 및 코드
이 문제는 스택을 잘 사용해야 하는 문제다.
문제를 간략히 설명해보자면
- 입력으로 각 탑의 높이가 들어온다. (같은 높이의 탑은 없다.)
- 각 탑은 탑의 꼭대기에서 왼쪽으로 신호를 보낸다.
- 2에서 보낸 신호를 받을 수 있는 센서는 각 탑의 기둥에 부착되어있다. (탑의 높이만큼 길게 부착되어있다는 것)
- 이 때 가장 먼저 신호를 받는 탑의 위치가 어디인지 출력한다.
그러므로 스택에 각 탑의 위치(인덱스)를 넣고 비교하는 과정을 통해서 이 문제를 해결할 수 있다!
아직 헷갈릴 수 있으니 코드를 봐보자!
풀이코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String[] input_arr = br.readLine().split(" ");
int[] arr = new int[n];
// 각 탑의 인덱스를 저장할 스택
Stack<Integer> s = new Stack<Integer>();
for(int i = 0; i < n; i++)
{
// string으로 받은 입력을 int형으로 바꿔주는 작업
arr[i] = Integer.parseInt(input_arr[i]);
// 만약 스택이 비었다면 (신호를 받을 수 있는 탑이 없다면)
if(s.isEmpty())
{
// 0을 출력한다. (신호를 못 받는 경우 0 출력)
bw.write("0 ");
}
// 스택이 비어있지 않다면
else
{
// 아래 과정 반복
while(true)
{
// 스택이 비었다면
if(s.isEmpty())
{
// 0 출력하고 반복문 벗어나기
bw.write("0 ");
break;
}
// 스택에 들어있는 탑의 위치(인데스)에 있는 탑의 높이가 현재 탑의 높이보다 크다면
if(arr[s.peek()] > arr[i])
{
// 스택에 들어있는 탑의 위치 + 1을 출력하고 반복문을 벗어난다.
// 1 더해주는 것은 인덱스와 문제에서 원하는 답과의 차이 때문에 해준다.
bw.write((s.peek() + 1) + " ");
break;
}
// 스택에 들어있는 탑의 위치(인데스)에 있는 탑의 높이가 현재 탑의 높이보다 크지 않다면
else
{
// 스택에서 pop해준다.
s.pop();
}
}
}
// 항상 스택에 현재 탑의 위치(인덱스)를 add해준다.
s.add(i);
}
bw.flush();
}
}
제출 화면
오늘 문제는 스택을 생각하지 못한다면 굉장히 풀기 힘든 문제이다.
사실 바로 전에 올렸던 문제와 굉장히 흡사한 문제였기에 이 블로그를 봤던 사람이라면 쉽게 풀었을 것이다.
이 블로그를 보는 사람이 거의 없다는 점이 문제긴 하지만...
'백준 문제 풀이' 카테고리의 다른 글
| [BOJ / 백준] 백준 2294번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.21 |
|---|---|
| [BOJ / 백준] 백준 2799번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.14 |
| [BOJ / 백준] 백준 17298번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.30 |
| [BOJ / 백준] 백준 1043번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.26 |
| [BOJ / 백준] 백준 1987번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.24 |