[java] 백준 17298번 문제(오큰수)

원본 링크 : https://www.acmicpc.net/problem/17298

 

문제설명

 

 

소스코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // n과 수열을 받아옴
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) arr[i] = Integer.parseInt(st.nextToken());

        int[] answer = new int[n]; // 정답을 저장하는 배열 선언

        // 스택을 이용해서 정답 배열을 초기화
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < n; ++i)
        {
            while ((!stack.isEmpty()) && (arr[stack.peek()] < arr[i])) answer[stack.pop()] = arr[i];
            stack.push(i);
        }

        while (!stack.isEmpty()) answer[stack.pop()] = -1; // 나머지는 -1로 저장

        for (int i = 0; i < n; ++i) bw.write(answer[i] + " ");
        bw.flush();
    }
}

 

설명

 

 

단계	현재 인덱스(i)	현재 값	스택 상태	정답 배열	설명
초기	0	3	[0]	[0,0,0,0]	첫 인덱스 push
1	1	5	[1]	[5,0,0,0]	3<5이므로 pop해서 answer[0]=5 / 1 push
2	2	2	[1,2]	[5,0,0,0]	5>2이므로 2 push
3	3	7	[3]	[5,7,7,0]	2<7, 5<7이므로 연속 pop 후 answer[] 갱신
최종	-	-	[]	[5,7,7,-1]	남은 스택 원소 -1로 처리

스택의 동작을 더 자세히 보면:

인덱스 검사	스택 top 값	현재 값	비교 결과	동작
i=1	arr[0]=3	5	3<5	pop, answer[0]=5
i=2	arr[1]=5	2	5>2	push(2)
i=3	arr[2]=2	7	2<7	pop, answer[2]=7
i=3	arr[1]=5	7	5<7	pop, answer[1]=7

최종 결과:

인덱스	0	1	2	3
원본 배열	3	5	2	7
정답 배열	5	7	7	-1

---

단계	현재 인덱스(i)	현재 값	스택 상태	정답 배열	설명
초기	0	9	[0]	[0,0,0,0]	첫 인덱스 push
1	1	5	[0,1]	[0,0,0,0]	9>5이므로 1 push
2	2	4	[0,1,2]	[0,0,0,0]	5>4이므로 2 push
3	3	8	[0,1]	[0,0,8,0]	4<8이므로 pop해서 answer[2]=8
3	3	8	[0]	[0,8,8,0]	5<8이므로 pop해서 answer[1]=8
최종	-	-	[]	[-1,8,8,-1]	남은 스택 원소 -1로 처리

스택의 동작 세부사항:

인덱스 검사	스택 top 값	현재 값	비교 결과	동작
i=1	arr[0]=9	5	9>5	push(1)
i=2	arr[1]=5	4	5>4	push(2)
i=3	arr[2]=4	8	4<8	pop, answer[2]=8
i=3	arr[1]=5	8	5<8	pop, answer[1]=8

최종 결과:

인덱스	0	1	2	3
원본 배열	9	5	4	8
정답 배열	-1	8	8	-1