20240221_대충 만든 자판(프로그래머스)

오늘의 TIL은 대충 만든 자판이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/160586

프로그래머스

 

문제 설명

 

핸드폰의 자판처럼 하나의 키에 여러 개의 문자가 할당된 자판이 있고,

해당 자판은 키를 누를 때마다 할당된 순서대로 문자가 바뀐다.

 

예를 들어서 1번 키에 "A", "B", "C", "D"가 할당되어 있으면

1번 키를 한 번 누르면 "A"가, 두 번 누르면 "B"가, 세 번 누르면 "C"가 되는 식이다.

 

이 규칙을 이용해서 만든 대충 만든 자판이 있고, 이 자판은 키의 개수가 1개부터 100개까지 있을 수 있으며,

특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있다. 또, 같은 문자가 자판 전체에 여러번 할당된 경우도 있고,

키 하나에 같은 문자가 여러 번 할당된 경우도 있다.

어떤 경우에는 특정 문자가 할당되지 않은 경우도 있기 때문에 문자열을 작성할 수 없는 경우도 있다.

 

이 자판을 이용하여 특정 문자열을 작성할 때, 키를 최소로 누르는 방법으로 문자열을 작성하려고 한다.

 

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return하시오.

 

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장한다.

 

 

제한 조건

1 <= keymap의 길이 <= 100

1 <= keymap의 원소의 길이 <= 100

keymap[i]는 i + 1번 눌렀을 때, 순서대로 바뀌는 문자

keymap의 원소의 길이는 서로 다를 수 있다.

keymap의 원소는 알파벳 대문자로만 이루어져있다.

 

1 <= targets의 길이 <= 100

1 <= targets의 원소의 길이 <= 100

targets의 원소는 알파벳 대문자로만 이루어져있다.

 

 

해결 방안

1. string의 매서드인 IndexOf를 사용

IndexOf를 사용해서 해당 문자가 몇 번째 인덱스에 있는지를 확인할 수 있다.

 

2. dictionary 사용

keymap에 있는 문자들을 가지고 targets의 문자들을 만드는 것이 목표이며,

여기서 사용하는 문자는 알파벳 대문자만 있으므로

dictionary를 이용해서 알파벳 A부터 Z까지 만든 후에

keymap을 돌면서 최소의 인덱스(최소로 눌러서 만들 수 있는 횟수)를 찾는다.

 

 

통과한 답안

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] keymap, string[] targets) {
        int[] answer = new int[] {};
        List<int> answerList = new List<int>();
        Dictionary<char, int> charMap = new Dictionary<char, int>();

        for (char c = 'A'; c <= 'Z'; c++)
        {
            int defalut = int.MaxValue;

            foreach (var keyString in keymap)
            {
                int index = keyString.IndexOf(c);
                if (index != -1 && index < defalut)
                {
                    defalut = index;
                }
            }
            if (defalut != int.MaxValue)
            {
                charMap.Add(c, defalut + 1);
            }
        }

        for (int i = 0; i < targets.Length; i++)
        {
            int sum = 0;
            for (int j = 0; j < targets[i].Length; j++)
            {
                if (charMap.ContainsKey(targets[i][j]))
                {
                    sum += charMap[targets[i][j]];
                }
                else
                {
                    sum = -1;
                    break;
                }
            }
            answerList.Add(sum);
        }

        answer = answerList.ToArray();
        return answer;
    }
}

 

 

초기화 및 dictionary 만들기

List<int> answerList = new List<int>();
Dictionary<char, int> charMap = new Dictionary<char, int>();

for (char c = 'A'; c <= 'Z'; c++)
{
    int defalut = int.MaxValue;

    foreach (var keyString in keymap)
    {
        int index = keyString.IndexOf(c);
        if (index != -1 && index < defalut)
        {
            defalut = index;
        }
    }
    if (defalut != int.MaxValue)
    {
        charMap.Add(c, defalut + 1);
    }
}

 

answer를 순서대로 담을 answerList와 알파벳 A부터 Z까지의 최소 누르는 횟수를 담을 dictionary를 만든다.

 

dictionary를 만드는 방법은 문자를 A부터 Z까지 순회하면서

 

기본 값을 int의 최대값(여기서는 100이 최대이므로 100을 입력해도 되지만, 숫자 대신 내장된 값을 이용했다)로 정하고

 

keymap에 있는 string들을 순회하면서 해당 문자의 index를 찾고, 만약 index가 기존의 값보다 작다면 이를 대체한다.

 

그 후에 찾은 index가 defalut값(int 최대값)이 아니라면 해당 값을 dictionary에 저장한다.

(여기에서 누르는 횟수는 인덱스가 아니므로 +1을 해준다)

 

 

dictionary를 이용해서 targets 문자들 만들기

for (int i = 0; i < targets.Length; i++)
{
    int sum = 0;
    for (int j = 0; j < targets[i].Length; j++)
    {
        if (charMap.ContainsKey(targets[i][j]))
        {
            sum += charMap[targets[i][j]];
        }
        else
        {
            sum = -1;
            break;
        }
    }
    answerList.Add(sum);
}

answer = answerList.ToArray();

 

dictionary를 생성한 후에 targets의 문자를 만들 수 있는지 확인하는데,

 

targets에는 문자열이 여러개 존재하므로, for문을 2개 사용해서

 

targets안에 있는 문자열 안에 있는 문자들을 dictionary에서 만들 수 있는지 확인한다.

 

확인하여 만들 수 있으면 그 값을 모두 더해주며, 확인할 수 없다면 -1를 반환한다.

 

이후에 이를 답을 담기위해 만든 answerList에 담아주고, 마지막으로 answerList를 배열인 answer로 변환해준다.

 

 

 

오늘은 난이도가 낮은 부분에 있지만, 어떤 방식으로 접근하면 좋을지 몰라서 풀지 못했었던 문제에 도전했는데,

 

이전에는 dictionary의 개념도 부족하고, 이를 맵핑하는 작업도 막막해서 시도하지 못했었지만,

 

과정이 끝나가는 지금의 시점에서는 문제를 보면서 어떤 방식으로 풀이하면 좋을지,

 

맵핑을 하는 방식은 어떤 방식이 좋을지 고민하며 풀이하여서 이를 기록하기 위해 정리했다.

 

(처음에는 주체를 targets로 두고 targets에 있는 문자들을 모두 dictionary로 만들거나,

 keymap에 있는 문자들만 dictionary로 만드는 등의 방법을 시도했지만,

 결론적으로는 A부터 Z까지를 모두 dictionary로 만드는 방법이 훨씬 유용할 것이라 생각하여

 이 방법을 선택하게 되었다)