[EPPER/14회 5번]단어 게임(상-2)

 

<문제>

 

 

<입력예시> 

단어와  단어의 첫글자들은 배열(c)/vector(c++)로 주어짐 

 

 

만족해야하는 조건

1. 미리 주어진 (입력받은) 단어 목록일 것 

→ 전달받은 단어 배열 내로 정답을 한정함 

2. 첫글자가 동일해야할 것 

→ 리스트를 for문으로 탐색하면서 첫글자가 동일할 떄 까지 비교 

3. (2번 조건이 중복될 경우) 최소 횟수로 언급한 것 이어야 할 것

4. (3번 조건까지 중복될 경우) 알파벳 순서로 답할 것 

→ 언급횟수를 기준으로 정렬 + 언급횟수가 같으면 알파벳순으로 정렬

 

정렬을 해주면 for문으로 첫글자만 비교해서 첫번째로 같은 것을 정답으로 생각해 줄 수 있음 

 

 

 

 

<코드>

// 실제 시험에서는 Solution 클래스의 solution 함수를 사용합니다. 이를 감안하여 풀이해주세요.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

/*

답변을 선택할 때 고려해야할 사항을 순서대로 말하면,

1. 주어진 글자로 시작하는 단어 고르기
2. (1)이 여러개라면, 가장 적게 말한 단어 고르기 -> 이 조건을 위해 그냥 단어를 언급횟수 순서로 정렬하면 굳이 고려할 필요가 없음!
3. (2)이 여러개라면, 알파벳 순으로 고르기 -> 이 조건을 위해 그냥 단어를 알파벳 순서로 정렬하면 굳이 고려할 필요가 없음!

단어와 함께 단어가 언급된 횟수를 저장해야함 => vector pair로 단어,언급횟수를 묶음 

이렇게되면 2,3번은 그냥 정렬해놓고 1번만 고려하면됨 

-> vector pair를 sort함수를 이용하여 
1. 언급횟수순서대로 정렬 
2. 언급횟수가 같은경우 알파벳순으로 정렬 

-> 이 상태로 정렬한 후 
첫글자가 주어질 때마다 pair에서 순서대로 첫글자가 맞으면 출력한 후 언급횟수를 ++해주고 재정렬하면됨





*/

vector<pair<string,int>> wordTable;

//단어목록과 언급횟수를 pair로 만듬 
bool compare(pair<string,int> a, pair<string,int> b){
	
	//적게 말한단어가 앞으로 -> 오름차순 
	if(a.second == b.second){ //언급 횟수가 같다면 
		return a.first<b.first; //알파벳 순서대로(오름차순)
	}else{//언급횟수 다르면 
		return a.second<b.second; //언급횟수에서 오름차순으로 정렬 
	}
	
}

void solution(vector<string> word, vector<char> start, int K, int N){
	
	//pair로  (word,0)으로 초기화
	for(int i=0;i<K;i++){
		wordTable.push_back({word[i],0});
	}
	
	//언급횟수를 우선으로 -> 같으면 알파벳 순서대로 정렬 (최초수행)
	sort(wordTable.begin(),wordTable.end(),compare);
	
	
	//입력받은 시작 문자 숫자만큼 반복 
	for(int k=0;k<N;k++){
		
		//입력받은 단어목록 만큼 반복 
		for(int j=0;j<K;j++){
			
			//첫자를 비교하기 위해 첫자를 저장함 
			char S = wordTable[j].first.at(0);
			
			//첫자와 시작문자가 같은 경우 
			if(start[k]==S){
				
				//해당 단어가 답이므로 이를 출력 
				cout<<wordTable[j].first<<endl;
				
				//언급했으므로 언급횟수를 1회증가시킴 
				wordTable[j].second++;
				//횟수가 증가되었으므로 재정렬함 
				sort(wordTable.begin(),wordTable.end(),compare);
				
				//이미 단어목록에서 답을 했으므로 다음 단어를 탐색할 필요가 없으므로 종료 
				break;
			}
		}
		
		
	}
	
	
	
}


int main() {
	
	int K,N;
	vector<string> word;
	vector<char> start;
	string wordType;
	char startType;
	
	cin>>K>>N;
	
	for(int i=0;i<K;i++){
		cin>>wordType;
		word.push_back(wordType);
	}
	for(int i=0;i<N;i++){
		cin>>startType;
		start.push_back(startType);
	}
	
	solution(word,start,K,N);
	
	return 0;
}