백준 문제 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();
}
}