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

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

프로그래머스

 

• 숫자로 이루어진 문자열 t와 p가 주어질 때,
• t에서 p와 길이가 같은 부분문자열 중에서,
• 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return

제한사항

• 1 ≤ p의 길이 ≤ 18
• p의 길이 ≤ t의 길이 ≤ 10,000
• t와 p는 숫자로만 이루어진 문자열, 0으로 시작하지 않음

 

"""
입출력 예시)

t = "3141592", p = "271" -> 2
t = "500220839878", p = "7" -> 8
t = "10203", p = "15" -> 3
"""

 

# t = "3141592", p = "271" -> 2

# t="3141592"이고 p="271" 인 경우
# t에서 길이가 3인 부분 문자열: 314, 141, 415, 159, 592
#   -> 첫 번째 문자부터 인덱스를 한 칸씩 옮기면서 p 길이만큼 자름
# 이 문자열이 나타내는 수 중 271보다 작거나 같은 수: 141, 159 
# => 2개

 

 

## 의사코드 ##

# t와 p를 split해서 리스트에 담음 -> 여기서는 str 그대로 사용 (int로 바꾸면 부분문자열 구할 때 숫자끼리 더해져버림)

# for문 돌면서 p 길이만큼의 부분문자열을 생성하고 부분문자열을 담을 리스트에 삽입

# t의 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는지 -> 문자열을 숫자로 변환해서 크기 비교

의사코드에서는 t와 p의 각 문자열을 split해서 리스트에 담는다고 썼는데 이렇게 하면 부분문자열을 담은 리스트에서 2차원 배열이 됨.

그래서 그냥 문자열 t와 p를 그대로 사용해서 문자열 슬라이싱으로 풀었음.

 

 

첫 번째 시도

 

def solution(t, p):
    answer = 0

    i = 0 # t의 인덱스
    lenp = len(p) # 문자열 p의 길이 
    stop_i = len(t) - len(p) # 슬라이싱을 멈춰야 할 t의 인덱스
    part_li = [] # 부분문자열을 담을 리스트

    while t:
        # 문자열 p의 길이가 1이면
        if lenp == 1: 
            part_li = list(t) # 부분문자열에 t의 각 문자열을 split해서 추가
        # 문자열 p의 길이가 2 이상인 경우 
        else: 
            part = t[i:lenp] # 부분문자열
            part_li.append(part) # 부분문자열 리스트에 추가
            # 다음번 부분문자열 슬라이싱을 위해 i와 lenp 각각 + 1
            i += 1 # t의 인덱스 + 1
            lenp += 1 # 문자열 p의 길이 + 1
            # 현재 t의 인덱스가 stop_i보다 크면 
            if i > stop_i:
                break # while문 탈출

    # 부분문자열을 int로 변환
    part_li = list(map(int, part_li)) 

    # 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수
    for n in part_li:
        if n <= int(p): # 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같으면
            answer += 1 # answer + 1

    return answer

-> 테스트 케이스 2에서 실행 시간 10.0초 초과

(t = "500220839878", p = "7")

 

 

통과한 코드

 

def solution(t, p):
    answer = 0

    i = 0 # t의 인덱스
    lenp = len(p) # 문자열 p의 길이 
    stop_i = len(t) - len(p) # 슬라이싱을 멈춰야 할 t의 인덱스
    part_li = list() # 부분문자열을 담을 리스트

    while t:
        # 문자열 p의 길이가 1이면
        if lenp == 1: 
            part_li = list(t) # 부분문자열에 t의 각 문자열을 split해서 추가
            break # while문 탈출
        # 문자열 p의 길이가 2 이상인 경우 
        else: 
            part = t[i:lenp] # 부분문자열
            part_li.append(part) # 부분문자열 리스트에 추가
            # 다음번 부분문자열 슬라이싱을 위해 i와 lenp 각각 + 1
            i += 1 # t의 인덱스 + 1
            lenp += 1 # 문자열 p의 길이 + 1
            # 현재 t의 인덱스가 stop_i보다 크면 
            if i > stop_i:
                break # while문 탈출

    # 부분문자열을 int로 변환
    part_li = list(map(int, part_li)) 

    # 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수
    for n in part_li:
        if n <= int(p): # 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같으면
            answer += 1 # answer + 1
    
    return answer

-> 문자열 p의 길이가 1인 경우, part_li = list(t) 한 다음 break 추가

 

 

다른 풀이

 

def solution(t, p):
    answer = 0

    for i in range(len(t) - len(p) + 1):
        if int(p) >= int(t[i:i+len(p)]):
            answer += 1

    return answer

 

def solution(t, p):
    answer = 0
    for i in range(len(t)-len(p)+1):
        answer += 1 if int(t[i:i+len(p)]) <= int(p) else 0
    return answer

 

-> 둘 다 for문을 range(len(t) - len(p) + 1)의 범위로 돌리고, t[i:i+len(p)]로 슬라이싱

 

 

나는 슬라이싱을 멈춰야 할 t의 인덱스도 따로 구해서 i가 멈춰야 할 인덱스보다 커지면 break 하도록 했는데 

이걸 range(len(t) - len(p) + 1)의 범위로 돌리면 되는 거였음

 

그리고 반복문을 돌리면서 i와 len(p)를 각각 +1을 해서 슬라이싱 했는데

i부터 i + len(p)까지 슬라이싱하는 걸로 작성하면 훨씬 간단한 거였다..! 

 

또, 부분문자열을 생성해서 따로 리스트에 담은 후에 int(p)랑 비교하지 않고 

그냥 부분문자열을 슬라이싱으로 구해서 바로 int(p)랑 비교하면 됨