[ boj : 1148 ] 단어 만들기

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

1148번: 단어 만들기

해설 : 아우 이런 문제 미치겠어요 정말.... 그냥 빡구현 문제입니다.

 

제일 처음 사전에 담겨져 있는 단어들의 알파벳들을 [key : value] 형식으로 표현을 해줍시다. 벡터를 사용하던 이차원배열을 사용하던 취향대로 선택하시면 됩니다. 전 이차원 배열을 선택했습니다.

 

그 후에 퍼즐이 입력될때 2가지만 확인해 주면 됩니다.

 

1. 퍼즐에 존재하는 문자들로 사전의 단어를 만들 수 있는가??

2. 1을 통과 했다면, 퍼즐에 적혀있는 문자들을 일일히 확인해서 존재한다면 그 문자가 퍼즐의 가운데에 위치할 수 있으니 count 해준다.

 

2번을 진행할때 주의할 점은 중복된 문자는 그냥 패스해야 됩니다.

 

그럼 이를 그냥 출력해 주면 됩니다. 다만 구현하기가 좀 까다로워서 침착하게 공책에다가 적으면서 로직을 생각하세요.

#include<bits/stdc++.h>

using namespace std;

int A[200000][30], B[30];
int cnt[30],visit[30];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int len = 0;
	string str;
	for (int i = 0;; i++) {
		cin >> str;
		if (str == "-")break;
		for (int j = 0; j < str.length(); j++)
			A[i][str[j] - 'A'] += 1;
		len++;
	}
	for (int i = 0;; i++) {
		memset(B, 0, sizeof(B));
		memset(cnt, -1, sizeof(cnt));
		cin >> str;

		if (str == "#")break;
		for (int j = 0; j < str.length(); j++) {
			B[str[j] - 'A'] += 1;
			cnt[str[j] - 'A'] = 0;
		}
		for (int j = 0; j < len; j++) {
			bool flag = true;
			for (int k = 0; k < 26; k++) {
				if (B[k] - A[j][k] < 0) {
					flag = false;
					break;
				}
			}
			if (flag) {
				for (int k = 0; k < str.length(); k++) {
					if (A[j][str[k] - 'A'] > 0 && !visit[str[k] - 'A']) {
						cnt[str[k] - 'A'] += 1;
						visit[str[k] - 'A'] = 1;
					}
				}
			}
			memset(visit, 0, sizeof(visit));
		}
		int Min = (int)1e9;
		int Max = -1;
		for (int j = 0; j < 26; j++) {
			if (Min>= cnt[j] && cnt[j]!=-1)Min = cnt[j];
			if (Max <= cnt[j] && cnt[j]!=-1)Max = cnt[j];
		}
		string ans1="", ans2="";
		for (int j = 0; j < 26; j++) {
			if (Min == cnt[j])ans1 += j + 'A';
			if (Max == cnt[j])ans2 += j + 'A';
		}
		cout << ans1 << " " << Min << " " << ans2 << " " << Max << "\n";
		
	}
	return 0;
}