2021년 7월 30일 금요일 - 건강 검진 처음 해봄!
오늘 올려볼 문제는 17298번 오큰수 라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘은 건컴 후배님이 푸신 문제들을 둘러보다가 찾은 문제를 가지고 왔다!
형님 보고 계시나요??
입력 예제
입력은 매우 단순한 문제이다.
풀이 및 코드
이 문제는 스택을 사용하는 것이 가장 중요한 포인트이다.
풀이를 간단히 설명해보자면
- 스택에는 배열의 인덱스를 저장한다.
- 스택이 비어있지 않을 경우에는 아래의 과정을 진행한다.
- 스택의 들어있는 인덱스에 해당하는 값보다 현재 인덱스의 해당하는 값이 클 경우 스택에서 인덱스를 pop하고 pop한 인덱스 부분에 현재 인덱스의 해당하는 값을 저장한다.
- 스택의 들어있는 인덱스에 해당하는 값보다 현재 인덱스의 해당하는 값이 크지 않을 경우 이 과정을 벗어난다.
- 또한 스택이 비어있는 경우에도 이 과정을 벗어난다.
- 스택이 비어있을 경우에는 그냥 해당하는 인덱스를 저장한다.
- 위 과정이 모두 끝나면 스택이 비워지지 않을 때까지 스택에 있는 인덱스를 꺼내서 인덱스 부분에 -1을 저장한다.
위에서 설명을 간단히 하느라 조금 헷갈리는 부분이 있을 수도 있을 것 같다... (특히 해당하는 인덱스와 저장하는 부분의 괴리)
그러니 코드를 봐보자!
풀이코드
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));
// n 입력 받음
int n = Integer.parseInt(br.readLine());
// 배열 입력 받음
String[] input_arr = br.readLine().split(" ");
// 최종적으로 출력할 숫자들을 저장하는 배열 (위에서 설명한 저장하는 곳이 이 배열이다.)
int[] result = new int[n];
// 스택
Stack<Integer> s = new Stack<Integer>();
for(int i = 0; i < n; i++)
{
while(true)
{
// 스택이 비워져 있다면 break;
if(s.isEmpty())
break;
// 스택에 들어있는 인덱스를 입력받은 배열에 접근하여 값을 가져옴, 그 값이 현재 for문 i에 해당하는 값보다 작으면
if(Integer.parseInt(input_arr[s.peek()]) < Integer.parseInt(input_arr[i]))
{
// result배열에 스택에 들어있던 인덱스를 pop하고 그 인덱스에 현재 for문 i에 해당하는 값을 저장한다.
result[s.pop()] = Integer.parseInt(input_arr[i]);
}
// 아니라면 break;
else
{
break;
}
}
// 위 과정과 상관없이 현재 인덱스는 스택에 항상 추가해준다.
s.add(i);
}
// 스택에 값이 남아있다면
while(!s.isEmpty())
{
// 스택에 들어있던 인덱스를 pop하고 그 인덱스에 -1을 저장한다.
result[s.pop()] = -1;
}
// result 배열을 출력한다.
for(int i = 0; i < n; i++)
{
bw.write(result[i] + " ");
}
bw.flush();
}
}
제출 화면
오늘 문제는 스택을 생각하지 못한다면 굉장히 풀기 힘든 문제이다.
2중 for문을 사용하면 시간복잡도가 O(n^2)이 되어버리기 때문에 최대 입력이 1,000,000인 이 문제에서는 시간초과가 분명히 날 것이다.
이런 문제들을 볼 때마다 자료구조 공부가 얼마나 중요한지 깨닫게 되는거 같다.
'백준 문제 풀이' 카테고리의 다른 글
| [BOJ / 백준] 백준 2799번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.14 |
|---|---|
| [BOJ / 백준] 백준 2493번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.02 |
| [BOJ / 백준] 백준 1043번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.26 |
| [BOJ / 백준] 백준 1987번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.24 |
| [BOJ / 백준] 백준 2578번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.21 |