올림픽 종목 투표 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 3347

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWDTHsZ6r0EDFAWD&categoryId=AWDTHsZ6r0EDFAWD&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

2018년 올림픽은 한국에서 열린다. 이전 올림픽에서 채택되었던 종목에 더해 하나의 종목을 더 추가하려고 하는데, 다음과 같은 투표 과정을 거친다. 조직위원회가 정식 종목으로 새롭게 채택하고자 하는 종목 N개에 대해 재미가 있다고 생각되는 순서대로 나열한 리스트가 있다. 위에서부터 i번째로 있는 종목이 i번째로 재미있는 종목인 것이다. 또한 i번 종목을 개최하는데 드는 비용은 Ai이다. 조직위원회는 총 M명으로 구성되어 있으며, 순서대로 1번 위원에서 M번 위원이다. j번 위원은 개최 비용이 B(j)를 넘지 않는 종목 중에서 가장 재미있는 경기에 표를 준다. 이 기준에 부합하는 경기는 모든 위원에 대해 반드시 존재한다. 가장 많은 표를 획득한 경기는 하나이다. 첫 번째 테스트 케이스를 예를 들어보자. N = 4개의 종목의 리스트와 M = 3명의 조직위원회가 있다. 종목 A(1) = 5, A(2) = 3, A(3) = 1, A(4) = 4 조직 위원회 B(1) = 4, B(2) = 3, B(3) = 2 조직위원회 B(1) 이하이면서 가장 앞쪽에 있는 종목은 A(2) = 3 이다. 조직위원회 B(2) 이하이면서 가장 앞쪽에 있는 종목은 A(2) = 3 이다. 조직위원회 B(3) 이하이면서 가장 앞쪽에 있는 종목은 A(3) = 1 이다. 조직 위원회의 투표가 끝나면 A(2)가 2표, A(3)가 1표, A(1), A(4)가 각각 0표로 A(2)가 정식 종목으로 채택 된다. 이와 같이 종목 목록과 위원들의 정보가 주어질 때 가장 많은 표를 받은 종목은 몇 번인지 구하는 프로그램을 작성하라.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 N, M(1 ≤ N, M ≤ 1,000)이 공백으로 구분되어 주어진다. 두 번째 줄에는 N개의 정수 A(1)에서 A(N)이 공백으로 구분되어 주어진다. A(i)는 1이상 1000이하의 정수이다. 세 번째 줄에는 M개의 정수 B(1)에서 B(M)이 공백으로 구분되어 주어진다. B(j)는 1이상 1000이하의 정수이다.

출력

각 테스트 케이스마다 가장 많은 표를 획득한 경기의 번호를 출력한다.

예시

입력	출력
2 4 3 5 3 1 4 4 3 2 6 6 3 1 4 1 5 9 2 6 5 3 5 9	#1 2 #2 1

---

2. 문제풀이

간단하게 파이썬 내장함수와 카운팅기법으로 풀엇다. 심사위원기준으로 반복문을 시작하며 올림픽종목을 도는데 심사위원이 생각하는 가격안에 들어있다면 카운팅 한다. 모든 카운팅이 끝나게 되면 제일 많은 투표를 받은 종목을 출력한다.

---

3. 소스코드

#D4 3347 올림픽 종목 투표
 
for t in range(1, int(input()) + 1):
    #올림픽 종목과 심사위원 입력받기
    N, M = map(int, input().split())
    #올림픽 종목 비용 입력받기
    N_list = list(map(int, input().split()))
    #심사위원 생각비용 입력받기
    M_list = list(map(int, input().split()))
    #각종목당 투표갯수 저장변수
    count_list = [0]*N
    #심사위원을 기준으로 돈다
    for m in M_list:
        #올림픽 종목을 순회하면서 투표횟수를 카운팅한다.
        for i in range(len(N_list)):
            if N_list[i] <= m:
                count_list[i] += 1
                break
    #제일 많은 투표횟수를 얻은 인덱스를 구한다.
    result = count_list.index(max(count_list)) + 1
    print('#{} {}'.format(t, result))