[Lv.1] 대충 만든 자판 [프로그래머스_코딩테스트] [문자열 매핑] [25분]

🔍 문제 요약

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

프로그래머스

문제가 길게 적혀 있지만 실제로는 targets 배열에 나와있는 문장들을 순회하면서 해당 문장의 알파벳들을 keyMap에서 순서대로 찾아서 가장 빠른 순서대로 더한 값을 반환하는 문제이다.

 

🧠 나의 접근 방식과 시행착오

실제 푼 시간은 약 20분 정도 걸렸다. 문제가 복잡하지 않았음. 아래의 코드처럼 문제를 해결했다. 코드는 작성하다 보니 for가 3중첩이나 되고 있어서 시간 초과가 걸릴 것으로 생각했으나 제한사항으로 길이가 그렇게 길지 않아서인지 오래걸리진 않았던듯. (사실 좀 더 빠르게 하기 위해서는 Dictionary 해시 맵을 써서 이미 찾아서 나온 알파벳의 경우 중복으로 찾지 않게 해도 될 듯 하다) 이 문제도 피드백 받을 부분이 있을 지 체크해서 문제 풀이 부분에 적어보려고 한다.

using System;

public class Solution
{
    /// <summary>
    /// 대충 만든 자판
    /// https://school.programmers.co.kr/learn/courses/30/lessons/160586
    /// </summary>
    public int[] solution(string[] keymap, string[] targets)
    {
        int[] answer = new int[targets.Length];
        
        // targets를 순회하면서 각 문장을 다시 단어 하나씩 순회
        // 단어를 keyMap에서 인덱스별로 제일 빨리 마주치는 것을 체크 해서 저장.
        for (int k = 0; k < targets.Length; k++)
        {
            var target = targets[k];
            
            // 타겟 문장의 단어 하나씩 
            for (int i = 0; i < target.Length; i++)
            {
                char c = target[i];
                int minFindIdx = int.MaxValue;
                
                // c가 매칭되는 가장 가까운 keyMap 찾기
                for (int j = 0; j < keymap.Length; j++)
                {
                    var findKeyStr = keymap[j];
                    int findKeyIdx = findKeyStr.IndexOf(c, StringComparison.OrdinalIgnoreCase);

                    if (findKeyIdx >= 0 && minFindIdx > findKeyIdx)
                    {
                        minFindIdx = findKeyIdx;
                    }
                }

                // 발견
                if (minFindIdx < int.MaxValue)
                {
                    answer[k] += (minFindIdx + 1);
                }
                // 못찾은 경우 keyMap 내역에 없는 경우 -1 집어 넣고 건너 뜀
                else
                {
                    answer[k] = -1;
                    break;
                }
            }
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var keyMap1 = new string[] { "ABACD", "BCEFD" };
        var targets1 = new string[] { "ABCD","AABB" };
        var keyMap2 = new string[] { "AA" };
        var targets2 = new string[] { "B" };
        var keyMap3 = new string[] { "AGZ", "BSSS" };
        var targets3 = new string[] { "ASA","BGZ" };
        
        var res1 = sl.solution(keyMap1, targets1);
        var res2 = sl.solution(keyMap2, targets2);
        var res3 = sl.solution(keyMap3, targets3);

        foreach (var res in res1)
        {
            Console.Write(res + ", ");
        }
        Console.WriteLine();
        
        foreach (var res in res2)
        {
            Console.Write(res + ", ");
        }
        Console.WriteLine();
        
        foreach (var res in res3)
        {
            Console.Write(res + ", ");
        }
        Console.WriteLine();
    }
}

 

✅ 풀이 코드

gpt에게 피드백을 부탁해서 나온 코드는 아래와 같다. 사실 그냥 IndexOf 전에 dictionary 캐시를 체크해서 찾아오는 것까지만 생각했는데, 아래 풀이의 경우 모든 keymap을 전체 순회를 한 다음 각 알파벳을 찾는데 걸리는 수치를 미리 저장해두는 방식을 썼다. (이렇게 하면 확실히 3중첩되는 for문도 정리가 가능해서 가독성도 올라가는 것을 확인) 문제 자체는 어렵진 않았던 부분이라 풀이 코드만 적어둬 본다.

public int[] solution(string[] keymap, string[] targets)
{
    var answer = new int[targets.Length];
    var minKeyMap = new Dictionary<char, int>();

    // 1. 모든 알파벳에 대해 최소 키 입력 횟수 사전화
    for (int i = 0; i < keymap.Length; i++)
    {
        var keys = keymap[i];
        for (int j = 0; j < keys.Length; j++)
        {
            char c = keys[j];
            int pressCount = j + 1;

            if (!minKeyMap.ContainsKey(c) || minKeyMap[c] > pressCount)
            {
                minKeyMap[c] = pressCount;
            }
        }
    }

    // 2. targets 처리
    for (int i = 0; i < targets.Length; i++)
    {
        int total = 0;
        bool valid = true;

        foreach (var c in targets[i])
        {
            if (!minKeyMap.ContainsKey(c))
            {
                total = -1;
                valid = false;
                break;
            }

            total += minKeyMap[c];
        }

        answer[i] = total;
    }

    return answer;
}

 

🔄 정리

탐색 등에서 확실히 Dictionary 해시맵을 사용해서 반복횟수를 줄이거나 해서 빠르게 원하는 것을 얻을 수 있다는 점에서 정말 유용하게 활용가능한 부분인 듯 하다