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

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

프로그래머스

 

0️⃣

문제

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

입출력 예 #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에 해당한다는 점에 주의하세요

 

1️⃣ 어떻게 문제를 풀까?

t를 p의 크기로 잘라서 p와 비교!

 

📌 이슈

- String(ex."271", "06")을 int로 어떻게 바꿀까?

    → int반환 : Integer.valueOf()

    → Integer반환: Integer.parseInt()

 

1) 첫번째 시도 (런타임 에러)

class Solution { //몇몇 test case에서 런타임 에러!
    public int solution(String t, String p) {
        int answer = 0;
        
        int n = p.length(); int k = t.length();
        int int_p = Integer.valueOf(p);
        
        for(int i = 0; i < k - n + 1; ++i) {
            String part = "";
            if(n == 1) part += t.charAt(i);
            else part += t.substring(i, i + n);
            
            if(Integer.valueOf(part) <= int_p) ++answer;
        }
        
        return answer;
    }
}

→ 구글링을 해보니까 int는 10의 자리 숫자까지 밖에 저장을 못함! 그런데 1 ≤ p의 길이 ≤ 18 이므로 p를 int로 저장할 수 없음!

→ Long을 써보자 (약 19자리 숫자까지 가능!)

 

2) 두번째 시도

class Solution {
    public int solution(String t, String p) {
        int answer = 0;
        
        int n = p.length(); int k = t.length();
        Long Long_p = Long.valueOf(p);
        
        for(int i = 0; i < k - n + 1; ++i) {
            String part = "";
            if(n == 1) part += t.charAt(i);
            else part += t.substring(i, i + n);
            
            if(Long.valueOf(part) <= Long_p) ++answer;
        }
        
        return answer;
    }
}

→ 중간에 40ms은 뭐지..? 코드를 좀 간단하게 해보자

 

3) 세번째 시도

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

 

2️⃣ 배운점

- int / long 범위 잘 숙지하기

  ■ int : 10자리 숫자

  ■ long: 19자리 숫자

- 간단한 리팩토링도 성능을 2배이상 향상할 수 있구낭..!