코드

doc = input()
k = input()

def solution(doc, k):
    cnt = 0 # 정답 변수
    i = 0   # 인덱스
    
    # len(doc) - len(k)
    # 주어지는 두 값의 차이보다 작거나 같은 경우만 수행
    # i값이 더 더 커지면, i + len(k)가 len(doc)보다 커짐
    # 더 이상 k가 doc의 부분일 수가 없음
    while i <= len(doc) - len(k):
        
        # doc[i ~ k까지의 문자열]이 k와 같다
        if doc[i:(i + len(k))] == k:
            
            # 개수 1 증가
            cnt += 1
            
            # len(k)까지 같았으므로
            # i는 그 이후의 값부터 봐야함
            # 따라서 len(k)만큼 더해줌
            i += len(k)
        # 같지 않다
        # 1만 증가시켜서 다음은 k와 같은지 비교
        else:
            i += 1
    
    return cnt
print(solution(doc, k))

문제 해설

그리디 알고리즘 문제.

난이도가 낮은 그리디 알고리즘의 경우, 생각만 천천히 꼼꼼하게 잘 하면 쉽게 해결할 수 있는 경우가 많다.

이 문제의 해결 순서는 아래와 같다.

  1. 주어지는 문자열 doc에서 찾고자 하는 문자열 k의 길이만큼 앞에서부터 탐색
    1. 찾은 부분 문자열이 k와 같으면 개수를 1 증가 시킨 후, 찾은 인덱스에 k의 길이만큼 더 함
    2. 같지 않다면 인덱스만 1 증가
  2. 인덱스의 값이 (전체 문자열 길이 - 찾고자 하는 문자열 길이)보다 작은 경우까지 탐색을 반복 수행
    1. 전체 문자열 길이 - 찾고자 하는 문자열 길이 보다 인덱스의 값이 커지면, 전체 문자열의 길이보다 부분 문자열의 길이가 더 커지므로 더 이상 전체 문자열에 속할 수 없게 되므로 의미가 없음

DP와 더불어 문제 풀이에 깊은 사고력과 센스를 많이 요하는 알고리즘이라고 개인적으로 많이 느껴지는 파트이다. 난이도가 낮은 것부터 높은 것까지 다양한 문제를 풀어 사고력을 기르고 센스를 얻도록 노력해야겠다.

댓글남기기

참고