백준] 2890 - 카약(COCI 2009/2010)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 R과 C가 주어진다. 다음 R개 줄에는 '.', 'S', 'F', '1'~'9'로 이루어진 위성 지도가 주어진다. 한 줄에는 최대 한 개의 카약만 있고, 위성 사진에 있는 카약은 항상 9개이다. (10 ≤ R, C ≤ 50)

출력

출력은 총 9줄을 해야 한다. i번째 줄에는 i번 팀의 등수를 출력한다. (i=1~9)

소스코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct team {
	int id;
	int distance;
	int rank;
};
bool compareDistance(const struct team a, const struct team b)
{
	if (a.distance < b.distance)
		return true;
	else
		return false;
}
bool compareID(const struct team a, const struct team b)
{
	if (a.id < b.id)
		return true;
	else
		return false;
}
int main(void)
{
	int R, C, size = 9;
	cin >> R >> C;
	vector<string> picture(R);
	vector<struct team> list(size);
	for (int i = 0; i < R; i++)
		cin >> picture[i];

	for (int i = 0; i < 9; i++)
		list[i].id = i + 1, list[i].distance = -1;
	
	for (int i = 0; i < R; i++)
	{
		size_t pos;
		int teamNumber = 1;
		for (; teamNumber < size+1; teamNumber++)
		{
			pos = picture[i].find(to_string(teamNumber));
			if (pos != string::npos)
				break;
		}

		if (pos == string::npos)
			continue;
		else
			list[teamNumber - 1].distance = C - pos;
	}

	sort(list.begin(), list.end(), compareDistance);
	int rank = 1;
	for (int i = 0; i < size; i++)
	{
		list[i].rank = rank;
		if (i < size - 1)
		{
			if (list[i].distance < list[i + 1].distance)
				rank++;
		}
	}

	sort(list.begin(), list.end(), compareID);
	for (int i = 0; i < size; i++)
		cout << list[i].rank << '\n';
}

Tip

문자열 처리 문제로 카약의 크기가 고정되었다는 부분에서 문제 난이도가 매우 수월한 편이다.