(백준 #17298) 오켄수(JAVA)

by


백준 문제 17298 – 오켄 수

#17298: 오쿤수

첫 번째 라인은 시퀀스 A의 크기 N(1 ≤ N ≤ 1,000,000)을 제공합니다. 두 번째 행에는 시퀀스 A의 요소 A1, A2, …, AN(1 ≤ Ai ≤ 1,000,000)이 포함됩니다.

'추천 관련글,

www.acmicpc.net

문제 분석



  • 오크수: n보다 큰 수 중에서 가장 왼쪽에 있는 수, 입력값(들)의 오른쪽에 있는 수 → 해당 입력값(들) 이후에 받는 다음 n보다 큰 수.
  • 있으면 옥타브 숫자를 반환하고 없으면 -1을 반환합니다.
  • 제한 시간은 1초입니다(시간이 충분하지 않음).

핵심 문제를 해결하기 위해

  • 스태킹 개념 필요
  • 스택 클래스는 Java에 존재합니다.
  • 큰 수: n 이후에 받은 다음 n보다 큰 값
  • 스택에 입력을 푸시하는 대신 스택을 사용하는 경우 해당 인덱스스택에 삽입하는 것이 좋습니다.
  • 2개의 배열 사용: 입력 값의 배열(num()) | 출력(결과) 값의 배열(result())
  • 제한 시간은 단 1초
    • 다른 루프에서 입력하고 계산하는 데 시간이 오래 걸립니다. ▷ 입력이 수신되면 계산
    • 스캐닝 및 인쇄에 더 많은 시간이 소요됨 ▷ I/O에 BufferReader 및 BufferedWriter 사용
    • 버퍼링된 기록기는 나중에 for 문에 쓸 수 있습니다.
      • 그래요 다음 두 가지 경우와 같이 bufferedwriter:인쇄와 같은 형식을 사용하고 있다면 둘의 시간이 비슷하다고 생각했습니다. (계산할 때 써야 하는데 시간의 속도가 다르다)
      • 그러나 인쇄의 경우 타임아웃이 되었고, 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)+" ");

스택 설명

스택의 구조는 다음과 같습니다. 즉, 스택의 속성은 다음과 같습니다. “삽입 및 삭제 알고리즘: LIFO(후입선출)” 오전

  • LIFO: 후입선출


해! 알고리즘 코딩 테스트 기초

스택은 역추적 코딩 테스트의 일종인 DFS(깊이 우선 탐색)에 효과적입니다.

스택 조건

위치

  • 위: 삽입 및 삭제가 발생하는 위치

계산

  • push : 최상위 위치에 새로운 데이터 삽입
  • pop : 현재 상위에 있는 데이터를 삭제하고 조회하는 작업
  • 피크: 현재 피크 위치에 있는 데이터를 쉽게 검토

암호

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();
	}
}