[C/C++] 백준 9375번 - 패션왕 신해빈

 

 

 

<코드>

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int N, T;
int ans;
vector<pair<string, int>> v;
string s1, s2;

int main()
{
	cin >> T; // 테스트케이스 수

	while (T--)
	{
		ans = 1;
		cin >> N; // 의상 수

		for (int i = 0; i < N; i++)
		{
			cin >> s1 >> s2;

			if (v.size() == 0) // 맨 처음 값 벡터에 저장 후 1개 체크
			{
				v.push_back(pair(s2, 1));
				continue;
			}

			for (int j = 0; j < (int)v.size(); j++)
			{
				if (s2 == v[j].first)
				{
					v[j].second++; // 개수 체크
					break;
				}
				if (j == (int)v.size() - 1) v.push_back(pair(s2, 0)); // vector에 있지않은 원소라면 추가.			
			}
		}	
		for (int k = 0; k < (int)v.size(); k++) // 가능한 조합 수 구하기
			ans *= (v[k].second + 1);
		
		// 아무것도 안입는 경우인 1 빼기
		cout << ans - 1 << "\n"; // 줄바꿈 꼭하기

		v.clear(); // 벡터 비우기
	}
}

 

최악의 경우는 의상이 30개에 모든 의상의 종류가 다를 경우이며 경우의 수는 2^30-1으로 int형의 범위를 넘어서지 않는다. 조합의 수는 만약 상의 x2, 하의 x2, 신발 x2 인 경우에는 (2+1)*(2+1)*(2+1) - 1 = 26이며 아무것도 안 입는 경우인 1을 빼주어야 한다. 출력할 때 줄 바꿈을 제대로 처리하지 않아 30분 정도 헤매었던 것 같다.

 

+위의 코드는 좀 복잡하게 풀이를 하였고 문제분류에 맞게 해시 맵을 이용하여 풀이해봤습니다. (2021.05.26 추가)

 

 

<2021-05-26 해시맵을 이용한 풀이 추가>

#include<iostream>
#include<map>
#include<string>
using namespace std;

int N, T;
int ans;
string s1, s2;

int main()
{
	cin >> T; // 테스트케이스 수

	while (T--)
	{
		map<string, int> m; // Map<의상종류,의상수>

		ans = 1;
		cin >> N; // 의상 수

		for (int i = 0; i < N; i++)
		{
			cin >> s1 >> s2;

			// 해당key값이 존재하지 않을 경우 find함수는 end()리턴
			if (m.find(s2) == m.end()) 
			{
				m[s2] = 1;
			}
			else // 해당 key값이 존재할 경우
			{
				m[s2]++;
			}

		}

		for (auto iter : m) // iter.first = key, iter.second = value
			ans *= (iter.second + 1); // (의상수+1) 씩 곱하기
		
		cout << ans - 1 << "\n";
	}
}

 

문제에서 같은 이름을 가진 의상은 존재하지 않는다고 명시되어있기 때문에 의상 이름(s1)에 상관없이 의상 종류(s2)가 매핑되어있지 않다면 m[s2] = 1, 매핑되어있다면 m[s2]++을 하여 의상 종류별로 개수를 카운트하였습니다.

 

 

www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