[JAVA][Baekjoon] 11003번 최솟값 찾기 ⭐️⭐️⭐️⭐️
2024. 5. 2. 13:59
728x90
SMALL
https://www.acmicpc.net/problem/11003
🚫 시간초과 코드
처음에 너무 단순하게 그냥 반복문으로 구간마다 최솟값을 찾아서 출력하려 했었다....
완전 멍청이 코드였다 😡💢
import java.util.*;
import java.io.*;
public class Main {
public static void main(String [] args) throws IOException{
int N, L;
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
L = sc.nextInt();
int [] arr = new int[N];
for(int i=0; i<N; i++){
arr[i] = sc.nextInt();
}
for(int i=0; i<N; i++){
long min = 1000000000;
if(i-L+1 < 0){
for(int j=0; j<=i; j++){
if(min>arr[j]){
min = arr[j];
}
}
}
else{
for(int j=i-L+1; j<=i; j++){
if(min>arr[j]){
min = arr[j];
}
}
}
System.out.print(min + " ");
}
}
}
728x90
📌 접근 방법
일정 범위 안에서 최솟값을 구하는 문제는 슬라이딩 윈도우와 정렬을 사용하는 것 추천!
➡️ Deque(덱) 사용 !! (슬라이딩 윈도우를 deque로 표현하여 정렬 효과 )
더보기
🥐 Deque 란?
양방향으로 값을 삽입 및 삭제할 수 있는 자료구조
<Reference>
- Deque에 value, index 값을 저장하여 비교
- 반복문을 통해 새로 삽입하는 값이 더 작으면 앞의 요소들을 제거하는 식으로 구현한다.
✅ pass code
import java.util.*;
import java.io.*;
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());
int N, L;
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
Deque<Node> deque = new LinkedList<>();
for(int i = 0; i < N; i++) {
int num = Integer.parseInt(st.nextToken());
while(!deque.isEmpty() && deque.getLast().value > num){
deque.removeLast();
}
deque.addLast(new Node(num, i));
if(deque.getFirst().index <= i - L) {
deque.removeFirst();
}
bw.write(deque.getFirst().value + " ");
}
bw.flush();
bw.close();
}
static class Node {
public int index;
public int value;
Node(int value, int index) {
this.value = value;
this.index = index;
}
}
}
Reference
728x90
LIST
'Baekjoon' 카테고리의 다른 글
[JAVA][Baekjoon] 17298번 오큰수 ⭐️⭐️⭐️⭐️⭐️ (0) | 2024.05.07 |
---|---|
[JAVA][Baekjoon] 1874번 스택 수열 (0) | 2024.05.02 |
[JAVA][Baekjoon] 12891번 DNA 비밀번호 ⭐️ (1) | 2024.03.23 |
[JAVA][Baekjoon] 1940번 주몽 ⭐️ (1) | 2024.03.23 |
[JAVA][Baekjoon] 2018번 수들의 합 5 (0) | 2024.03.23 |