[프로그래머스] - 크기가 작은 부분문자열(C#)

크기가 작은 부분문자열

안녕하세요 오늘은 "크기가 작은 부분문자열" 문제를 풀어보도록 하겠습니다. 어제 실수로 오늘 할 문제의 이름을 크기가 작은 문자열 이라고 했는데 정정하겠습니다.

 

문제 설명

숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.

예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

 

제한 사항

• 1 ≤ p의 길이 ≤ 18
• p의 길이 ≤ t의 길이 ≤ 10,000
• t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

 

입출력 예

t	p	result
"3141592"	"271"	2
"500220839878"	"7"	8
"10203"	"15"	3

 

입출력 예 설명

입출력 예 #1
본문과 같습니다.

입출력 예 #2
p의 길이가 1이므로 t의 부분문자열은 "5", "0", 0", "2", "2", "0", "8", "3", "9", "8", "7", "8"이며 이중 7보다 작거나 같은 숫자는 "5", "0", "0", "2", "2", "0", "3", "7" 이렇게 8개가 있습니다.

입출력 예 #3
p의 길이가 2이므로 t의 부분문자열은 "10", "02", "20", "03"이며, 이중 15보다 작거나 같은 숫자는 "10", "02", "03" 이렇게 3개입니다. "02"와 "03"은 각각 2, 3에 해당한다는 점에 주의하세요

 

시작 코드

using System;

public class Solution {
    public int solution(string t, string p) {
        int answer = 0;
        return answer;
    }
}

 

나의 풀이

using System;

public class Solution {
    public int solution(string t, string p) {
        int answer = 0;
        long num = 0;
        for(int i = 0; i < t.Length - p.Length + 1; i++)
        {
            num = long.Parse(t.Substring(i, p.Length));
            if(num <= long.Parse(p)) { answer++; }
        }
        return answer;
    }
}

 

코드 분석

string 타입의 t, p가 주어지며 코드가 시작됩니다. long타입으로 num을 선언하고 for문을 돌립니다. 실행범위는 t의 길이에서 p의 길이를 뺀값에 1을 더한 만큼 입니다. for문 안에서는 문자열 t에 Substring()을 사용하여 i부터 p의 길이만큼 자르고, long타입으로 변환시킨다음 num에 넣어줍니다. if문에서는 num이 long타입으로 변환시킨 p보다 작거나 같다면 answer를 올려줍니다. 최종적으로 answer값을 리턴합니다.

 

풀이 설명

문제에서 요구하는 것은 t에서 p와 길이가 같은 문자열 중에 p보다 수가 작거나 같은 수의 개수를 세는 것입니다.

t와 p는 문자열이지만, 숫자로 이루어져 있기 때문에 형 변환이 필수적으로 사용됩니다. 또 한가지 주의해야 할 점은 문자열을 잘라서 나타내는 것이기 때문에 숫자의 순서가 지켜져야 합니다. 그리고 이미 사용한 숫자를 겹쳐서 사용할 수도 있습니다. 입출력 예 1번을 보면, "3141592"가 "314" "159" ... 혹은 "341" "925" ... 이런식으로 만들어지지 않고, "314" "141" ... 처럼 순서대로 만들어지는 숫자가 같지 않게끔 만들어지는 것을 볼 수 있습니다. for문을 돌리는 길이의 계산은 이러한 방식으로 자르기 위해 나타낸 것이고, Substring()을 통해 1씩 증가하는 i부터 p의 길이만큼 잘라내는 것입니다. long타입으로 만드는 이유는 제한사항에서 정해진 p의 길이가 int형을 초과할 수 있기 때문입니다.

 

<NEXT>

오늘은 "크기가 작은 부분문자열" 문제를 풀어보았습니다. 다음에는 완전탐색 분야에 포함되어 있는 "최소직사각형" 문제를 풀어보도록 하겠습니다. 감사합니다.