[Java] 크기가 작은 부분문자열

문제

숫자로 이루어진 문자열 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으로 시작하지 않습니다.

 

class Solution {
    public int solution(String t, String p) {
        int answer = 0;
        int pLen = p.length();
        
        for(int i = 0; i <= t.length()-pLen; i++) {
            boolean isSmall = true;
            for(int j = 0; j < pLen; j++) {
                if(t.charAt(i+j) == p.charAt(j)) {
                    continue;
                }
                
                if(t.charAt(i+j) > p.charAt(j)) {
                    isSmall = false;
                }
                break;
            }
            if(isSmall) {
                answer++;
            }
        }
        return answer;
    }
}

위 방법은 substring() 메서드를 사용하지 않고 해결한 방법이고 그 결과이다.

문자열 t의 문자를 하나씩 가져와서 p의 길이만큼 p의 같은 위치의 문자와 비교한다.

만약 같다면 두 숫자가 같은 크기라는 뜻이므로 continue를 한다.

 

만약 두 숫자가 다르다면, 둘 중 하나의 수가 더 크다는 뜻인데, 만약 문자열 t에서 가져온 문자가 더 크다면 이는 자연스럽게 문자열로 표현된 숫자 p 보다 더 크다는 뜻이므로 isSmall 을 false로 변환하는 방법이다.

 

 

그리고 아래는 substring() 메서드를 사용한 방법과 결과이다.

class Solution {
    public int solution(String t, String p) {
        int answer = 0;
        int pLen = p.length();
        long pNum = Long.parseLong(p);
        
        for(int i = 0; i <= t.length()-pLen; i++) {
            long sliceNum = Long.parseLong(t.substring(i, i+pLen));
            if(sliceNum <= pNum) {
                answer++;
            }
        }
        return answer;
    }
}

substring을 쓴 방법과

문자열 t와 p의 문자끼리의 비교 중

문자끼리 비교하는 처음 방법이 더 시간이 빠르게 나왔다.

 

charAt은 인덱스를 이용해서 문자를 뽑기때문에 O(1)의 시간이 걸린다.

그런데 substring()은 뽑으려는 문자 길이만큼의 시간이 걸린다.

따라서, 처음 코드는 p의 길이보다 짧은 시간에 문자를 하나씩 가져오다가 중간에 결과가 나올 가능성이 있지만

substring 코드는 확정적으로 p의 길이만큼의 시간이 걸리기 때문에 시간차이가 나는 것 같다.

 

 

출처

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