[Python][SWEA] 20728. 공평한 분배 2 D3

🗒️ 파이썬 코드 풀이

T = int(input())
for tc in range(1,T+1):
    N,K = map(int,input().split())
    lst = list(map(int,input().split()))
    lst.sort()

    candle_mn = lst[K-1]-lst[0]
    for i in range(1,len(lst)-K+1):
        tmp = lst[i:i+K]
        candle_mn = min(candle_mn,(tmp[K-1]-tmp[0]))

    print(f"#{tc} {candle_mn}")

 

1. 투포인터 알고리즘 방식으로 진행한다.

 

2. 우선 lst를 오름차순으로 정렬해준다.

 

3. candle_mn (최소값)을 초기값으로 설정한다.

 

4. N-K+1 만큼 만복을하면서 candle_mn의 값을 생신해준다. 

 

 

📌 나의 잘 못된 코드

from itertools import combinations

T = int(input())
for tc in range(1,T+1):
    N,K = map(int,input().split())
    lst = list(map(int,input().split()))

    comb_lst = list(combinations(lst,K))
    min_com= 10e6
    for c in comb_lst:
        min_com = min(min_com,(max(c)-min(c)))

    print(f"#{tc} {min_com}")

 

조합으로 itertools 쓸 생각으로 행복사 ...  결국에는 시간초과가 떴다 ㅠㅠ 

N의 범위가 50인데, 50까지 조합으로 하는것을 무리인가보다...

 

T = int(input())
for tc in range(1,T+1):
    N,K = map(int,input().split())
    lst = list(map(int,input().split()))
    lst.sort()

    candle_mn = 10e4
    for i in range(0,len(lst)-K+1):
        tmp = lst[i:i+K]
        candle_mn = min(candle_mn,(tmp[K-1]-tmp[0]))

    print(f"#{tc} {candle_mn}")

 

두번째는 candle_mn 설정은 10e4 아주 큰값으로 설정해서, 무조건 candle_mn이 갱신되도록 시도했는데,

93번째 케이스에서 에러가 발생했다. 아마 저 값이 갱신 안된 케이스 인 것 같다.

최소값,최대값을 초기 설정할때는 리스트의 처음 값으로 갱신해주자.

🧐 문제 코멘트

itertools의 combinations를 쓸 생각해 행복했었지만... 런타임 에러 

그래도 투포인터 방식으로 크게 어렵지는 않았다.

---

📚 문제

사탕이 담긴 N개의 주머니가 있다. 이 중 i (1≤i≤N) 번째 주머니에는 사탕이 ai개 들어 있다. 당신은 이 주머니 중 정확히 K개를 선택하여 어린이들에게 나누어 주려고 한다.
공정성을 위해, 당신은 나눠 준 주머니 가운데 사탕의 개수가 가장 많은 것과 가장 적은 것의 사탕 개수 차이를 최소화하려고 한다.
모든 유효한 방법 중 차이의 최솟값을 구하는 프로그램을 작성하라.
 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 두 개의 줄로 이루어진다. 첫 번째 줄에는 주머니의 개수 N (2≤N≤50)과 나눠 줄 주머니의 개수 K (2≤K≤N)이 공백 하나를 사이로 두고 주어진다.
두 번째 줄에는 주머니 속 사탕의 개수를 나타내는 N개의 정수 a1,a2, ⋯ ,aN(1≤ai≤109)이 공백 하나씩을 사이로 두고 주어진다.
 

출력

각 테스트 케이스마다, 차이의 최솟값을 출력한다.