[BOJ 백준] 최솟값 찾기(11003) C++, Java

링크 : https://www.acmicpc.net/problem/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를 공백으로 구분하여 순서대로 출력한다.

 

예제 입력 : 

12 3
1 5 2 3 6 2 3 7 3 5 2 6

 

예제 출력 : 

1 1 1 2 2 2 2 2 3 3 2 2

 

접근법 : 

1) 어떻게 풀 것인가?

기본적으로 특정 구간에 대한 숫자를 출력해야하는 문제이다.

구간합, 또는 구간의 최대 최소를 구하는 문제이므로 인덱스드트리를 떠올려봤다.

 

인덱스드트리를 이용할 경우 시간복잡도는 N logN으로 500만*22.25 = 1억을 초과해 아마도 시간초과가 발생할 것이다.

N logN의 시간복잡도로 불가능한 문제로 기본적으로 N의 시간복잡도를 가져야 기타 로직이 더해져 통과할 수 있는 문제이다.

 

N의 시간복잡도로 문제를 해결하려면 보통 2가지 방법이 있다.

Stack, Deque, Priority Queue 등 FIFO, LIFO 등 특성을 이용해 자료구조로 문제를 해결하거나,

메모이제이션을 통해 문제를 해결해야한다.

 

메모를 통해 문제를 해결하기위해서는 범위를 초과할때 어떤 숫자를 빼야하는지 알아야하는데

단순 배열에서는 알기 어렵다.

(Ex> A[1] ~ A[30] 까지의 최솟값이 A[1]이고, L이 30일때 A[31]에서 A[1]은 L의 범위를 초과하므로 무조건 답에서 제외해야하는데 단순 배열에 메모이제이션을 했을 경우 어떤 녀석을 제외하는지 알기 어렵다.)

 

따라서 구조체 또는 클래스를 통해 id와 value 2개를 모두 갖고 있어야하고,

양방향으로 데이터를 넣고 뺄 수 있는 deque가 필요하다.

 

자세한 로직은 아래 코드 참고.

 

참고자료 : https://ko.wikipedia.org/wiki/%EB%8D%B1_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

덱 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

 

2) 시간복잡도

기본적으로 N번 입력 받으면서 모든 로직을 처리하기 때문에 O(N)으로 생각했는데,

최악의 경우 deque에 계속 데이터가 쌓이다가 한 번씩 while문을 쭉 돌면서 deq.pop_back( ) 을 실행한다면 조금 더 높은 시간복잡도가 나올 것으로 예상. 정확한 측정은 하기 힘듦.

(Cpp 기준 2,244ms → 시간을 줄일 수 있는 요소를 생각해보면 더 좋음)

 

3) 공간복잡도

입력받으면서 처리하면 되고 L이 최대 500만이므로 여유있음

 

4) 풀면서 놓쳤던점

Cpp로 해도 2,244ms 가 소요되서 시간을 줄일 수 있는 방법을 생각해보는게 좋을 듯.

 

5) 이 문제를 통해 얻어갈 것

deque의 기본적 활용.

양방향으로 다 push, pop이 될때의 장점 활용.

 

** priority queue 테스트

  - 동일 로직 코드로 진행

 1) Java - time out

 2) C++ scanf / printf - time out

 3) C++ cin.tie / cout.tie - 1,980 ms     ( C++ deque - 1,596 ms)

 

 

Java 코드 : 

import java.io.*;
import java.util.*;

//최솟값 찾기 11003
public class Main {
	
	static class info {
		public int id;
		public int val;

		info(int id, int val) {
			this.id = id;
			this.val = val;
		}
	}

	public static void main(String[] args) throws Exception {
		
		// 1. 입력 받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());

		ArrayDeque<info> dq = new ArrayDeque<>();

		st = new StringTokenizer(br.readLine());
		int input;
		
		// 2. 입력받으면서 투포인터 실행
		for (int i = 0; i < N; i++) {
			
			input = Integer.parseInt(st.nextToken());
			
			// 1) deque의 첫번째 숫자의 id가 i-L보다 작다면?
			//    → id 기준으로 오래된 숫자 제거
            if (!dq.isEmpty() && dq.getFirst().id <= i - L) {
            	dq.pollFirst();
            }
            
            // 2) deque의 first 숫자를 최솟값으로 만들기
            //    deque의 last부터 제거 (방금 input된 값과 비교)
			//    → id 기준으로 오래된 숫자 제거
			while (!dq.isEmpty() && dq.getLast().val >= input) {
				dq.pollLast();
			}
			
			// 3) 방금 input 된 값이 나중에 최솟값이 될 수도 있으므로 무조건 넣기
			dq.addLast(new info(i, input));
			
			// 현재 deque의 first 값은 최솟값을 보장함
            sb.append(dq.getFirst().val+" ");
		}
		sb.append("\n");
		bw.write(sb.toString());
		
		br.close();
		bw.flush();
		bw.close();
	}

}

 

 

Cpp 코드 (deque) : 

// 최솟값 찾기 11003
#if 1
#include <stdio.h>
#include <deque>

using namespace std;

typedef struct st {
	int id, val;		// id : 입력받은 순서, val : 값
	st(int id, int val) {
		this->id = id;
		this->val = val;
	}
}node;

int N, L;			// N 숫자 개수, L 최솟값을 구할 범위 (D[i] = A[i-L+1] ~ A[i] 의 최솟값
int i, input;		// i 입력받는 순서, input 입력받은 값
deque<node> deq;	// 앞뒤로 pop이 가능한 deque를 이용 (최대 L개만 갖고 있을 예정)

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &L);
	for (i = 0; i < N; i++) {
		// 상황 : 제약조건인 deque의 첫번째 숫자의 id가 i-L보다 작다면? 
		// 동작 : 오래된 숫자 제거
		if (!deq.empty() && deq.front().id <= i - L) deq.pop_front();
		// 새로운 숫자의 입력
		scanf("%d", &input);
		// 목표 : deque의 first숫자를 최솟값으로 만들기 위해서
		// 상황 : deque의 last부터 비교해가면서 input보다 기존 값이 더 클 경우
		// 동작 : 제거해줌 (왜냐하면 지금 input된 값보다 쓸모가 없는 값이므로 제거)
		while (deq.size() && deq.back().val >= input) {
			deq.pop_back();
		}
		// 지금 input된 값은 나중에 최솟값이 될 수도 있으므로 무조건 넣어줌
		deq.push_back(node(i, input));
		// 현재 deque의 first 값은 최솟값을 보장함
		printf("%d ", deq.front().val);
	}
	return 0;
}
#endif

 

C++ 코드 (priority queue) : 

#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <queue>

#define MAX (52)

using namespace std;

int N, L;
int ans;						// ans : 정답

typedef pair<int, int> pii;

struct compare
{
	bool operator()(pii& o1, pii& o2) {
		return o1.second > o2.second;
	}
};

int main() {
	// 1. 입력받으면서 
	//freopen("input.txt", "r", stdin);
	//scanf("%d %d", &N, &L);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> L;

	int input;
	priority_queue<pii,vector<pii>,compare> pq;

	for (int i = 0; i < N; i++) {
		cin >> input;

		pq.push({ i, input });

		while (!pq.empty() && pq.top().first <= i - L ) {
			pq.pop();
		}
		cout << pq.top().second << ' ';
		//printf("%d ", pq.top().second);
	}
	
	return 0;
}
#endif