일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- SSAFY 테스트
- 코로나 싫어요
- Hamming weight
- DFS
- 수학
- SSAFY 화이팅
- 아자아자 화이팅
- 텐션 업 10기!
- HAVE A GOOD DAY
- have a nice day
- 우유가 옆으로 넘어지면 아야
- 텐션 업 10기 화이팅
- SeongSeobDang
- amazon
- Java 환경 설정
- 네트워크
- 모르고리즘
- 자료구조
- 우유가옆으로넘어지면아야
- SSAFY IM/A
- Have a good day :)
- LeetCode #릿코드 #좋은 하루 되세요 #Have a nice day
- SSAFY 10기 화이팅
- 우유아야
- I am Korean
- Have a nice day.
- DP
- BFS
- 자고 싶다
- Today
- Total
Hope Everyone Is Happy
[골드4] 17298. 오큰수 (Java) 본문
https://www.acmicpc.net/problem/17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
오감자 먹고 싶다
※ 문제를 요약하면 아래와 같습니다.
▶ 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! (피드백 감사합니다!)
'※ 백준 (Baekjoon) > [Java] 문제 풀이 ( Solve the problems)' 카테고리의 다른 글
[실버1] 2667. 단지 번호 붙이기 (Java) (0) | 2023.09.12 |
---|---|
[실버2] 11724. 연결 요소의 개수(Java) (0) | 2023.09.11 |
[골드5] 2493. 탑 (Java) (0) | 2023.09.09 |
[골드5] 5430. AC (Java) (0) | 2023.09.08 |
[실버5] 11866. 요세푸스 문제 0 (Java) (0) | 2023.09.07 |