코딩 알고리즘 크기가 작은 부분 문자열

2023. 12. 19. 08:21카테고리 없음

숫자로 이루어진 문자열 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 tLength = t.length();
        int pLength = p.length();

   
        for (int i = 0; i <= tLength - pLength; i++) {
            String subString = t.substring(i, i + pLength);
          
            if (Long.parseLong(subString) <= Long.parseLong(p)) {
                answer++;
            }
        }

        return answer;
    }
}



t에서 길이가 p와 같은 모든 부분String을 검사하고 각 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 경우 횟수를 증가 시켰다. 최종적으로 횟수를 반환하면된다.


또다른 풀이로 자바의 스트림 기능을 활용한 방식이 있었다.

 

class Solution {
    public int solution(String t, String p) {
        long targetNumber = Long.parseLong(p);
        int targetNumberLength = p.length();

        return (int) LongStream.range(0L, t.length() - targetNumberLength + 1L)
                .mapToObj(i -> t.substring((int) i, (int) i + targetNumberLength))
                .mapToLong(Long::parseLong)
                .filter(number -> number <= targetNumber)
                .count();
    }
}


자바의 스트림 기능을 활용한 문제 풀이이다.

자바 스트림(Stream)은 데이터를 다루는 방식을 표현하는 인터페이스이다.

 

스트림 사용시

  • LongStream.range 메서드를 사용하여 0부터 t.length() - targetNumberLength + 1까지의 범위에서 스트림을 생성한다.
  • mapToObj를 사용하여 각 인덱스에 해당하는 부분 문자열을 생성하고, 이를 다시 mapToLong을 사용하여 Long 형태로 변환한다.
  • filter를 사용하여 조건에 맞는 요소만을 남기고, count를 사용하여 그 수를 계산한다.