알파벳 카드로 단어 만들기

문제

대문자 알파벳 A~Z중 임의로 구성된 8개의 카드 3세트가 주어진다.
주어지는 카드 세트를 활용하여 입력된 Words중 만들 수 있는 Word를 반환하라.

만드는 규칙은 다음과 같다.

조건 1. 모든 카드는 한번만 쓸 수 있다.
조건 2. A~Z까지 모든 카드가 존재하지 않을 수도 있다.
조건 3. 동일한 카드가 존재할 수 있으며, 동일한 카드는 동일한 라인에 존재한다.
조건 4. 3세트(줄) 중 어느 하나라도 사용되지 않으면 안된다.
아무것도 만들 수 있는 단어가 없으면 {“-1”}을 반환한다.
문제의 예시는 다음과 같다.

알파벳 카드 { "ABCDEFGH", "IJKLMNOP", "QRSTUVWX" } 가 다음과 같이 주어지고

만들 단어가 { "AIMR", "CBOX", "ANV", "AGIP", "HIXX" } 로 주어졌을 때

만들 수 있는 단어는 AIMR과 CBOX, ANV이다.

AGIP는 3번째 카드 세트인 QRS..X가 사용되지 않아 조건 4에 위배된다.

HIXX는 X의 카드가 총 1장 있어 HIX후 다음 X를 만들기 위한 카드가 존재하지 않는다.

따라서 출력 결과는 { "AIMR", "CBOX", "ANV" } 이다.

풀이

주석 참고

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

using namespace std;

vector<string> solution(vector<string> card, vector<string> word)
{
  vector<string> answer = {};

  string::iterator      it;
  vector<int>::iterator vit;
  int                   i, j, k;
  bool                  bFind;

  // 1. 총 단어 수
  for (i = 0, bFind = true; i < word.size(); i++, bFind = true)
  {
    // 2. 단어별 검색
    vector<string> cpCard(card);
    vector<int>    isVisit = { 0, 1, 2 };  // 1~3세트 방문 체크

    for (j = 0; j < word[i].size(); j++)
    {
      // 단어마다 카드를 새로 생성
      // 3. 카드별 탐색
      for (k = 0; k < 3; k++)
      {
        it = find(cpCard[k].begin(), cpCard[k].end(), word[i].at(j));
        if (it != cpCard[k].end())
        {
          // 사용한 카드 삭제
          cpCard[k].erase(it);

          // 방문한 세트 번호는 삭제
          vit = find(isVisit.begin(), isVisit.end(), k);

          if (vit != isVisit.end())
            isVisit.erase(vit);
          break;
        }
      }

      // 알파벳이 없을 때
      if (k == 3)
      {
        bFind = false;
        break;
      }
    }

    // 1~3세트 카드 모두 방문하였는지 체크
    if (isVisit.size() != 0)
      bFind = false;

    if (bFind)
      answer.push_back(word[i]);
  }

  if (answer.size() == 0)
    answer.push_back("-1");

  return answer;
}

int main()
{
  vector<string> cards = {
    "ABACDEFG",
    "NOPQRSTU",
    "HIJKLKMM"
  };
  // vector<string> words = { "GPQM", "GPMZ", "EFU", "MMNA" };
  vector<string> words = { "AACDPQRJMM", "ANOEFTMHILMZ" };

  vector<string> answer = solution(cards, words);
  for (int i = 0; i < answer.size(); i++)
  {
    cout << answer[i] << " ";
  }
  cout << endl;
}

출처

프로그래머스