[백준 17298번] 오큰 수 (JAVA)

백준 17298번 문제  -  오큰 수

17298번: 오큰수

---

문제 분석

 

• 오큰 수: 입력값(n) 오른쪽에 있으면서 n보다 큰 수 중에서 가장 왼쪽에 있는 수 → 해당 입력 값(n) 이후에 입력받은 가장 가까운 n보다 큰 값
• 오큰 수 존재하면 오큰수 출력, 존재하지 않을 경우 -1 출력
• 시간제한은 1초 (시간이 충분하지 않음)

 

---

해결 키 포인트

• Stack 개념 이해가 필요
• Stack Class가 자바에 존재
• 오큰 수: n 이후에 입력받은 가장 가까운 n보다 큰 값
• 스택 이용할 때 입력값을 스택에 넣기보다 해당 index를 스택에 삽입하면 좋음
• 배열 2개 사용 : 입력 값 배열(num []) | 출력(결과) 값 배열 (result [])
• 시간제한이 1초 뿐
  • 입력과 계산을 다른 반복문에서 하면 시간이 오래 걸림 ▷ 입력받음과 동시에 계산을 해라
  • Scanner과 Print는 시간이 더 소요됨 ▷ 입출력은 BufferReader와 bufferedwriter를 이용해라 
  • bufferedwriter는 나중에 for문에서 write해도 된다
    • 나는 다음 두 경우처럼 bufferedwriter도 Print와 동일한 형태로 사용하면 둘의 시간이 비슷한 줄 알았다. (계산을 하면서 write를 해야지 시간 속도가 다른 줄)
    • 하지만 Print로 할 경우는 시간초과, bufferedwriter로 할 경우는 성공했다.

 

// (1) bufferedwriter 이용
for(int i=0;i<N;i++)
	bw.write(result[i]+" ");
bw.flush();
bw.close();

// (2) Print 이용
for(int i=0;i<N;i++)
	System.out.print(result[i]+" ");

 

---

스택(Stack) 설명

 

스택의 구조는 다음과 같다. 즉 스택의 특징은 "삽입과 삭제 연산 방식: LIFO(후입선출)"이다

 

• LIFO: Last-in first-out

Do It! 알고리즘 코딩 테스트 기본

 

 스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적 

 

스택  용어

 

위치

• top: 삽입과 삭제가 일어나는 위치

 

연산

• push: top 위치에 새로운 데이터를 삽입
• pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek: top 위치에 현재 있는 데이터를 단순 확인

 

---

코드

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;

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));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// N입력
		int N = Integer.parseInt(st.nextToken());
		
		// index를 저장할 stack
		Stack<Integer> stack = new Stack<Integer>();
		
		// 입력 수열 배열, 결과 배열
		int num [] = new int [N];
		int result [] = new int [N];
		
		// num 입력 확인과 동시에 오큰 수 확인
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			// num 입력
			int n = Integer.parseInt(st.nextToken());
			// 만약 n이 스택 top에 들어있는 값보다 더 큰 경우 
			// -> 현재 값이 top의 오큰 수 (반복)
			while(!stack.isEmpty() && num[stack.peek()] < n) {
				result[stack.pop()] = n;
			}
			// stack과 num 배열에 해당 값 저장
			stack.push(i);
			num[i] = n;
		}
		
		// 전체를 다 확인했는데도 stack에 값이 남아있는 경우 
		// -> 오큰 수가 없는 경우
		while(!stack.isEmpty()) {
			result[stack.pop()] = -1;
		}
		
		// 출력
		for(int i=0;i<N;i++)
			bw.write(result[i]+" ");
		
		bw.flush();
		bw.close();
	}
}

---

추가적인 스토리

 

처음에 ToPoint로 시도하였다가 시간초과가 나서 성공하지 못하였다. 다음이 시도한 코드이다.

• 백준 검사기 결과 : 시간 초과 발생

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
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));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// N입력
		int N = Integer.parseInt(st.nextToken());
		
		// N개의 수 num[] 입력
		int num [] = new int [N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) 
			num[i] = Integer.parseInt(st.nextToken());
		
		// start, end 변수 선언
		int start = 0;
		int end = 1;
		
		// while(start < N)
		while(start < N) {
			// num[end]가 num[start]보다 클 경우 nge는 num[end]
			if(start != N-1 && num[end] > num[start]) {
				bw.write(num[end]+" ");
				start++;
				end = start+1;
				continue;
			}
			// end가 마지막 변수 인덱스라면 nge는 -1 
			else if(end >= N-1) {
				bw.write("-1 ");
				start++;
				end = start+1;
				continue;
			}
			end++;
		}
		bw.flush();
		bw.close();
	}
}