끄적끄적

문제풀이

 주어진 조건에 맞게 정렬하는 문제이다. 

 1. 장르별로 각 곡이 몇 번 재생되었는지를 가지고 있는 딕셔너리(g_songs)와 각 장르가 총 몇번 재생되었는지를 가지고 있는 딕셔너리(g_num)을 선언한 뒤, 주어진 genres와 plays에서 하나씩 꺼내며 적절히 넣는다.

* g_songs는 key 가 장르명이고 value는 (곡 번호, 재생수))인 튜플들로 이루어진 리스트이다.

* g_num은 key가 장르명이고 value는 그 장르의 모든 곡들의 재생수의 합이다.

 2. 주어진 곡들을 모두 넣은 후, g_num의 key를 value에 따라 정렬한다. (정렬의 첫번째 조건인 "속한 노래가 많이 재생된 장르를 먼저 수록합니다."를 먼저 수행)

 3. 2에서 정렬된 순서대로 각 장르별로 g_songs에서 value들을 가져와 각 곡의 재생수인 튜플의 두번째 요소로 정렬한 후, 같다면 곡 번호인 튜플의 첫번째 요소로 정렬해 준다. (정렬의 두, 세번째 조건 수행)

Python Code

Line 3의 comparator 함수는 과정 3을 수행하는 함수로 cmp_to_key 를 이용하여 line 34에서 sort함수의 key로 활용됩니다.

Line 18 의 i는 각 곡의 고유 번호로, for문은 과정 1을 수행합니다.

Line 28 ~ 29는 과정 2의 장르를 장르별 총 재생수로 정렬하는 과정입니다.

Line 34는 장르별로 해당 곡들을 꺼내와 정렬하는 과정입니다.

문제 링크

문제풀이

 works의 요소들의 제곱의 합이 가장 작게 하면 되는 문제로, works 요소들에서 주어진 n만큼을 적절히 빼서 works의 요소들의 최댓값을 가장 작게 만들어주면 된다. 따라서 가장 단순한 풀이로는, works를 정렬해가며 최댓값인 요소에서 1씩 빼는 과정을 n번 반복하면 된다. 

 하지만 위와 같은 방법으로 풀게되면, 당연히 효율이 좋지 못하므로, 더 효율적인 풀이를 고려해야한다. 제 풀이는 다음과 같습니다.

 1. works를 정렬한 후, i를 1씩 늘려가며 works의 i-1번째 요소까지의 모든 요소들의 값을 같게 하는데,

 1-1. 만약 works의 0번째부터 i-1번째 요소들을 모두 i번째 요소와 같도록 만들 수 있다면 바꾼 후, 바꿔준 만큼 n에서 빼줍니다.

 1-2. 불가능하다면 1과정을 멈춘다.

 2. 1-1을 거쳐 값을 똑같이 맞춰줄 수 있었던 요소들에 대하여 남은 n을 공평하게 배분한다.

 3. 남은 값들을 앞에서부터 1씩 배분한다.

예시

 works = [3,5,7], n = 3인 경우를 예로 들어보면 다음과 같다.

알고리즘이 동작하는 과정을 편의상 t라고 했습니다. 

t=0은 과정 1의 정렬을 하는 과정입니다.

t=1은 works의 두번째 요소(works[1])까지의 요소들의 값들이 같도록 만드는 과정입니다. works[0]을  works[1]과 같도록 만들 수 있으므로 바꾸어주고 n에서 works[0]-works[1]을 빼줍니다. i가 2 이상이라면 i*(works[i-1]-works[i])를 빼주면 됩니다. 

t=2는 과정 2인데, 0이 아닌 요소가 3개인데, n은 1이므로 이 과정은 진행되지 않지만, 이해를 돕기위해 넣었습니다.

t=3은 과정 3으로, 남아있는 n을 앞에서부터 1씩 처리하는 과정입니다.

이제 t=3에서의 요소의 값들을 제곱하여 반환하면 됩니다.

* 시간복잡도는 최악의 경우 for문 3번으로 끝나므로, works의 길이를 N이라 하면 O(NlonN + N)이 됩니다(정확히는 O(NlonN + 3N)).

Python Code

line 6의 for문이 과정 1(equal index까지 요소들의 값이 같게 됩니다.),

line 19이 n을 공평하게 처리하는 부분,

line 23이 남은 n을 1씩 앞에서부터 처리하는 부분입니다.

문제링크