[백준] 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 구현하기

코드