[백준] 17298. 오큰수 (자바 JAVA)

[ 문제 ]  [백준] 17298. 오큰수 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

---

# 접근 방법 및 풀이 

 

• 스택을 이용한 문제다. 진짜 자바라서 좀 짜증나는 문제였다. 자바는 왜 입출력에 그렇게 시간이 오래걸리냐?
• 같은 로직이어도 언어에 따라서 수행시간이 당연히 다르겠지만, 자바는 입력이나 출력을 뭐로 하냐에 따라 문제 통과여부가 갈려서 화난다.. 
• 그리고 문제를 어디서 풀어봤나 싶었더니, https://ilmiodiario.tistory.com/119 프로그래머스 주식가격이랑 푸는 방식은 비슷하다. 백준에서 골드4인데 프로그래머스에서 레벨2 뭐죠.. 갭차이?
• 이 문제 정답률 낮은 이유는 시간초과때문이다. 정답 배열을 for문 돌면서 sysout으로 찍었더니 역시나 시간초과 났다.
• StringBuilder 이용해서 바꿔주니 겨우 통과..허허
• 아무튼 이 문제의 로직은 생각보다 간단하다. 인덱스와 값을 저장할 수 있는 class로 배열에 입력받는다.
• 순서대로 탐색하며, 스택에 값이 들어있을 경우 스택의 값이 빌때까지 꼭대기값이 현재 값과 비교해 현재값이 더 클 경우 pop해주면된다.
• 그리고 정답배열을 N크기 만큼 생성해 pop해준 인덱스에 현재값을 넣으면 된다. 
• 배열 탐색을 다 하고나면 오큰수를 찾지 못한 값과 맨 마지막 인덱스 값이 스택에 남아있다.
• 그러한 경우는 -1 처리를 해주어야 하므로, 스택이 빌때까지 pop하며 해당 인덱스에 -1을 넣어주면된다.
• 그리고 중요한 정답배열을 그냥 sysout찍으면 시간초과뜬다 ^^...주의
• 자세한건 코드참조

# 주의할 점 

 

• 출력시 정답 배열 sysout으로 찍으면 시간초과남.

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class bj17298_오큰수 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		Point arr[] = new Point[N];
		int ans[] = new int[N];
		Stack<Point> stack = new Stack<>();
		StringTokenizer st = new StringTokenizer(in.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			arr[i] = new Point(i, Integer.parseInt(st.nextToken()));
		}
		for (int i = 0; i < N; i++) {
			while (!stack.isEmpty() && stack.peek().y < arr[i].y) {
				int idx = stack.pop().x;
				ans[idx] = arr[i].y;
			}
			stack.add(arr[i]);
		}
		while(!stack.isEmpty()) {
			ans[stack.pop().x] = -1;
		}
		for (int i = 0; i < ans.length; i++) {
			//System.out.print((ans[i] == 0) ? -1 : ans[i]);
			sb.append(ans[i]+ " ");
		}
		System.out.println(sb);
	}
}

 

 

 

REVIEW