[백준] 2461.대표 선수 (Swift)

[백준] 2461.대표 선수 (Swift)

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

2461번: 대표 선수

풀이

각 배열마다 수를 하나씩 뽑아 그 중 최대값과 최소값의 차이가 제일 작은 경우를 구하는 문제입니다.

 

처음에는 Heap 을 이용해 최소값을 모두 뽑은 다음, 최대값과 최소값의 차이를 계산한 뒤 그 중 최소값들을 삭제하고 다시 값을 뽑는 식으로.. 진행할 계획이었습니다.

 

입출력 예시는 모두 맞았지만, O(n^2) 정도로 코드를 작성하다보니 시간초과가 발생했습니다. 

 

그래서 다른 방법을 생각해보려고 했는데 도저히 떠오르지가 않아서.. 아래 링크를 참고했습니다.

대표선수 - 백준 2461 - swift

 

먼저 각 배열은 모두 내림차순으로 정렬된 상태고, 여기에서 최소값들을 뽑아 minHeap 에 삽입합니다. 삽입하는 과정에서 이 중 최대값을 따로 저장합니다.

 

그 다음 최대값과 최소값의 차이를 계산하고, 계산에 사용한 최소값은 삭제한 뒤 해당 최소값이 존재하던 배열에서 다음 값을 뽑아냅니다.

 

입출력 예시 2 를 예로 들자면 minHeap 에는 10, 40, 70, 100 이라는 값이 저장되어있고, 최대값과 최소값의 차이는 100 - 10 으로 90 입니다.

 

여기서 사용된 최소값은 10이기 때문에 10이 포함되어있던 원래 배열 10, 20, 30 에서 다음 최소값 20을 뽑아 minHeap 에 삽입해줍니다.

 

이 과정을 반복하면 최대값은 작게, 최소값은 크게 유지할 수 있기 때문에 최대값과 최소값이 차이가 감소합니다.

 

더 이상 배열에서 삭제할 원소가 없을때까지 반복합니다.

 

문제 풀이에 쓰인 Heap 관련 내용은 다음 링크에서 확인하실 수 있습니다.

[자료구조] Swift 로 Heap 구현하기

코드

	import Foundation
	let input = readLine()!.split(separator: " ").map { Int(String($0))! }
	let (n, m) = (input[0], input[1])
	var array = [[Int]]()
	var pq = Heap<Item>(<) // minHeap
	var top = 0 // 뽑은 최소값들 중 최대값
	var answer = Int.max
	for i in 0 ..< n {
	var line = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by: >) // 내림차순 정렬
	top = max(top, line.last!)
	pq.insert(Item(index: i, value: line.removeLast())) // pq 삽입
	array.append(line)
	}
	while !pq.isEmpty {
	let pop = pq.delete()! // 뽑은 최소값들 중 최소값
	answer = min(answer, top - pop.value)
	// 한 라인에서 다뽑으면 끝
	if array[pop.index].isEmpty {
	break
	}
	// 리스트 내 최대값 갱신
	top = max(top, array[pop.index].last!)
	// pq 삽입
	pq.insert(Item(index: pop.index, value: array[pop.index].removeLast()))
	}
	print(answer)
	// MARK: - 선언
	struct Item: Comparable {
	var index: Int
	var value: Int
	static func < (lhs: Item, rhs: Item) -> Bool {
	return lhs.value < rhs.value
	}
	}
	struct Heap<T: Comparable> {
	var heap: [T]
	// maxHeap >, minHeap <
	var compare: (T, T) -> Bool
	var root: T? {
	return heap.isEmpty ? nil : heap[0]
	}
	var isEmpty: Bool {
	return heap.isEmpty
	}
	init(_ compare: @escaping (T, T) -> Bool) {
	heap = []
	self.compare = compare
	}
	// 삽입
	mutating func insert(_ n: T) {
	heap.append(n)
	shiftUp(i: heap.count - 1)
	}
	// 삭제
	@discardableResult
	mutating func delete() -> T? {
	if heap.isEmpty {
	return nil
	}
	if heap.count == 1 {
	return heap.removeFirst()
	}
	heap.swapAt(0, heap.count - 1)
	let result = heap.removeLast()
	shiftDown(i: 0)
	return result
	}
	// 삽입 시 노드 상승
	mutating func shiftUp(i: Int) {
	var now = i
	// 현재 노드가 루트 노드보다 하위 노드일때
	while now > 0 {
	// 부모 노드 인덱스
	let parent = (now - 1) / 2
	// 부모 노드와 대소비교, 교환 필요 시
	if compare(heap[now], heap[parent]) {
	heap.swapAt(now, parent)
	// 교환 후 현재 노드를 원래 부모 노드가 있던 자리로 옮겨줌
	now = parent
	} else {
	break
	}
	}
	}
	// 원소 삭제 시 노드 하강
	mutating func shiftDown(i: Int) {
	var now: Int = i
	// 자식 노드 인덱스
	var child: Int = 2 * now + 1
	let count: Int = heap.count
	// 자식 노드가 트리 범위안에 있을때
	while child < count {
	// 왼쪽 자식, 오른쪽 자식 둘다 있을때
	if child + 1 < count {
	child = compare(heap[child], heap[child + 1]) ? child : child + 1
	}
	// 자식 노드와 대소비교 후 교환
	if compare(heap[child], heap[now]) {
	heap.swapAt(now, child)
	now = child // 현재 노드를 자식노드 인덱스로
	child = 2 * now + 1
	} else {
	break
	}
	}
	}
	}

view raw BOJ_2461.swift hosted with ❤ by GitHub