크기가 작은 부분 문자열

문제

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

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

풀이

import java.util.*;

class Solution {
    public int solution(String t, String p) {
        int answer = 0; 
        String s = "";
        ArrayList<Character> arr = new ArrayList<>();
        char[] tc = t.toCharArray();
        
        for(int i=0; i<p.length(); i++) arr.add(tc[i]);
        
        for(int i=p.length(); i<t.length(); i++){
            //검증
            for(int j=0; j<arr.size(); j++) s+=arr.get(j);       
            if(Long.valueOf(s)<=Long.valueOf(p)) answer++;
            s = "";
            
            //연결리스트 슬라이딩
            arr.add(tc[i]);
            arr.remove(0);         
        }
        
        //arr 나머지 요소 검증
        for(int j=0; j<arr.size(); j++) s+=arr.get(j);     
        if(Long.valueOf(s)<=Long.valueOf(p)) answer++;
        s = "";
        
        return answer;
    }
}

이 문제를 보자마자 슬라이딩 알고리즘 느낌으로 풀어야겠다는 생각을 했다.
연결리스트를 새로 파서 , p길이만큼 담고 계속 슬라이딩 시킨 후에, 계속 검증을 해준다. 마지막에 남아있는 arr요소의 검증도 추가로 해준다.

이 문제에서 Integer.valueOf()를 이용해서 값을 비교하면 런타임 에러가뜬다. Integer형으로 표현할 수 있는 최대 값을 초과해서 런타임 에러가 발생하는 거 같음. 그래서 값 표현 범위가 더 큰 Long.valueOf()를 이용했다.