[프로그래머스] 크기가 작은 부분문자열

문제

숫자로 이루어진 문자열 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

 

풀이

초기 코드

class Solution {
    public int solution(String t, String p) {
        int answer = 0;        
        String[] str = new String[t.length()-p.length()+1];
        
        for (int i=0; i<str.length; i++) {
            str[i] = t.substring(i, i+p.length());
        }
        
        for (int i=0; i<str.length; i++) {
            if(Integer.parseInt(str[i]) <= Integer.parseInt(p))
                answer++;
        }
        
        return answer;
    }
}

 

처음에 제출했던 코드이다. 테스트 케이스를 실행했을 때는 모두 통과였는데, 제출하고 보니 런타임 에러로 오답이라는 메시지가 나왔다. 이유가 뭔가 싶어 제한사항을 자세히 살펴봤더니 p의 최대 길이가 18이라는 것을 간과하고 있었다. Java의 정수를 표현할 수 있는 타입은 int와 long이 있는데, 이 둘의 차이는 간단히 정리하면 다음과 같다.

	int	long
크기	32비트	64비트
표현할 수 있는 정수 범위	-(2^32) ~ 2^32-1	-(2^64) ~ 2^64-1

 

따라서 런타임 에러를 해결하려면 str에 저장한 문자를 int 타입이 아닌 long 타입으로 변환해서 비교를 하면 된다.

 

제출한 코드

class Solution {
    public int solution(String t, String p) {
        int answer = 0;        
        String[] str = new String[t.length()-p.length()+1];
        
        for (int i=0; i<str.length; i++) {
            str[i] = t.substring(i, i+p.length());
        }
        
        for (int i=0; i<str.length; i++) {
            if(Long.parseLong(str[i]) <= Long.parseLong(p))
                answer++;
        }
        
        return answer;
    }
}

 

t를 substring() 메소드를 사용하여 p의 길이만큼 부분으로 잘라 배열에 저장하고, 이를 long 타입으로 변환하여 p와 비교하는 형식으로 부분 문자열의 크기를 비교하는 방식이다. 런타임 에러 등 문제가 생겼을 때는 제한 사항을 다시 파악하는 습관을 가져야겠다고 생각했다.

 

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/147355