[백준][C] 2238 경매

https://www.acmicpc.net/problem/2238

파이썬을 사용하면 딕셔너리를 사용해 간단하게 구할 수 있을 것 같지만 C언어에는 직접 구현해야하므로 배열을 사용해 구하기로 했다.

일단 문제에서 주어진 조건은 다음과 같다.

1. 가장 적은 수의 사람이 제시한 가격을 택한다.
2. 사람의 수가 같을 경우 가장 낮은 가격을 택한다.
3. 출력은 해당하는 가격을 제일 먼저 제시한 사람을 출력한다.

 

구현은 다음과 같은 방법으로 했다.

1. 개수를 세는 cnt 배열을 통해 가격에 따른 개수를 센다 (cnt[가격] = 해당 가격의 개수)
2. 가격을 낮은 값부터 돌며 사람의 수가 가장 적은 가격을 찾는다.
3. 다시 사람을 돌며 위에서 찾은 가격과 일치하는 사람을 찾으면 출력하고 종료한다.

이때 for문이 낮은 값부터 돌기 시작하므로 제일 먼저 나오는 값이 최소값임을 이용한다.

밑은 C언어로 구현한 방법이다.

#include <stdio.h> 
#pragma warning(disable:4996)

char name[100000][11];
int U, N;
int P[100000];
int cnt[10001] = { 0 };

int main()
{
	scanf("%d %d", &U, &N);

	// 값을 입력받으면서 cnt 배열에 개수를 더해준다.
	for (int i = 0; i < N; i++)
	{
		scanf("%s %d", name[i], &P[i]);
		cnt[P[i]]++;
	}

	int min = 10000;
	int idx = 0;
	// 모든 가격을 순회하며 개수가 가장 적은 최소값을 찾는다.
	for (int i = 1; i <= U; i++)
	{
		if (cnt[i] == 0) continue;
		if (min > cnt[i])
		{
			min = cnt[i];
			idx = i;
		}
	}

	// 이제 다시 처음 배열을 돌며 해당하는 가격을 제시한 사람을 출력한다.
	for (int i = 0; i < N; i++)
	{
		if (idx == P[i])
		{
			printf("%s %d\n", name[i], P[i]);
			break;
		}

	}
	
	return 0;
}