[PS] BOJ 2457 (공주님의 정원)

문제부터 살펴보면 3월 1일부터 11월 30일까지 꽃이 지지 않게 하는 것이 핵심이다. 

이때의 입력은 각각 꽃이 피는 날과 꽃이 지는 날이 들어온다. 

 

1번째 접근

우선, 가장 먼저 생각나는 것은 특정 날짜 이전에 피는 꽃 중 가장 늦게 피는 꽃을 매 시행시 구하면 된다. 

하지만, 매 시행 시 $N$개의 꽃을 살펴보게 되기 때문에, 시작 복잡도는 $O(N^2)$이 된다. 해당 문제에서 $N$은 최대 100,000이기 때문에, $O(N^2)$은 시간 초과가 발생하게 된다. 

 

2번째 접근 

매 시행시 특정 날짜 이전에 피는 꽃 중 가장 늦게 피는 꽃을 상수 혹은 로그 시간에 구할 수만 있게 된다면, 시간초과가 발생하지 않고 문제를 해결할 수 있게 된다. 

 

이와 같이 그리디 한 풀이로 접근하면, 매 시행마다 꽃이 지는 날짜는 증가하게 될 것이다.

즉, 꽃이 지는 날짜는 다음 시행에서 선택할 꽃의 피는 날짜의 마지노선이기 때문에, 꽃이 피는 날짜를 기준으로 정렬을 해준다. 

 

이때, 꽃이 지는 날짜를 기준으로 정렬하는 우선순위 큐에 선택할 수 있는 꽃을 삽입한 후, 

매 시행시 우선순위 큐에서 원소를 빼내기만 하면 된다. 

우선순위 큐에서 원소의 삽입, 삭제는 $O(logN)$이므로, 총 시간 복잡도는 $O(NlogN)$이 된다. 

 

이를 코드로 옮겨보자면 다음과 같다. 

풀이 

우선, 스위프트에선 우선순위 큐를 제공하지 않아, 힙 자료구조부터 직접 구현해야 한다. 

우선순위 큐구현에 관환 내용은 해당 포스팅을 참고 바란다.

https://seokyoungg.tistory.com/91

[Data Structure] Priority Queue

 

// 시작날짜 기준으로 정렬
let sortedFlowers = flowers.sorted {
	$0.stDate < $1.stDate
}

다음과 같이 시작날짜 기준으로 정렬해 준 뒤,

while currentEnDate < targetEnDate {
	// 현재의 꽃이 지는날보다, 먼저 피는 꽃들을 우선순위 큐에 삽입한다.
	while
		flowerIndex < sortedFlowers.count &&
		sortedFlowers[flowerIndex].stDate <= currentEnDate {
		
		priorityQueue.push(sortedFlowers[flowerIndex])
		flowerIndex += 1
	}

	// 이후, 가장 늦게 지는 꽃을 선택한다.
	if let date = priorityQueue.pop() {
		currentEnDate = date.enDate
		result += 1
	} else {
		break
	}
}

매 시행마다, 선택 가능한 꽃들을 우선순위 큐에 삽입한 뒤, 가장 늦게 지는 꽃을 선택하면 된다. 

 

 

전체 코드 

Swift

import Foundation

struct Heap<T: Comparable> {
	enum HeapType {
		case min, max
	}
	
	private var nodes = [T]()
	private let sort: (T, T) -> Bool
	
	var isEmpty: Bool { nodes.isEmpty }
	var count: Int { nodes.count }
	var top: T? {
		guard !isEmpty else { return nil }
		return nodes[0]
	}
	
	init(type: HeapType) {
		switch type {
			case .min:
				sort = { $0 < $1 }
			case .max:
				sort = { $0 > $1 }
		}
	}
	
	mutating func insert(_ element: T) {
		nodes.append(element)
		shiftUp()
	}
	
	mutating func pop() -> T? {
		guard !isEmpty else { return nil }
		
		defer {
			nodes.swapAt(0, nodes.count - 1)
			nodes.removeLast()
			shiftDown()
		}
		
		return nodes[0]
	}
}

private extension Heap {
	mutating func shiftUp() {
		var now = nodes.count - 1
		var parent = getParent(of: now)
		
		while now > 0 && sort(nodes[now], nodes[parent]) {
			nodes.swapAt(now, parent)
			now = parent
			parent = getParent(of: now)
		}
	}
	
	mutating func shiftDown() {
		var now = 0
		
		while true {
			let (left, right) = getChilds(of: now)
			var candidate = now
			
			if left < nodes.count && sort(nodes[left], nodes[now]) {
				candidate = left
			}
			if right < nodes.count && sort(nodes[right], nodes[now]) && sort(nodes[right], nodes[left]) {
				candidate = right
			}
			
			if candidate == now { return }
			nodes.swapAt(now, candidate)
			now = candidate
		}
	}
	
