sm 기술 블로그
156. 17298(오큰수) - 자바 본문
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[] A = new int[N];
int[] result = new int[N];
Stack<Integer> stack = new Stack<>();
String[] S = br.readLine().split(" ");
for (int i = 0; i < N; i++) {
result[i] = -1;
A[i] = Integer.parseInt(S[i]);
}
for (int i = 0; i < N; i++) {
try {
while (A[stack.get(stack.size() - 1)] < A[i]) {
result[stack.pop()] = A[i];
}
} catch (Exception e) {
}
stack.add(i);
}
for (int val : result) sb.append(val).append(" ");
System.out.println(sb);
}
}
문제요약
입력값에 오큰수를 구해라.
오큰수란?
A=A1 ~ AN이 있을 때 Ai번째의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중 가장 왼쪽에 있는 수이다.
다시 말해 지금 수 보다 크고, 인덱스 크기가 가장 작은 수
설명
입력 예시로
백준에 있는 다음과 같은 예시를 들어보자.
3과 5를 비교했을 때 5가 더 크다. 따라서 답은 5가 된다.
답이 7이 될 수 없는 이유는 오큰수는 N보다 오른쪽에 있으면서 가장 왼쪽에 있는 수이다.
다음 5는 먼저 2보다 크다 그래서 2가 될 수 없고 7은 5보다 크기 때문에 가능하다.
2도 7이 더 크기 때문에 7이 나온다.
7의 오른쪽에는 수가 없을 뿐만 아니라 7보다 더 큰 수도 없기 때문에 -1이 나온다.
따라서 답은 5 7 7 -1이다.
전체적인 맥락은 이렇다.
for (int i = 0; i < N; i++) {
result[i] = -1;
A[i] = Integer.parseInt(S[i]);
}
먼저 모두 오큰수가 없는 경우인 -1로 초기화 했다.
초기화 하는 김에 입력값도 같이 받았다.
try {
while (A[stack.get(stack.size() - 1)] < A[i]) {
result[stack.pop()] = A[i];
}
}
stack에 값이 없다면 에러를 불러 일으킬 것이다.
그것을 이용하여 try / catch문을 사용했다.
A[stack.get(stack.size() - 1)]이 기준이다.
기준을 중심으로 오른쪽의 크기 A[i]가 크다면 while문을 계속 진행한다.
result에 stack 값을 꺼내 인덱스로 정하고, 크기가 더 큰 오른쪽 값을 집어 넣는다.
catch (Exception e) {
}
stack.add(i);
try except문이 종료되면 stack에 i값을 집어넣는다.
아직 i번째의 오큰수를 구하지 않았기 때문이다.
for (int val : result) sb.append(val).append(" ");
System.out.println(sb);
for문을 이용하여 값을 StringBuilder에 넣어 주었다.
바로 출력하지 않는 이유는 system.out.print는 생각보다 시간을 많이 잡아먹는다.
따라서 바로 출력하면 시간초과가 발생하기 때문에 sb에 저장하고 sb를 출력하는 방식을 채택하였다.
'문제 > 백준_자바' 카테고리의 다른 글
158. 2164(카드2) - 자바 (0) | 2022.07.26 |
---|---|
157. 18258(큐) - 자바 (0) | 2022.07.25 |
155. 1874(스택 수열) - 자바 (0) | 2022.07.22 |
154. 4949(균형잡힌 세상) - 자바 (0) | 2022.07.22 |
153. 9012(괄호) - 자바 (0) | 2022.07.21 |