[세번째 문제] 백준 / 1148 : 단어 만들기

하루에 한문제를 풀려고 했는데 이 문제에서 삼일을 헤맸다..
너무 슬프지만 어쨌든 해결했으니 다행이다.

(80명중 39위의 속도라 매우 뿌듯..!)

이 문제 또한 많은 점을 느낄수 있었는데 후술 하도록 하겠다.

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

// 단어 개수를 저장해놓으면 개수가 맞는지 + 가운데 글자가 있는지만 

char gameboard[9];

int main() {
	int wordcnt = 0;
	int** arr = new int* [200001];
	for (int i = 0; i < 200001; i++) {
		arr[i] = new int[26];
	}
	for (int i = 0; i < 200001; i++) {
		for (int j = 0; j < 26; j++) {
			arr[i][j] = 0;
		}
	}
	int** board = new int* [200001];
	for (int i = 0; i < 200001; i++) {
		board[i] = new int[26];
	}
	for (int i = 0; i < 200001; i++) {
		for (int j = 0; j < 26; j++) {
			board[i][j] = 0;
		}
	}
	string temp;
	while (temp != "-") {
		cin >> temp;
		if (temp != "-") {
			for (int j = 0; j < temp.length(); j++) {
				arr[wordcnt][temp[j] - 65] += 1; // 단어개수를 더해준다
			}
			wordcnt += 1;
		}
	};
	int cnt = 0;
	int cancnt = 0;
	int maxi = 0;
	int mini = 10;
	while (temp != "#") {
		cin >> temp;
		if (temp != "#") {
			for (int j = 0; j < 9; j++) {
				board[cnt][temp[j] - 65] += 1; // 단어개수를 더해준다
				gameboard[j] = temp[j];
			}

			// 글자에대해서
			int score[9] = { 0 };
			for (int k = 0; k < 9; k++) {
				// 몇가지 단어나 성공이 가능할지
				cancnt = 0;	
				for (int word = 0; word < wordcnt; word++) {
					int plag = 0;
					for (int q = 0; q < 26; q++) {
						if (board[cnt][q] < arr[word][q]) {
							plag = 1;
							break;
						}
					}
					if (plag == 0) {
						if (arr[word][gameboard[k] - 65] != 0) {
							cancnt += 1;
						}
					}
				}
				score[k] = cancnt;
			}
			int max = 0;
			int min = 500000;
			for (int x = 0; x <9; x++) {
				if (score[x] > max) {
					max = score[x];
				}
				if (score[x] < min) {
					min = score[x];
				}
			}
			vector<char>v_mini;
			vector<char>v_maxi;
			int min_count = 0;
			int max_count = 0;
			for (int v = 0; v < 9; v++) {
				if (score[v] == min && find(v_mini.begin(),v_mini.end(),gameboard[v]) == v_mini.end()){
					v_mini.push_back(gameboard[v]);
					min_count += 1;
				}
			}
			for (int v = 0; v < 9; v++) {
				if (score[v] == max && find(v_maxi.begin(), v_maxi.end(), gameboard[v]) == v_maxi.end()) {
					v_maxi.push_back(gameboard[v]);
					max_count += 1;
				}
			}
			sort(v_mini.begin(), v_mini.end());
			sort(v_maxi.begin(), v_maxi.end());
			for (int a = 0; a < min_count; a++) {
				cout << v_mini[a];
			}
			cout <<  " " << min << " ";
			for (int a = 0; a < max_count; a++) {
				cout << v_maxi[a];
			}
			cout << " " << max << endl;

			cnt += 1;
		}
	}
	return 0;
}

알파벳 단어를 처리하는 문제를 봤을 때, 단어의 개수를 저장해두면 편하게 풀리던 기억이 났다.

따라서 입력받은 단어들의 개수를 모두 저장해두고,
보드판의 단어의 수와 비교한다.

풀이는 두 가지 조건을 만족해야 한다.

1. 만약 보드판 단어의 빈도가 더 작다면 그 단어는 만들수 없는 단어이다.

2. 보드판의 가운데 글자는 무조건 포함해야 하므로 단어에 가운데 글자가 존재하지 않으면 만들수 없는 단어이다.

이 두가지 제약조건 중 처음조건은 쉽게 구현했으나,
두번째 조건을 만드는데 너무 오랜 시간이 걸렸다.

이유는 너무 황당하게도 단어 9개를 포함하는 배열을 만드는게 두려웠기 때문..

1번 조건을 위해서는 입력단어의 수만 중요하다. 그것을 위해 생성된 단어를 세는 배열을 2번에도 적용하려고 하니 실제 단어가 뭔지를 알 수 없어서 문제가 생겼다.

직접 단어를 저장하는 gameboard[9]배열을 만들고 계산만 한번 더 해주면 쉽게 해결 할 수 있는 문제였는데 오래걸려서 아쉽다.

배운점--------

1. stl의 sort 사용법
2. 중복되는 일을 어떻게 처리하는가?(find 함수를 통해 vector에 존재하지 않는것만 삽입)
3. 단어의 count를 세는 방법의 복습

느낀점--------

1. 시간초과를 생각하는것도 물론 중요하지만 , 상수계산에서 시간초과가 날일이 없으니 간단하게 해결할 수 있다면 자료구조를 몇개 더 만들더라도 그쪽으로 돌아가자. 멋잇게 해결할 단계는 아직 아닌것 같다.

2. 처음에는 단어의 count의 min을 무슨정신인지 10으로 잡아놓았는데 (게임판이 9라 그렇게한게 아닌가 싶다)
   min은 20만 까지 가능하다. 그래서 수정을 해야했다. 이런 제약 조건들도 잘 확인해서 설정하자.