[SWEA] 3347. 올림픽 종목 투표

문제

2018년 올림픽은 한국에서 열린다.

이전 올림픽에서 채택되었던 종목에 더해 하나의 종목을 더 추가하려고 하는데, 다음과 같은 투표 과정을 거친다.


조직위원회가 정식 종목으로 새롭게 채택하고자 하는 종목 N개에 대해 재미가 있다고 생각되는 순서대로 나열한 리스트가 있다.

위에서부터 i번째로 있는 종목이 i번째로 재미있는 종목인 것이다.

또한 i번 종목을 개최하는데 드는 비용은 Ai이다.

조직위원회는 총 M명으로 구성되어 있으며, 순서대로 1번 위원에서 M번 위원이다.

j번 위원은 개최 비용이 Bj를 넘지 않는 종목 중에서 가장 재미있는 경기에 표를 준다.

이 기준에 부합하는 경기는 모든 위원에 대해 반드시 존재한다.

가장 많은 표를 획득한 경기는 하나이다.


첫 번째 테스트 케이스를 예를 들어보자.

N = 4개의 종목의 리스트와 M = 3명의 조직위원회가 있다.


종목 A1 = 5, A2 = 3, A3 = 1, A4 = 4
조직 위원회 B1 = 4, B2 = 3, B3 = 2


조직위원회 B1 이하이면서 가장 앞쪽에 있는 종목은 A2 = 3 이다.

조직위원회 B2 이하이면서 가장 앞쪽에 있는 종목은 A2 = 3 이다.

조직위원회 B3 이하이면서 가장 앞쪽에 있는 종목은 A3 = 1 이다.


조직 위원회의 투표가 끝나면 A2가 2표, A3가 1표, A1, A4가 각각 0표로 A2가 정식 종목으로 채택 된다.

이와 같이 종목 목록과 위원들의 정보가 주어질 때 가장 많은 표를 받은 종목은 몇 번인지 구하는 프로그램을 작성하라.

 

풀이방법

각 종목의 비용을 a[n], 조직위원회를 b[m], 각 종목 당 투표 수를 v[n]라고 할 때(0 <= i < n, 0<= j < n),

 

조직위원회는 종목 중 가장 재미있으면서(인덱스가 낮으면서) 비용이 본인이 생각한 비용보다 낮거나 같으면(a[i] <= b[j])이면 투표한다.

 

즉 낮은 a[i]를 낮은 인덱스부터 탐색하면서 b[j]를 만족하면 투표한다.

 

다시말해, a[i]를 낮은 인덱스부터 탐색하면서, b[j]의 값이 a[i]보다 낮다면 v[i]의 값을 1씩 증가시켜준다.

 

소스코드

package samsung;

import java.util.*;

public class s_3347 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[] a = new int[n];
			int[] b = new int[m];
			int[] v = new int[n];
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			for(int i = 0; i < m; i++) {
				b[i] = sc.nextInt();
			}
			
			for(int i = 0; i < m; i++) {
				for(int j = 0; j < n; j++) {
					if(a[j] <= b[i]) {
						v[j]++;
						break;
					}
				}
			}
			int idx = 0;
			int max = 0;
			for(int i = 0; i < n; i++) {
				if(v[i] > max) {
					idx = i;
					max = v[i];
				}
			}
			System.out.println("#" + t + " " + (idx + 1));
		}
	}
}