[CodinGame] SCRABBLE(해시맵으로 단어 만들기)

문제 간략 설명: 이 문제는 스크래블이라는 유명한 단어 조합 게임에서 가져왔습니다.

스크래블은 주어진 알파벳을 조합하여 사전에 있는 단어를 만드는 게임입니다.

[사진]

[Rules_규칙]

목표: Scrabble 게임에서 각 플레이어는 7개의 글자를 뽑고, 이 중에서 가능한 가장 높은 점수를 얻을 수 있는 단어를 만들어야 합니다. 단어의 길이는 1에서 7 사이일 수 있습니다.

 

규칙:

1. 각 글자는 난이도에 따라 점수가 주어집니다. 점수는 아래와 같습니다.
   • e, a, i, o, n, r, t, l, s, u: 1점
   • d, g: 2점
   • b, c, m, p: 3점
   • f, h, v, w, y: 4점
   • k: 5점
   • j, x: 8점
   • q, z: 10점
2. 주어진 7개의 글자를 이용하여 사전에 있는 단어 중 가장 높은 점수를 얻을 수 있는 단어를 찾아야 합니다. 
3. 입력받은 알파벳은 단 한 번만 사용할 수 있습니다. 사전에 있는 단어가 같은 알파벳을 여러 번 사용한 경우 주어진 알파벳에도 같은 수의 알파벳이 있어야 합니다.
   • 예를 들어 "apple"이라는 사전 안의 단어가 있고 알파벳 꾸러미는 "aehilop" 라면 p가 "apple"은 2개 "aehilop"은 1개 이기 때문에 안됩니다.
4. 입력으로는 사전에 있는 단어의 수와 각 단어, 그리고 주어진 7개의 글자가 주어집니다.
5. 출력으로는 주어진 7개의 글자를 이용하여 얻을 수 있는 가장 높은 점수를 가진 단어를 출력해야 합니다. 출력하는 단어는 사전에 반드시 포함되어 있어야 합니다.
6. 만약 같은 점수를 얻을 수 있는 단어가 여러 개 있다면, 사전 상에서 가장 먼저 등장하는 단어를 선택해야 합니다.

 

[문제]

 

https://www.codingame.com/training/medium/scrabble

Practice Loops and Conditions with the exercise "Scrabble"

 

[난이도]

[학습 개념]

연관 배열, 해쉬 테이블

[풀이]

1. 규칙을 보면 점수가 같은 경우 사전에 먼저 나온 단어가 정답이므로 사전의 단어 순서가 매우 중요해서, 입력받은 순서대로 배열에 넣어주었습니다.
2. 최고 점수와 그 단어를 저장할 변수를 선언했습니다.
3. 반복문을 이용해 사전의 모든 단어를 확인하고, 각 단어가 주어진 알파벳 꾸러미로 조합 가능한지 확인하고, 그 단어의 점수를 확인 후 기존 단어보다 높으면 그 단어가 최고 점수의 단어가 되게 해야겠다고 생각하였습니다.
4. 반복문을 만들고 조합 가능한지 확인하는 bool 값을 반환하는 함수를 만들고, 단어의 점수를 확인하는 int 값을 반환하는 함수를 틀만 만들었습니다.
5. 반복문이 종료되면 가장 큰 점수인 단어를 뽑을 수 있게 반복문 안을 만들고 반복문이 끝나면 최고 점수인 단어를 출력하게끔 하였습니다.
6. 단어의 점수를 반환하는 함수를 만드는게 더 쉬울 거 같아 이 함수부터 만들었습니다.
7. get_word_score 함수에 매개변수로 단어를 받고 그 단어에 맞는 점수를 더해줘 반환해 주면 되겠다 생각했습니다.
8. 규칙처럼 데이터가 쌍으로 이루어진 데이터 구조는 해쉬맵으로 만들면 검색도 매우 빠르고 가독성도 좋아서 딕셔너리 클래스로 letterPoints 객체를 만들고 규칙대로 단어와 점수를 초기화했습니다.
9. 이제 각 단어가 주어진 알파벳 꾸러미로 조합 가능한지 확인하는 is_word_feasible 함수 안을 채워야 했습니다.
10. 주어진 알파벳 꾸러미로 사전의 단어를 만들 수 있는 방법을 고민했습니다.
11. 일단 단어에 쓰인 모든 글자가 알파벳 꾸러미 안에 있는지 하나씩 확인해보기 위해 LINQ를 사용해야겠구나 생각했습니다.
12. 그리고 규칙에서 단어에 쓰인 글자의 개수만큼 알파벳 꾸러미에 있는지도 확인해야 했습니다.
13. word.All을 써서 문자열의 모든 문자에 대해 참인지 확인하고 Contains를 써서 c 문자가 문자열에 있는지 확인 후 word.Count를 써서 word 문자열에서 c 문자가 몇 번 써졌는지 확인하고 알파벳 꾸러미에서 쓰인 c 문자 개수보다 적으면 참을 반환하게 했습니다.

 

 

