백준 1715번. 카드 정렬하기

 

해결방안

가장 적은 두 값을 더하여 다시 넣는 행위를 반복하여 쉽게 해결할 수 있었다.

시간 복잡도는 O(NlogN)이 나온다.

 

 

 

또 다른 방법으로는 2개의 큐를 이용하는 방법이 있다. 

첫번째 큐: a는 cards 리스트를 정렬한 다음 만든 큐

두번째 큐: b는 빈 큐

 

아래의 코드에서 보면 두 큐의 첫번째 원소끼리 비교하여 더 적은 숫자를 리턴하는데, 

a 큐에서는 이미 정렬된 상태이기 때문에 맨 앞이 가장 적은 숫자임을 보장한다.

b 큐에서는 더한 값들을 순서대로 추가하는데, 이럴 경우 뒤에 더한 값들이 무조건 먼저 더한 값들보다 클 수 밖에 없다.

따라서 b의 맨 앞이 가장 적은 숫자임을 보장한다.

 

이 경우도 힙과 마찬가지로 시간복잡도 O(NlogN)이 나온다.

 

정리

일반적으로 가장 큰 원소를 뽑아내라? 이건 그냥 힙 구현하라는 것

But 2개의 큐를 사용했을 때도 같은 시간 복잡도로 해결할 수 있었다.

만약에 카드 리스트가 이미 정렬되어있다고 문제에서 보장한다면 힙 보다 2개의 큐를 사용하는 편이 좀 더 효율적인 방법이 될거 같다!👍