[골드4] 17298. 오큰수 (Java)

https://www.acmicpc.net/problem/17298

17298번: 오큰수

오감자 먹고 싶다

---

※  문제를 요약하면 아래와 같습니다.

▶ N개의 수가 수열( A1, A2, ... Ai)로 주어질 때 각 수의 오큰수(NGE) 그하기 

▶ 오큰수란 수열을 나열했을 때, Ai를 기준으로 오른쪽의 수들 중에, Ai보다 큰 수이며 가장 왼쪽에 있는 수

▶ 오큰수가 존재하지 않을 때는 -1로 저장

     ex) A=[3,5,2,7] 의 경우 3의 오큰수는 5, 5의 오큰수는 7, 2의 오큰수는 7, 7의 오큰수는 없으므로 -1

▶  Input : 첫째 줄에 수열의 갯수 N, 둘째 줄에 수열 A의 원소가 공백을 구분으로 주어짐

▶  Output : 총 N개의 수의 각각의 오큰수를 출력

---

◈ Input - 1

4
3 5 2 7

◈ Output - 1

5 7 7 -1

◈ Input - 2

4
9 5 4 8

◈ Output - 2

-1 8 8 -1

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 각 수열의 번호와 값을 클래스 형태로 정의

▶ Stack에 클래스 형태로 정의한 수열의 정보를 저장

▶ 수열의 값이 주어질 때마다 스택의 마지막 값과 비교 작업 후 주어진 값을 스택에 저장

▶ 스택의 마지막 값 < 주어진 값 == 오큰수

      ex) 3이 저장되어 있는 스택에서 5가 들어올 경우 5 == 3의 오큰수

▶ 오큰수일 경우, 해당 스택의 마지막 값을 제거한 뒤, 제거한 인덱스 번호에 오큰수 값을 저장

▶ 오큰수일 경우, 위의 작업을 스택이 비었거나 주어진 값이 크지 않을 때 까지 반복 (오큰수가 아닐 때까지 반복)

▶ 위의 탐색이 모두 끝난 후 스택에 남아있는 값들은 오큰수가 없다고 판정, 해당 인덱스들은 -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;
import java.util.StringTokenizer;

class NGE{
	int m_nNumber = 0;
	int m_nValue = 0;
	
	public NGE(int m_nNumber, int m_nValue) {
		this.m_nNumber = m_nNumber;
		this.m_nValue = m_nValue;
	}
}

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(bReader.readLine());
		Stack<NGE> stNGE = new Stack<>();
		int[] narrResult = new int[N];
		
		StringTokenizer st = new StringTokenizer(bReader.readLine());

		for(int i = 0; i < N; i++) {
			int nNumber = Integer.parseInt(st.nextToken());
			// 스택 맨 마지막 값보다 큰값이 들어 왔다??
			// 오큰수니까 다 저장해버려
			while(!stNGE.isEmpty() && stNGE.peek().m_nValue < nNumber) {
				narrResult[stNGE.pop().m_nNumber] = nNumber;
			}
			
			// 인덱스와 값을 저장해
			stNGE.add(new NGE(i, nNumber));
		}
		
		// 오큰수가 없는 것만 남아있다아
		while(!stNGE.isEmpty()) {
			narrResult[stNGE.pop().m_nNumber] = -1;
		}
		
		// 출력해
		for(int i = 0; i < N; i++)
			bWriter.write(narrResult[i] + " ");
		
		bWriter.flush();
		bWriter.close();
	}
}

으헝 주말인데 술도 못먹구22,,,

Good Luck! (피드백 감사합니다!)