Boj 20136 c++ 멀티탭 스케줄링 2

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

 

 

문제 & 조건

멀티탭의 플러그 개수와 전기용품 사용 순서의 길이를 제외하고는 1700 과 동일하다.

달라진 점은 N과 K가 최대 500000이라는 점.

 

접근

 

N과 K가 작을 때에는 플러그를 교체해야 하는 시점에 전기용품 배열을 완전탐색하여 가장 오랫동안 사용되지 않을 전기용품을 

찾아 그것을 멀티탭에서 제거할 수 있었다.

그리고 임의의 전기용품이 이미 멀티탭에 존재하는지 여부를 검사할 때에도 완전탐색을 통해 알아낼 수 있었다.

 

하지만 K개의 전기용품에 대해서 완전탐색을 진행하였을 때의 최악 연산 횟수는 N * K / 2 로 

이 문제에서는 N과 K의 범위가 각각 500000 이기에 이전 문제와 같은 방법으로는 TLE를 받을 수 있다.

즉, 최적화가 필요하다.

 

 

최적화

최적화해야 하는 부분은 멀티탭에 있는 전기 용품 중에서 현재 위치를 기준으로 가장 멀리 떨어져 있는 것을 구하는 코드이다.

플러그 교체 횟수를 구하기 위해서 K(전기용품의 개수) 만큼의 순회는 불가피하다.

즉, 시간 제한에 맞추기 위해서는 교체할 전기용품을 찾는 코드의 복잡도를 최소한 O(logN) 까지 줄여야 한다.

 

때문에, 교체해야 하는 전기용품을 찾을 때에는 최댓값만을 빠르게 취하는 최대힙을 사용하고 우선순위의 기준은 현재 위치에서 떨어진 거리여야 하겠다고 생각했다.

'가장 멀리 떨어져 있다'를 판단하기 위해서는 두 물건 사이의 간격을 저장해놓아야 한다.

 

때문에, 입력을 받을 때 부터 전처리를 해주기로 했다.

 

 

 

구현

구현하느라 정말 애를 많이 먹었다. 

최적화를 하는 과정에서 여러가지 문제들이 있었다.

 

첫번째 문제는 

최대힙에 들어간 거리 정보와 인덱스 정보(어떤 전기용품을 교체할지) 를 어떻게 대응시킬지 였다.

 

이는 입력값이 pair<int, int> 일 때, 첫번째 값을 기준으로 우선순위가 부여되는 특성을 이용하여 해결할 수 있었다.

첫번째 값으로 거리를, 두번째 값에는 전기용품의 인덱스 또는 전기용품의 물건 번호를 넘겨주면 된다.

 

두번째 문제는 

전기용품이 이미 멀티탭에 있을 때에는 거리를 갱신해줘야 한다 는 것이였다.

 

최대힙에는 전기용품의 정보와 다음 지점까지의 거리가 저장되어있다. 때문에, 이미 존재하는 경우에도 거리를 갱신해주어야 한다.

하지만 라이브러리에서 제공되는 우선순위 큐는 인덱스 기반 값 수정이 불가능하므로 인덱스를 기반으로 직접 값을 삭제할 수 있는 최대힙을 구현했다.

 

다 풀고 나서야 굳이 삭제하지 않아도 우선순위 때문에 그냥 push 해줘도 된다는 것을 알게 되었다. (삽질)

 

세번째 문제는

현재 위치가 변할 때 마다 dist배열의 값도 수정해줘야 한다 는 것이였다.

 

처음에는 dist[idx] 배열의 정의를 arr[idx]가 다음 등장하기 까지의 거리로 했었다.

하지만 이는 거리를 검사하는 기준이 변화함에 따라 대소관계가 망가지는 문제가 있었다.

때문에 dist배열의 정의를 '시작 지점에서 다음에 등장하기 까지의 거리' 로 바꾸어 기준을 모두 맞춰주었다.

 

 

정답 코드 (삽질) 

 

#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_map>
#define Max 500001
using namespace std;

int dist[Max], arr[Max], N, K;
set<int> s, page;
unordered_map<int, int> pr;

typedef struct st {
    int d;
    int v;
} HEAP;

HEAP heap[Max];
int heapIdx[Max]; // 삭제하려 하는 값이 heap의 어느 위치에 있는지
int hn = 0;

bool is_max(HEAP a, HEAP b) {
    return a.d > b.d;
}

