[99클럽 4기 코테 스터디 TIL 2일차] 크기가 작은 부분 문자열

https://school.programmers.co.kr/learn/courses/30/lessons/147355?language=java

프로그래머스

1) 내가 구현한 코드

class Solution {
    public int solution(String t, String p) {
        
        int answer = 0; 
        
        long pNum = Long.parseLong(p);
        long val = -1; //관례적으로 long 타입 선언 시 -1로 초기화 많이함 (long val; 대신 사용)
        
        int tLen = t.length();
        int pLen = p.length();

        for(int i=0; i<tLen-pLen+1; i++){
            val = Long.parseLong(t.substring(i,i+pLen));
            if(val <= pNum) answer++;
        }
        
        return answer;
    }
}

2) 오늘의 학습 키워드

• 부분 문자열 추출
• 문자열-숫자 비교
• 슬라이딩 윈도우 기법

3) 공부한 내용 정리

이번 문제는 문자열 t에서 문자열 p와 길이가 같은 부분 문자열을 모두 비교하여 p보다 작거나 같은 값의 개수를 찾는 문제다.

여기서 주요 학습 포인트는 슬라이딩 윈도우 기법을 통한 부분 문자열 추출과 문자열을 숫자로 변환하여 비교하는 방법이다.

1. 부분 문자열 추출:
   • 문자열 t에서 p와 길이가 같은 부분 문자열을 순차적으로 추출하는 작업이 필요하다.
   • 이를 위해 슬라이딩 윈도우 방식을 사용하여 반복 작업의 효율성을 높일 수 있다.
2. 숫자 비교:
   • 각 부분 문자열을 정수형으로 변환한 후, 정수형 p와 비교한다.
   • 이 과정에서 Integer 타입을 넘어가는 긴 숫자를 처리하기 위해 Long 타입으로 변환하는 것이 중요하다.
3. 슬라이딩 윈도우:
   • t의 길이에서 p의 길이만큼 반복해 부분 문자열을 얻고, 해당 부분 문자열을 Long으로 변환하여 조건을 만족하는 경우 카운팅하는 방식으로 접근한다.

4) 문제 해결 과정

1. 문제 접근:
   • 문자열 t에서 p의 길이와 같은 부분 문자열을 순차적으로 가져온다.
   • 각 부분 문자열을 정수로 변환하여, 정수형 p와 비교 후 작거나 같으면 카운트를 증가시킨다.
2. 해결 시도:
   • t에서 p와 같은 길이의 부분 문자열을 반복문으로 추출하며, 슬라이딩 윈도우 기법을 적용했다.
   • Integer 대신 Long으로 변환하여 숫자가 큰 경우도 안전하게 비교할 수 있도록 했다.

 

5) 오늘의 회고

• 문제점
  • Integer.parseInt()를 사용하면 큰 숫자를 다룰 때 오버플로우 문제가 발생할 가능성이 있었다.  주의하자!!!!!
• 시도한 방법
  • Long.parseLong()을 통해 p와 부분 문자열을 비교할 수 있도록 했다.
• 새롭게 알게 된 점
  • 슬라이딩 윈도우 방식을 통해 반복문 내에서 연산을 최소화하고 시간 복잡도를 줄이는 방법을 배우게 되었다.
• 내일 학습 목표
  • 슬라이딩 윈도우 기법을 다양한 문제에 응용해보고, 문자열과 숫자 변환 시 효율성 높이기

 

 

Q1: Integer와 Long 변환의 차이가 성능에 미치는 영향은 무엇일까?

Q2: 다른 언어에서는 이 문제를 어떻게 구현할 수 있을까? Python을 사용해 비교하면 어떤 차이가 있을까?

Q3: 슬라이딩 윈도우 기법 외에 부분 문자열을 효율적으로 추출할 수 있는 방법은 어떤 것이 있을까?

 

 

 

6) 추가 문제

미들러 - 징검다리

https://www.acmicpc.net/problem/11561

챌린저 - 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389