ahlight
개발 저장소
ahlight
전체 방문자
오늘
어제
  • 분류 전체보기 (197)
    • Java (7)
    • Spring (5)
    • JPA (2)
    • JavaScript (0)
    • Computer Science (12)
      • 디자인패턴, 프로그래밍 패러다임 (1)
      • 네트워크 (4)
      • 운영체제 (4)
      • 데이터베이스 (3)
      • 자료구조 (0)
    • 알고리즘 (1)
    • 프로그래머스 (13)
    • 백준 (94)
    • 서평 (3)
    • 회고 (1)
    • TIL (58)
    • 기타 (1)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • 라즈베리파이4 #홈서버 #포트포워딩 #dhcp
  • 클린코드
  • TDD
  • Java
  • 넥스트스텝

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
ahlight

개발 저장소

백준

백준 11003번 자바 ☆

2023. 1. 2. 18:17

문제

https://www.acmicpc.net/problem/11003

 

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

www.acmicpc.net

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main11003 {

	static int N,L;
	static Deque<Node> dq;
	
	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 = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		dq = new LinkedList<Node>();
	
		for (int i=0; i<N; i++) {
			int temp = Integer.parseInt(st.nextToken());
			
			while (!dq.isEmpty() && dq.getLast().val > temp) {
				dq.removeLast();
			}
			
			dq.addLast(new Node(temp, i));
			
			if (dq.getFirst().idx <= i - L) {
				dq.removeFirst();
			}
			
			bw.write(dq.getFirst().val + " ");
		}
		
		bw.flush();
		bw.close();
	}
	
	static class Node {
		private int val;
		private int idx;
		
		public Node(int val, int idx) {
			this.val = val;
			this.idx = idx;
		}
	}
}

1. 덱이라는 자료구조를 이용하면 어렵지 않게 풀 수있다. 덱을 몰라 List로만 하려다보니 계속 애를 먹었다.

 

2. 덱의 마지막 부터 탐색을 할 때, 새로들어올 숫자가 기존에 있는 숫자보다 작을 경우 마지막 인덱스의 아이템을 삭제한다. 

 

그 다음 덱이 가지고 있는 아이템들의 인덱스 범위가 L을 초과할 경우 덱의 첫번째 아이템을 제거한다.

 

3. 그 다음 출력해주면 끝.

 

정리 : 덕분에 Deque라는 자료구조 하나 공부했다.

 

'백준' 카테고리의 다른 글

백준 17298번 자바 ☆  (0) 2023.01.04
백준 1874번 자바  (0) 2023.01.03
백준 12891번 자바  (0) 2022.12.31
백준 1253번 자바 ☆  (0) 2022.12.30
백준 1940번 자바  (0) 2022.12.29
    '백준' 카테고리의 다른 글
    • 백준 17298번 자바 ☆
    • 백준 1874번 자바
    • 백준 12891번 자바
    • 백준 1253번 자바 ☆
    ahlight
    ahlight

    티스토리툴바