[백준 1148번] 단어 만들기 (C++)

문제링크 : https://www.acmicpc.net/problem/1148

1148번: 단어 만들기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int word[200000][26]; //단어
int board[26]; //보드
int cnt[26]; //정답 카운트

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    string s;
    int n = 0; //단어 갯수
    while(1)
    {
        cin >> s;
        if(s == "-") break;
        for(int i=0; i<s.length(); i++)
        {
            word[n][s[i]-'A']++; //각 단어의 알파벳 갯수 저장
        }
        n++; //단어 갯수 증가
    }

    while(1)
    {
        memset(cnt, 0, sizeof(cnt));
        memset(board, 0, sizeof(board));
        cin >> s;
        if(s == "#") break;

        for(int i = 0; i<s.length(); i++)
        {
            board[s[i]-'A']++; //보드 알파벳 갯수 저장
        }

        for(int i=0; i<n; i++)
        {
            bool flag = true;
            for(int j=0; j<26; j++)
            {
                if(board[j] < word[i][j]) //해당 보드로 단어 표현불가
                {
                    flag = false; 
                    break;
                }
            }
            if(!flag) continue;
            for(int j=0; j<26; j++)
            {
                if(word[i][j] !=0 )
                {
                    cnt[j]++; //유효 단어 카운트
                }
            } 
        }

        int minV = MAX;
        int maxV = 0;

        for(int i=0; i<26; i++)
        {
            if(minV > cnt[i] && board[i]!=0) minV = cnt[i]; //정답 갯수 최소
            if(maxV < cnt[i]) maxV = cnt[i]; //정답 갯수 최대
        }
        
        string result1 = "", result2 = "";
        for(int i = 0; i<26; i++)
        {
            if(minV == cnt[i] && board[i] != 0)
            {
                result1 += ('A' + i); //최소일때 문자
            }
            if(maxV == cnt[i] && board[i] != 0)
            {
                result2 += ('A' + i); //최대일때 문자
            }
        }

        cout << result1 << " " << minV << " " << result2 << " " << maxV << "\n";
    }

    return 0;
}

처음에 단어를 입력받고, 각 단어의 경우마다 단어의 각 알파벳 갯수를 저장한다.

그 다음 마찬가지로 보드도 보드의 각 알파벳 갯수를 저장한다.

 

만약 보드의 해당 알파벳 갯수가 단어의 알파벳 갯수보다 적다면 해당 단어는 구현이 불가능한 것이다.

이렇게 구현 불가능한 단어를 거르고 난뒤에 구현이 가능한 단어가 존재한다면 해당 단어의 알파벳 마다 (유효한 알파벳) 카운트를 해준다.

이때 중복되는 문자는 필요가 없으므로 한번만 카운트되도록 해줘야한다.

 

그 다음에 각 정답 갯수가 최소가 되는 경우와, 최대가 되는 경우를 각각 저장해줘야 한다.

이때 단순히 알파벳 총 갯수에 대해 완전탐색을 하는 것이라서 보드에 값이 없는 경우는 따로 걸러줘야 한다. (board != 0)

그렇지 않다면 보드에 없어서 원래는 안되는데 해당 조건에는 아무튼 맞기 때문에 출력되는 경우가 발생한다.

이를 주의하여 최소값과 최대값을 구한 후에, 해당 값이 위치한 문자를 찾아서 출력해주면 된다.