12월13일 수 TIL

알고리즘 43번 크기가 작은 부분문자열

• 문제 설명

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

🔰 내 풀이

public int solution(String t, String p) {
        char[] charArr = t.toCharArray();
        int size = charArr.length - p.length() + 1;
        char charArr2[] = p.toCharArray();
        Long pInt = Long.parseLong(p);
        int count = 0;

        Long a;

        for(int i =0;i<size;i++){
            String stringValue = "";
            for(int j=i;j<p.length()+i;j++){
                stringValue += charArr[j];
            }
            if(stringValue.isEmpty()){
                 a = 0L;
            }else {
                 a = Long.parseLong(stringValue);
            }
            if(a <= pInt){
                count++;
            }

        }

        return count;
    }

-> chatGPT : 코드의 성능을 고려하면, 'stringValue'에 문자를 추가할 때마다 새로운 문자열 객체가 생성되므로, 이 방식은 메모리를 많이 사용하고 성능이 떨어집니다. 이를 해결하기 위해 StringBuilder를 사용하는 것이 좋습니다.

🤖 chatGPT가 제안한 코드

public int solution3(String t, String p) {
     char[] charArr = t.toCharArray();
     int size = charArr.length - p.length() + 1;
     BigInteger pInt = new BigInteger(p);
     int count = 0;

     for (int i = 0; i < size; i++) {
         StringBuilder stringValue = new StringBuilder();
         for (int j = i; j < p.length() + i; j++) {
             stringValue.append(charArr[j]);
         }
         BigInteger a = new BigInteger(stringValue.toString());
         if (a.compareTo(pInt) <= 0) {
             count++;
         }
     }
     return count;
 }

• BigInteger란?
  BigInteger는 Java에서 제공하는 클래스로, 임의의 크기를 가진 정수를 표현하고 연산할 수 있게 해준다. int나 long 타입의 변수는 특정 범위의 숫자만 저장할 수 있는데, 이 범위를 초과하는 정수를 다루려면 BigInteger를 사용해야 해야한다. BigInteger는 불변(immutable) 객체로, 한 번 생성되면 그 값을 변경할 수 없습니다. 따라서 산술 연산 등을 수행할 때마다 새로운 BigInteger 객체가 반환된다.

     import java.math.BigInteger;
  
  public class Main {
      public static void main(String[] args) {
       BigInteger bigInteger1 = new BigInteger("12345678901234567890");
       BigInteger bigInteger2 = new BigInteger("98765432109876543210");
  
      // 산술 연산
          BigInteger sum = bigInteger1.add(bigInteger2);
          BigInteger diff = bigInteger1.subtract(bigInteger2);
          BigInteger product = bigInteger1.multiply(bigInteger2);
          BigInteger quotient = bigInteger1.divide(bigInteger2);
          BigInteger remainder = bigInteger1.remainder(bigInteger2);
  
          System.out.println("Sum: " + sum);
          System.out.println("Difference: " + diff);
          System.out.println("Product: " + product);
          System.out.println("Quotient: " + quotient);
          System.out.println("Remainder: " + remainder);
      }
  }

👱 다른 사람의 코드 1

 public int solution2(String t, String p) {
        int pLength = p.length();
        long pValue = Long.parseLong(p);
        int answer = 0;
        for (int i = 0; i <= t.length() - pLength; i++) {
            long tValue = Long.parseLong(t.substring(i, i + pLength));
            if (tValue <= pValue)
                answer++;
        }
        return answer;
    }
    

나처럼 for문을 2번 사용하지 않고 subString을 사용하여 반복문을 줄였다.
-> 코드를 간소화하고 가독성을 높일 수 있다.
-> 성능 향상 : 각 부분 문자열을 문자열로 처리한 후 Long 값으로 변환하는 과정이 추가로 필요, 중첩된 루프를 쓰지 않음

🙆 다른 사람의 코드 2

public int solution4(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();
 }

• LongStream.range(0L, t.length() - targetNumberLength + 1L : 0부터 t의 길이에서 targetNumberLength를 뺀 값까지의 범위를 생성, 부분 문자열의 시작인덱스를 표시한다.

• .mapToObj(i -> t.substring((int) i, (int) i + targetNumberLength)) : 각 시작 인덱스를 기반으로 t 문자열에서 targetNumberLength 길이의 부분 문자열을 추출한다.

  IntStream intStream = IntStream.of(1, 2, 3, 4, 5);
  Stream objectStream = intStream.mapToObj(value -> Integer.valueOf(value * 2));

• .mapToLong(Long::parseLong)

• .filter(number -> number <= targetNumber) : 변환된 long 값들 중에서 targetNumber보다 작거나 같은 값만 필터링

• .count(): 필터링된 결과의 개수를 반환한다.