[KT_코딩마스터스] 분리수거장 (python)

KT_Aivle School의 코딩마스터스가 시작되었다! 

기록해두면 좋을 문제들은 기록해두고자 글을 작성하게 되었다.

코드 자세한 설명은 주석을 달아놓았으니 참고하면 되겠다..!!

 

 

문제 설명

 

두정동에는 N개의 아파트 단지가 일직선상에 존재합니다. 각 아파트 단지에는 1번부터 N번까지 번호가 붙어있습니다. 두정동 동사무소에서는 아파트 단지 중 한 곳에 분리수거장을 지으려고 합니다. 분리수거장으로부터 각 주민들까지의 거리의 합이 최소가 되도록 하려면 어떤 아파트 단지에 분리수거장을 지어야 하는지 구하세요. 분리수거장으로부터 어떤 주민까지의 거리는 분리수거장이 있는 아파트 단지의 위치와 해당 주민이 거주하는 아파트 단지의 위치의 차로 계산됩니다. 단, 조건을 만족하는 아파트 단지가 여러개일 경우, 더 작은 번호의 아파트 단지에 분리수거장을 짓습니다.

 

입출력 예

 

입력 #1

7
475 170
28 95
506 8361
51 3988
2 977
607 793
49 847

 

입력 #2

11

998 2607
9422 3358
806 80622
2848 4153
398 180
867 22219
6514 806
246 9462
906 43046
2592 289
8 8486

 

입력 값 설명

첫째 줄에 아파트 단지의 수 N(1 ≤ N ≤ 100)이 주어집니다. 다음 N개의 줄에는 i(1 ≤ i ≤ N)번 단지의 위치 D[i]와 i번 단지에 거주하는 사람의 수 A[i]가 주어집니다. 단, 서로 다른 아파트 단지의 위치가 같은 경우는 존재하지 않습니다. (0 ≤ D[i] ≤ 100,000), (1 ≤ A[i] ≤ 100,000)

 

 

출력 #1

3

 

출력 #2

3

 

출력 값 설명

첫째 줄에 분리수거장을 지을 아파트 단지의 번호를 출력합니다.

 

 

# 분리수거장으로부터 어떤 주민까지의 거리 = 분리수거장이 있는 아파트 단지 위치 - 주민이 거주하는 아파트 단지 위치
# 우!선! 모든 단지의 주민 수를 구한 뒤, 그 수의 중앙값(2로 나누면 됨)과 가까운 주민 수가 위치한 단지 번째 수를 출력하면 된다. 
# 단, 조건을 만족하는 아파트 단지가 여러개일 경우, 더 작은 번호의 아파트 단지에 분리수거장을 짓습니다.  ----> 단지 위치 번호가 작은 순으로 sorting

n_list = []

n = int(input())  # 아파트 단지의 수

for _ in range(n):
    d, a = map(int, input().split())  # d = i번 단지의 위치, a = 단지에 거주하는 사람의 수
    n_list.append((d, a))  

# 누적 인구수
person_sum = sum(a for _, a in n_list)

def median_min(n_list):
    # 누적 인구수의 절반(중앙값)
    half_person = person_sum / 2
    # 누적 인구수 담을 변수
    cnt = 0 
    
    for d, a in sorted(n_list):   # 단지 위치 번호를 기준으로 sort --> 조건을 만족하는 단지가 여러 개일 경우, 더 작은 번호의 아파트 단지에 분리수거장을 짓기 위함.
        # 사람 수를 누적하면서 중앙값을 찾기
        cnt += a
        if cnt >= half_person:  # 누적 인구가 절반을 넘으면
        	# 그 단지의 원래 인덱스를 찾기 (1부터 시작하는 인덱스를 반환)
            return n_list.index((d, a)) + 1   # 저장된 데이터가 (위치, 사람 수) 형태의 튜플이기 때문에 'n_list.index((d, a))' 형태로 인덱스를 찾아야 한다.
    

print(median_min(n_list))