[소스 코드]

 

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

class Solution
{
    static Dictionary<char, int> letterPoints = new Dictionary<char, int>()
{
    {'e', 1}, {'a', 1}, {'i', 1}, {'o', 1}, {'n', 1}, {'r', 1}, {'t', 1}, {'l', 1}, {'s', 1}, {'u', 1},
    {'d', 2}, {'g', 2},
    {'b', 3}, {'c', 3}, {'m', 3}, {'p', 3},
    {'f', 4}, {'h', 4}, {'v', 4}, {'w', 4}, {'y', 4},
    {'k', 5},
    {'j', 8}, {'x', 8},
    {'q', 10}, {'z', 10}
};

    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        string[] dictionary = new string[N];
        for (int i = 0; i < N; i++)
        {
            dictionary[i] = Console.ReadLine();

        }
        string letters = Console.ReadLine();

        int max_score = 0; // 최고 점수
        string max_score_world = ""; // 최고 점수에 해당하는 단어

        foreach (var word in dictionary)
        {
            if (is_word_feasible(word, letters))
            {
                int score = get_word_score(word);
                if (score > max_score)
                {
                    max_score = score;
                    max_score_world = word;
                }
            }
        }

        Console.WriteLine(max_score_world);
    }

    //반복문을 이용하여 사전의 모든 단어를 확인하고, 각 단어가 주어진 알파벳 꾸러미로 조합 가능한지 확인하는 함수
    static bool is_word_feasible(string word, string letters)
    {
        // 단어가 조합 가능한지 확인하기 위해서는 다음 2가지 조건이 필요하다.
        // 1. 단어에 쓰인 모든 글자가 알파벳 꾸러미에 있는지 확인합니다.
        // 2. 단어에 쓰인 글자의 개수만큼 알파벳 꾸러미에 있는지 확인합니다.

        return (word.All(c => letters.Contains(c) && word.Count(x => x == c) <= letters.Count(y => y == c)));
    }

    //주어진 알파벳으로 글자로 조합 가능한 경우, 단어의 점수를 계산하는 함수
    static int get_word_score(string word)
    {
        int score = 0;
        foreach (char word_char in word)
        {
            score += letterPoints[word_char];
        }
        return score;
    }
}

 

[아쉬웠던 점]

규칙을 이해하고 코드를 구성하는 부분은 쉬었지만 사전의 모든 단어를 확인하고, 각 단어가 주어진 알파벳 꾸러미로 조합 가능한지 확인하는 방법을 무슨 방법을 써야 만들어야 하는지 잘 몰랐었습니다.

그리고 LINQ 사용법에도 무지해 쿼리 구문과 메서드 구문에 대해서도 잘 몰랐어서 사용하는데 여러 시행착오가 많았습니다.

 

[새롭게 알게된 점]

1. LINQ가 c#에서 쿼리 구문과 메서드 구문이 있다는 걸 새롭게 알게 되었습니다. 의미가 같아 상관없지만 이걸 이때까지 모르고 사용했던 점은 조금 부끄럽습니다. (알아야 하는 게 계속 계속 있어요 （＞人＜；） )
2. LINQ 사용법을 쿼리 구문과 메서드 구문을 보면서 확실히 알게되었습니다. (전에 썼던 LINQ 블로그 글을 수정했습니다.)
3. 해쉬 맵 알고리즘에 대해 알게 되었고 사용하면서 이해가 깊어졌습니다..