[Lv.1] 크기가 작은 부분 문자열 [프로그래머스_코딩테스트] [문자열, 슬라이딩 윈도우] [30분]

🔍 문제 요약

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

프로그래머스

숫자로 이루어진 문자열 t와 p가 주어질 때 p와 길이가 같은 부분문자열 중에서 t보다 p가 값이 작거나 같은 횟수를 구하는 문제

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

맨 처음 문제를 보고 가볍게 substring해서 int.Parse 해서 비교하면 끝 아닌가? 라고 생각해서 바로 제출했으나 런타임 오류.. 문제를 좀 더 자세히 읽어 보니 제한사항으로 문자열 t의 길이가 10,000이라고 적혀있었다. 그래서 자릿수가 그렇게 길어지게 되면 당연히 안되는 게 맞지.. 결국 생각해낸 방법은 문자열 substring을 한 것을 좌측에서부터 숫자 하나하나씩 때어내어 비교를 하는 형태로 계산. 이거를 하면서 시간을 좀 잡아 먹어 35분 정도 걸린 듯 하다. 문제는 그래도 모든 테스트 케이스 통과한 코드.

using System;
using System.Diagnostics;

public class Solution
{
    /// <summary>
    /// 크기가 작은 부분 문자열
    /// https://school.programmers.co.kr/learn/courses/30/lessons/147355
    /// </summary>
    public int solution(string t, string p)
    {
        // p의 길이
        int pLen = p.Length;
        int count = 0;

        for (int i = 0; i <= t.Length - pLen; i++)
        {
            bool isMatched = true;
            var slice = t.Substring(i, pLen);

            for (int j = 0; j < pLen; j++)
            {
                var sliceChar = slice[j];
                var pChar = p[j];

                if (sliceChar < pChar)
                {
                    isMatched = true;
                    break;
                }
                else if (sliceChar > pChar)
                {
                    isMatched = false;
                    break;
                }
            }

            if (isMatched)
            {
                count++;
            }
        }
        
        return count;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var tArr = new[] { "3141592", "500220839878", "10203" };
        var pArr = new[] { "271", "7", "15" };

        for (int i = 0; i < tArr.Length; i++)
        {
            Console.WriteLine(sl.solution(tArr[i], pArr[i]));
        }
    }
}

✅ 풀이 코드

피드백을 받았을 때 처음 알려준 방향은 uLong.parse를 알려줬으나 이건 문제의 제한사항이 p의 길이가 10,000자리 숫자가 될 수 있으므로 불가능. 추가로 C# 8부터 가능한 span으로 substring을 최적화 할 수 있다고 하지만 프로그래머스에서는 7.3까지만 지원이 되므로 불가능. 그 후에 알려준 방법이 필자처럼 단어 하나하나 비교도 가능하지만 편하게 CompareTo를 쓰는 방법이었다. 이건 깜빡했었던 것.. 종종 비교할 때 쓰곤 했는데 문자열을 숫자처럼 비교할 때 CompareTo를 써도 가능하다. 추가로 BigInteger는 최대 자리수가 무제한이라고 하는데 이걸 써봤어도 간단히 되었지 않을까 싶기도 하다.

🔄 정리

단어를 하나 하나 비교하는 방법이나, CompareTo, BigInteger로 숫자 비교를 하는 방법이나 잘 생각해서 시간 안에 풀 수 있게 선택을 내려야 할 듯 하다. 특히 제한사항을 실수로 제대로 안 보고 넘어가는 경우가 있는데 그런 경우 필자처럼 런타임 오류를 뱉으며 시간을 더 잡아 먹는 케이스가 있으므로 문제를 주의깊게 살펴보아야 할 듯 하다.