[백준/자바] 11003 최솟값 찾기

[백준/자바] 11003 최솟값 찾기

 

📌 문제 

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.

이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

 

⚔ 입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

 

 

📣 출력

첫째 줄에 Di
를 공백으로 구분하여 순서대로 출력한다.

 

 

 

---

 

 

 

💎 문제분석하기

 

먼저 문제에 주어진 범위에 대한 해석을 해보자면 

 

L은 슬라이딩 윈도우의 크기임을 알 수 있다. 

 

 

 

 

따라서 주어지는 크기 만큼의 슬라이딩을 움직이며 최소 값을 구하는 문제이다. 

 

i가 커지면서 순차대로 최소값을 구하면 된다. 문제에서 i <= 이므로 1부터 카운팅한다. 

 

 

실제로 3개의 윈도우가 형성되는 것은 i가 3부터이다. 

 

둘째 줄에 입력되는 N개의 Ai는 한번에 받아서 처리하는 것이 아니라 하나씩 꺼내가면서 세팅을 해주고 다음 것을 받는 식으로 로직을 구성한다. 

 

즉, 정렬이 아닌 방식을 Deque를 사용함으로써 비슷한 효과를 볼 수 있다. 

 

Deque의 특징은 입력과 출력이 앞뒤에서 가능하다는 점이다. 이를 이용해 

 

인덱스와 최소값을 기준으로 넣고 빼는 방식으로 모든 데이터 값을 비교할 수 있다. 이를 노드라 지칭하며 인덱스와 value를 쌍으로 구성하는 별도의 저장 로직을 구현한다. 

 

들어온 순서는 idx 순서를 판단할 때 쓰일 수 있고

최소 최대값은 마지막 들어온 순서로 판단할 수 있다. 

 

즉, 최소값보다 큰 값은 뒤에서부터 삭제하고, 인덱스를 벗어나는 값은 (윈도우 크기보다 커진 경우) 앞에서부터 판단하여 삭제한다. 

 

이렇게 함으로써 3개 미만의 데이터들이 계속 유지되면서 맨 앞의 값을 최소값으로 출력할 수 있다. 

 

 

1) value 비교에 의해 삭제되는 상황을 살펴보면 다음과 같다. 

 

 

new가 들어갈 때 이전 것이 더 크다면 항상 지워진다 이로써 오른쪽에 있는 value는 왼쪽의 있는 value보다 항상 클 수 밖에 없으며 따라서 맨 왼쪽의 값은 항상 최소값이 된다. 

 

실제 코드에서 돌아가는 로직 

 

2) idx에 따른 비교로 다음 윈도우로 넘어가는 상황을 살펴보면 다음과 같다. 

 

 

📜 슈도코드 작성하기 

사용할 변수를 생각한다. 

 

N : 입력값 데이터 개수 

L : 윈도우의 크기 

st : StringTokenizer에 N개의 Ai 데이터를 받아 임시 저장한다 

Deque : N개의 Ai를 담을 데이터구조 

 

 

st에서 꺼내온 new (인덱스, 값)에 대해서

1) 값이 큰 경우 뒤에서부터 비교하여 삭제한다

2) 마지막 위치에 new를 저장한다 

3) 인덱스에 대해서 1번째 위치와 비교하여 (now 에서 1번 위치의 idx를 뺀다) 벗어났다면 1번 위치의 값을 삭제한다

4) 덱의 1번째 위치를 보낸다. 

 

* 문제의 요구사항에 따라 출력은 한번에 이루어져야 하므로 출력을 버퍼에 넣고 한 번에 출력할 수 있게 해주는

BufferedWriter를 사용한다. 

 

* idx와 value를 같이 리턴해주는 별도 클래스를 만들어 node를 생성한다. 

 

 

 

 

 

 

 

 

 

💡 코드 구현하기

 

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

		// 2번째 열을 받는다
		st = new StringTokenizer(br.readLine());
		Deque<Node> myDeque = new LinkedList<>();

		for (int i = 0; i < N; i++) {
			int newA = Integer.parseInt(st.nextToken());

			while (!myDeque.isEmpty() && myDeque.getLast().value > newA) {        // deque가 비어있지 않고 지금 들어온 밸류가 기존에 있던 마지막 밸류보다 작으면 마지막 밸류를 지운다. => 비어있는 경우 (처음) while문을 건너 뛴다 // + 들어왔는데 이미 최소값으로만 구성이 되어 있다면 지울 필요가 없다
				myDeque.removeLast();
			}
			myDeque.addLast(new Node(newA, i));    // 현재 값이 들어가게 된다. // i는 0으로 들어가지만 어차피 인덱스를 위한 용도이므로 0부터 쌓여도 상관 없다

			if (myDeque.getFirst().index <= i - L) {    // 윈도우 사이즈를 벗어나게 된다면 처음 것을 삭제해준다
				myDeque.removeFirst();
			}
			bw.write(myDeque.getFirst().value + " ");
		}
		bw.flush();
		bw.close();

	}
	
	static class Node {
		public int value;
		public int index;

		Node(int value, int index) {
			this.value = value;
			this.index = index;
		}
	}
	
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편