[프로그래머스][PYTHON] Lv. 0 문자열이 몇 번 등장하는지 세기

문제설명

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

프로그래머스

 

 

내 풀이

def solution(myString, pat):
    answer = 0
    for i in range(len(myString)-len(pat)+1):
        # myString을 순회하며, pat의 길이만큼 자른다. 
        # 그것이 pat과 같으면 값을 하나 올린다. 
        if pat in myString[i:i+len(pat)]:
            answer += 1        
    return answer

 

처음에는 count만을 이용해서 풀었는데, count는 중복되는 부분을 찾지 못하여 풀 수 없었다. 

친구의 힌트를 듣고 for문을 이용해서 풀어보았다^^

 

테스트 케이스의 "banana"로 설명해보자면..

먼저 banana에서 마지막 pat의 길이만큼은 제외하고, for문을 순회한다. 

즉, 우리가 순회하고자 하는 부분은

banana

anana

nana

ana

이다. 

 

해당 부분에서 pat이 있는지 확인하기 위해 순회하고자 하는 부분을 pat의 길이만큼으로 자른다. 

즉, 

banana -> ban

anana -> ana

nana -> nan

ana -> ana

로 자르게 된다.

 

이 부분이 pat(ana)과 같다면, answer 값을 하나 늘린다. 

 

성능 개선

myString의 길이와 pat의 길이가 길 때, 나타날 수 있는 시간 초과 문제를 해결하기 위해 성능개선을 해보자

def solution(myString, pat):
    answer = 0
    for i in range(len(myString)-len(pat)+1):        
        for j in range(len(pat)):
            if pat[j] != myString[i+j]:
                break
        else:
            answer += 1
                
    return answer

 

일단 순회하고자 하는 부분은 위와 동일하다. 

banana

anana

nana

ana

이다. 

 

이때, 각 부분에서 pat의 각 단어를 비교할 것이다. 

pat이 ana이라고 해보자. 

만약 pat의 첫 글자[j]와 위에서 자른 myString의 첫 글자[i+j]가 같지 않다면, for문을 끝낸다. 

pat의 모든 글자와 주어진 범위의 myString과의 글자가 모두 같다면 answer을 하나 올린다. 

 

i = 0, 1, 2, 3 / j = 0, 1, 2

i = 0   j = 0

i = 0   j = 1

i = 0   j = 2

 

j는 pat의 길이를 의미하며, i는 잘라낸 범위의 시작 인덱스를 의미한다. 

 

 

for - else 문

for문과 같이 사용되는 else문을 for문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행되었을 경우

else문이 실행되는 방식으로 진행된다. 

 

위의 문제에서 적용하자면, pat의 모든 부분을 순회하며, myString과 같은지 확인하고, 

같지 않다면  break를 통해 for문을 빠져나오고, 

만약 모든 범위가 같다면 else문에서 지정한대로 answer을 하나 올린다. 

 

 

성능 개선까지 생각하니 많이 어려운 것 같다, 

난 언제쯤 잘 할 수 있을까. 

잘하고 싶다. 

끄읏-!