백준 11003번(JAVA)

반응형

문제가 많이 더럽다.

로직이나 알고리즘을 요구한다기보단 어떻게든 시간을 줄여야한다.

빠른 입출력을 요구하고 덱을 활용하는데 add가 아닌 offer를 쓰고 poll이아닌 remove를 쓰고 peek이 아닌 get을 쓰고

문제 자체는 어렵지 않다.

뭐 슬라이딩 윈도우라는 이름이 있다는데 그런거 잘 몰라도 충분히 풀 수 있다.

필자는 솔직히 이 로직 하나만 봤을때 이게 플레 5문제인가 싶다.

우선 덱을 활용하는 문제인데 앞에서 뒤로 갈때 오름차순이다.

출력할땐 당연히 맨 앞의 숫자를 출력하면 된다. 이 때 맨 앞의 숫자가 주어진 범위를 벗어났으면 맨 앞의 숫자를 삭제해준다. 입력을 받을 땐 while문을 써서 맨 뒤에 숫자가(q.getLast()) 입력할 숫자보다 작을 때 까지 계속 q.removeLast()로 뒤를 삭제 해준다.

코드도 매우 짧으니 코드만 봐도 충분히 이해 가능할 것이다.

 

소스코드

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=Integer.parseInt(st.nextToken());
		int L=Integer.parseInt(st.nextToken());
		st=new StringTokenizer(br.readLine()," ");
		int[] arr=new int[N];
		Deque<Integer> q=new ArrayDeque<>();
		for(int i=0;i<N;i++)
		{
			arr[i]=Integer.parseInt(st.nextToken());
		}
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<N;i++)
		{
			int num=arr[i];
			while(!q.isEmpty()&&arr[q.getLast()]>num)
			{
				q.removeLast();
			}
			q.offerLast(i);
			if(q.getFirst()<i-L+1)
			{
				q.removeFirst();
			}
			sb.append(arr[q.peekFirst()]+" ");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

댓글과 지적은 언제든지 환영입니다~!

 

글이 마음에 들었다면 왼쪽이미지를 눌러서 후원 부탁드립니다><