[Lv.1] 둘만의 암호 [프로그래머스_코딩테스트] [문자열, 구현] [30분]

🔍 문제 요약

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

프로그래머스

문자열 s 와 index 라는 자연수, skip이라는 건너뛰어야 하는 char가 들어있는 string이 있을 때 s의 각 알파벳을 index만큼 뒤의 알파벳으로 교체할 때 skip에 있는 char를 건너뛴 결과를 반환

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

char 배열에 결과를 반환시킬 것을 미리 생성시켜두고 s의 각 알파벳을 체크해서 뒤로 보내면서 z보다 큰 경우 a로 돌려주었다. 그리고 skip에 있는 알파벳인 경우 다음 회차로 돌리면서 index까지 while을 돌림. 문제를 풀 때 컨디션의 난조인지 집중려이 흐트러졌는지 테스트 케이스가 자꾸 틀린 경우가 발생하여서 다른 방법으로 계속 바꾸었었다. 맨처음에는 한 줄 아네 z를 넘어간 경우 a로 바꾸는 것까지 작업을 했었다가 조금씩 어긋 나는 부분이 발견되어 그냥 명시적으로 if문을 써서 해결.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 둘만의 암호
    /// https://school.programmers.co.kr/learn/courses/30/lessons/155652
    /// </summary>
    public string solution(string s, string skip, int index)
    {
        char[] answer = new char[s.Length];
        
        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            int count = 1;

            while (count <= index)
            {
                c++;

                if (c > 'z')
                {
                    c = 'a';
                }

                if (!skip.Contains(c))
                {
                    count++;
                }
            }
            
            answer[i] = c;
        }
        
        return new string(answer);
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var s = "aukks";
        var skip = "wbqd";
        var index = 5;
        Console.WriteLine(sl.solution(s, skip, index));
    }
}

✅ 풀이 코드

피드백을 받을 때 보면 조종 나오는데 이번에도 skip에 포함 되어있는지 체크하는 것을 HashSet으로 해서 시간복잡도를 O(1)로 끝내는 방식으로 알려주었다. string.Contains는 명식으로 문자열을 다 도는 것이어서인지 O(n)이어서 효율이 좋지 못하다는 점. 추가로 z를 넘어간 경우 a로 돌아오는 것도 한 줄로 해결하는 법도 나와 있으니 해당 방향으로 풀면 될 것으로 보인다.

public string solution(string s, string skip, int index)
{
    var skipSet = new HashSet<char>(skip);
    char[] result = new char[s.Length];

    for (int i = 0; i < s.Length; i++)
    {
        char c = s[i];
        int count = 0;

        while (count < index)
        {
            c = (char)((c - 'a' + 1) % 26 + 'a');
            if (!skipSet.Contains(c))
            {
                count++;
            }
        }

        result[i] = c;
    }

    return new string(result);
}

🔄 정리

HashSet을 사용한 최적화, 알파벳처럼 순환되는 형태일 때의 구현에 대해서 숙지해두면 좀 더 빠르게 풀이가 가능할 것 같다.