알고리즘/백준
[백준] 17298 - 오큰수
person456
2024. 3. 20. 08:49
난이도 - G4
사용 개념 - 구현, 자료구조(Stack)
풀이 시간 - 45분 ( 설계 25분, 구현 20분 )
핵심 키워드
* 1. 시간제한이 1초지만, N 범위 최대가 1,000,000회라 O(n²)이면 시간초과 발생 -> O(Nlogn)으로 해결 가능
* 2. 스택을 사용하며 역순으로 진행한다. ( 맨 뒤의 index는 무조건 -1이기 때문 )
2-1. 한 번 값을 얻어올 때 마다 스택의 맨 위와 비교하여 행동을 결정한다.
2-2. 만약 배열에 저장된 값이 스택의 맨 위보다 작다면, 스택에 저장된 값이 배열의 해당 index의 오큰수는
스택의 맨 위 값이 된다.
2-3. 만약 배열에 저장된 값이 스택의 맨 위보다 크다면, 스택을 하나씩 꺼내보며 더 큰 수를 발견하거나,
스택이 빌 때 까지 확인한다.
2-4. 스택이 비어있다면 해당 값의 오큰수는 없기때문에 -1을 저장
* 3. 반복문의 처음에서 스택이 비어있다면, 이미 해당 값의 오큰수는 없다는 것이기때문에 -1을 저장
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
static StringBuilder sb;
static int n,m,k;
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
Stack<Integer> stack = new Stack<>();
int[] result = new int[n];
// 역순으로 진행. 0번 인덱스는 정상 배열인 arr의 [n-1]의 위치 값 result[0] = -1;
int index = 1;
sb = new StringBuilder();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
int start = arr[n-1];
stack.push(start);
for(int i = n-2; i>=0; i--){
int now = arr[i];
if(stack.size()>0){
if(now<stack.peek()){
// 현재 arr배열의 값보다 스택의 맨 위가 크다면 해당 수가 오큰수 result[index++] = stack.peek();
}
else{
// peek로 확인했기 때문에 한번 pop을 해줘야 한다. stack.pop();
while(!stack.isEmpty()){
if(stack.peek()<=now){
stack.pop();
}
else{
result[index++] = stack.peek();
break;
}
}
if(stack.isEmpty()){
result[index++] = -1;
}
}
}
else {
result[index++] = -1;
}
stack.push(now);
}
for(int i = result.length-1; i>=0; i--){
sb.append(result[i]+ " ");
}
System.out.println(sb.toString().trim());
}
}
|
cs |
|
|
|
주의사항
- 처음에는 StringBuilder에 모든 값을 저장하고 StringBuilder.reverse().toString().trim()으로 진행했다.
-> 이것을 하면 -1을 저장할때도 "1-"로 저장해야 함
-> 10 이상의 숫자가 나오면 10 -> 01, 12 - > 21 등 이상하게 저장됨...
-> 이후 저장용 배열을 하나 더 생성하여 값을 저장하고 역순 조회를 통해 sb에 저장 후 출력