HEAP pop() {

    HEAP ret;

    ret = heap[1];  // 최대힙
    heap[1] = heap[hn]; // 최대힙 리프노드로 바꾸기
    heap[hn].d = -1; // 바꾼 리프노드 무효화하기
    heap[hn].v = -1;
    hn--; // 원소 개수 조정

    for(int i = 1; i * 2 <= hn;) {
        if (is_max(heap[i], heap[i * 2]) && is_max(heap[i], heap[i * 2 + 1])) break;

		else if (is_max(heap[i * 2], heap[i * 2 + 1])) {
            swap(heap[i], heap[i * 2]);
			heapIdx[heap[i].v] = i;
			heapIdx[heap[i * 2].v] = i * 2;

			i = i * 2;
		} else {
			swap(heap[i], heap[i * 2 + 1]);
			heapIdx[heap[i].v] = i;
			heapIdx[heap[i * 2 + 1].v] = i * 2 + 1;

			i = i * 2 + 1;
		}
    }
    return ret;
}

void push(int a, int b) {
	hn++;
	heap[hn].d = a;
	heap[hn].v = b;
	heapIdx[b] = hn;
	for (int i = hn; i > 1; i /= 2)
	{
		if (is_max(heap[i / 2], heap[i])) break;

		swap(heap[i], heap[i/2]);

		heapIdx[heap[i].v] = i;
		heapIdx[heap[i / 2].v] = i / 2;
	}
}
void delete_val(int a) {
	int delhn = heapIdx[a];
	heap[delhn].d = Max;

	for (int i = delhn; i > 1; i /= 2)
	{
		if (is_max(heap[i / 2], heap[i])) break;

		swap(heap[i], heap[i/2]);

		heapIdx[heap[i].v] = i;
		heapIdx[heap[i / 2].v] = i / 2;
	}

	pop();
}


int main() {

    cin >> N >> K;

    for(int i = 0; i < K; i++) {
        cin >> arr[i];
        if(s.find(arr[i]) == s.end()) {
            s.emplace(arr[i]);
            pr[arr[i]] = i;
            dist[i] = Max;
        } else {
            dist[pr[arr[i]]] = i;
            pr[arr[i]] = i;
            dist[i] = Max;
        }
    }

    int pg = 0, ans = 0;

    for(int i = 0; i < K; i++) {
        if(page.find(arr[i]) != page.end()) {
            delete_val(arr[i]);
            push(dist[i], arr[i]);
            continue;
        } else if(pg < N) {
            page.emplace(arr[i]);
            push(dist[i], arr[i]);
            pg++;
        } else {
            int most_not_used = pop().v;
            page.erase(most_not_used);
            page.emplace(arr[i]);
            push(dist[i], arr[i]);
            ans++;
        }
    }
    cout << ans << "\n";

}

 

 

 

 

 

정답코드 (수정본)

 

#include <iostream>
#include <queue>
#include <set>
#include <map>
#define Max 500001
using namespace std;

int dist[Max], arr[Max], N, K;
priority_queue<pair<int, int>> pq;
set<int> s, page;
map<int, int> pr;

int main() {

    cin >> N >> K;

    for(int i = 0; i < K; i++) {
        cin >> arr[i];
        if(s.find(arr[i]) == s.end()) {
            s.emplace(arr[i]);
            pr[arr[i]] = i;
            dist[i] = Max;
        } else {
            dist[pr[arr[i]]] = i;
            pr[arr[i]] = i;
            dist[i] = Max;
        }
    }

    int pg = 0, ans = 0;

    for(int i = 0; i < K; i++) {
        if(page.find(arr[i]) != page.end()) {
            pq.push({dist[i], i});
            continue;
        } else if(pg < N) {
            page.emplace(arr[i]);
            pq.push({dist[i], i});
            pg++;
        } else {
            int most_not_used = pq.top().second;
            pq.pop();
            page.erase(arr[most_not_used]);
            page.emplace(arr[i]);
            pq.push({dist[i], i});
            ans++;
        }
    }
    cout << ans << "\n";
    /*for(int i = 0; i < K; i++) {
        cout << dist[i] << " ";
    }
    */
}

 

 

 

 

삽질을 많이 했지만 자력으로 풀어내어 뿌듯하다. 앞으로 구현이 어려운 문제도 많이 풀어봐야겠다.