	func getParent(of node: Int) -> Int {
		return (node - 1) / 2
	}
	
	func getChilds(of node: Int) -> (left: Int, right: Int) {
		return (node * 2 + 1, node * 2 + 2)
	}
}

struct PriorityQueue<T: Comparable> {
	private var heap: Heap<T>
	
	var isEmpty: Bool { heap.isEmpty }
	var count: Int { heap.count }
	var top: T? { heap.top }
	
	init(type: Heap<T>.HeapType) {
		self.heap = Heap(type: type)
	}
	
	mutating func push(_ element: T) {
		heap.insert(element)
	}
	
	@discardableResult
	mutating func pop() -> T? {
		heap.pop()
	}
}

struct FlowerDate: Comparable {
	let month: Int
	let day: Int
	
	static func < (lhs: FlowerDate, rhs: FlowerDate) -> Bool {
		if lhs.month == rhs.month {
			return lhs.day < rhs.day
		} else {
			return lhs.month < rhs.month
		}
	}
}

struct Flower: Comparable {
	let stDate: FlowerDate
	let enDate: FlowerDate
	
	init(_ stMonth: Int, _ stDay: Int, _ enMonth: Int, _ enDay: Int) {
		self.stDate = FlowerDate(month: stMonth, day: stDay)
		self.enDate = FlowerDate(month: enMonth, day: enDay)
	}
	
	init(_ arr: [Int]) {
		self.init(arr[0], arr[1], arr[2], arr[3])
	}
	
	static func < (lhs: Flower, rhs: Flower) -> Bool {
		lhs.enDate < rhs.enDate
	}
}

func solution() {
	let n = readInteger()
	var result = 0
	var flowers = [Flower]()
	var currentEnDate = FlowerDate(month: 3, day: 1)
	let targetEnDate = FlowerDate(month: 12, day: 1)
	var priorityQueue = PriorityQueue<Flower>(type: .max)
	
	for _ in (0..<n) {
		let informations = readIntergers()
		flowers.append(.init(informations))
	}
	
	// 시작날짜 기준으로 정렬
	let sortedFlowers = flowers.sorted {
		$0.stDate < $1.stDate
	}

	var flowerIndex = 0
	
	while currentEnDate < targetEnDate {
		// 현재의 꽃이 지는날보다, 먼저 피는 꽃들을 우선순위 큐에 삽입한다.
		while
			flowerIndex < sortedFlowers.count &&
			sortedFlowers[flowerIndex].stDate <= currentEnDate {
			
			priorityQueue.push(sortedFlowers[flowerIndex])
			flowerIndex += 1
		}

		// 이후, 가장 늦게 지는 꽃을 선택한다.
		if let date = priorityQueue.pop() {
			currentEnDate = date.enDate
			result += 1
		} else {
			break
		}
	}
	
	currentEnDate >= targetEnDate ? print(result) : print(0)
}

func readInteger() -> Int {
	Int(readLine()!)!
}

func readIntergers() -> [Int] {
	return readLine()!.split(separator: " ").map { Int($0)! }
}

solution()

 

 

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'

struct Date {
	int month = 0, day = 0;
};

int N;
vector<pair<Date, Date>> arr;

bool compareDate(Date a, Date b) {
	if(a.month == b.month) return a.day < b.day;
	return a.month < b.month;
}

bool compare1(pair<Date, Date> a, pair<Date, Date> b) {
	return compareDate(a.first, b.first);
}

bool compare2(pair<Date, Date> a, pair<Date, Date> b) {
	return compareDate(a.second, b.second);
}

void input() {
	cin >> N;
	
	Date date1, date2;
	for(int i = 0; i < N; i++) {
		cin >> date1.month >> date1.day >> date2.month >> date2.day;
		arr.push_back({date1, date2});
	}
}

bool isFinish(Date &a) {
	Date temp;
	temp.month = 11;
	temp.day = 30;
	
	return compareDate(temp, a);
}

int solve() {
	sort(arr.begin(), arr.end(), compare1);
	
	vector<pair<Date, Date>> temp;
	
	Date currentDate;
	currentDate.month = 3; currentDate.day = 1;
	int index = 0;
	int cnt = 0;
	while(index < N) {
		if(isFinish(currentDate)) return cnt;

		while(index < N && !compareDate(currentDate, arr[index].first)) {
			temp.push_back(arr[index ++]);
		}

		if(temp.size() == 0) return 0;
		sort(temp.begin(), temp.end(), compare2);
		currentDate = temp[temp.size()-1].second;
		cnt++;
		
		temp.clear();
	}

	if(!isFinish(currentDate)) return 0;
	return cnt;
}

int main() {
	FAST;
	input();
	cout << solve() << endl;
}