[이진탐색] 작품상 투표

문제

영화제에서 작품상을 투표한다. 후보작품은 N개이며 투표 참여 인원은 M명이다.

투표 용지에 1~10점의 점수가 써있고 작품이름이 써있다.

그런데 잘못 기입된 작품 이름이 있어 해당 표는 무효표 처리한다고 한다.

작품상 투표가 완료되었을때, 상위 3등을 구하라.

단, 동점일시 후보번호가 빠른 순서가 상위로 한다.

 

입력

N은 5부터 10000이다.

작품이름은 20자 이하 알파벳이며

M은 5부터 100000이다.

5

ABC Apple Banana Melon Skycastle

6

Banana 3

Melon 3

Apple 1

ABC 1

SKcastle 10

ABC 1

 

출력

Banana 3

Melon 3

ABC 2

---

문제해결

후보자별 이름과 투표용지의 이름을 1:1로 대조하여 모든 비교를 한다. 그럼 시간복잡도 O(N*M)일 것이다.

그러나 N과 M이 각 10000과 100000이기 때문에 Timeout이 발생할 것이다. 코드는 아래와 같다.

#include <stdio.h>
#include <string.h>

int N;
char name[10000+100][20+10];
char voteN[100000+100][20+10];
int voteS[100000+100];
int M;

struct data
{
	int id;
	int score;
}typedef Data;

Data candi[100000+10];

void Input()
{
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%s", name[i]);
	}
	scanf("%d", &M);
	for(int i=0; i<M; i++){
		scanf("%s", voteN[i]);
		scanf("%d", &voteS[i]);
	}
	
}

void Solve(){
	for(int i=0; i<N; i++){ //후보자
		candi[i].id = i;
		candi[i].score =0;
		for(int j=0; j<M; j++) //투표용지
		{
			if(strcmp(name[i],voteN[j])==0)	
			{
				candi[i].score += voteS[j];
			}
		}
	}
	
	for(int i=0; i<3; i++){
		for(int j=i+1; j<N; j++){
			if(candi[i].score < candi[j].score || (candi[i].score == candi[i].score && candi[i].id > candi[j].id))
			{
				Data temp;
				temp = candi[i];
				candi[i]= candi[j];
				candi[j]=temp;
			}
		}
	}
	
	for(int i=0; i<3; i++)
	{
		printf("%s %d\n", name[candi[i].id], candi[i].score);
	}
}

int main() {
	Input();
	
	Solve();
	
	return 0;
}

 

For문으로 순차 탐색을 하는 것보다 정렬 상태에서 이진탐색으로 수행하면 NlogN의 시간 복잡도로 해결할 수 있다.

투표용지의 작품이름 순서대로 오름차순 정렬 후 이진탐색을 실시한다.

단, 인덱스만 저장하여 오름차순 해주는 편이 훨씬 편리하다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int N;
char name[10000+100][20+10];
char voteN[100000+100][20+10];
int voteS[100000+100];
int M;
int idx[100000+100];

struct data
{
	int id;
	int score;
}typedef Data;

Data candi[100000+10];

void Input()
{
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%s", name[i]);
	}
	scanf("%d", &M);
	for(int i=0; i<M; i++){
		scanf("%s", voteN[i]);
		scanf("%d", &voteS[i]);
	}
	
}

int comp(const void* a, const void* b){
	const int x = *(const int*)a;
	const int y = *(const int*)b;
	return strcmp(voteN[x], voteN[y]);
}

int bslow(int s, int e, int d){ //가장 작은 문자열 찾기
	int m;
	int sol=-1;
	int r;
	
	while(s<=e){
		m = (s+e)/2;
		r = strcmp(voteN[idx[m]], name[d]);
		if(r==0){
			sol = m; e=m-1;
		}
		else if(r>0) e=m-1;
		else s=m+1;
	}
	return sol;
}

void Solve(){
	//idx만 오름 차순 정리
	for(int i=0; i<M; i++){
		idx[i]=i;
	}
	qsort(idx, M, sizeof idx[0], comp);
	
	for(int i=0; i<N; i++){
		candi[i].id = i;
		candi[i].score = 0;
		int low = bslow(0,M-1,i);
		if(low<0) continue;
		for(int j=low; (j<M) && !strcmp(name[i], voteN[idx[j]]); j++){
			candi[i].score += voteS[idx[j]];
		}
	}
	
	
	
	
	for(int i=0; i<3; i++){
		for(int j=i+1; j<N; j++){
			if(candi[i].score < candi[j].score || (candi[i].score == candi[i].score && candi[i].id > candi[j].id))
			{
				Data temp;
				temp = candi[i];
				candi[i]= candi[j];
				candi[j]=temp;
			}
		}
	}
	
	for(int i=0; i<3; i++)
	{
		printf("%s %d\n", name[candi[i].id], candi[i].score);
	}
}

int main() {
	Input();
	
	Solve();
	
	return 0;
}