[프로그래머스] 문자열 나누기 (Python)

[프로그래머스] 문자열 나누기

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

문제 설명

· 첫 글자를 x라고 할 때, 문자열을 읽어나가면서 x가 나온 횟수와 x가 아닌 글자가 나온 횟수가 같아질 때, 문자열을 분리

· 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복하며, 남은 부분이 없다면 종료

· 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 문자열을 분리하고, 종료

· 분리한 문자열의 개수를 반환

조건에 따라 문자열을 분리하는 과정을 반복, 부분 문자열의 총 개수를 구하는 문제

접근 방법

· for loop를 통해 s를 순회하며, 부분 문자열 sub에 한 글자씩 더하기

· 만들어진 부분 문자열 sub의 길이의 절반이 x의 개수와 같다면, 문자열 분리

· for loop 이후 남아있는 문자열이 있다면, count + 1

알고리즘 설계 및 구현

def solution(s):
    sub_count = 0
    sub = ""
    for c in s:
        sub += c
        # x와 x가 아닌 문자열의 개수가 같아지는 순간
        if sub.count(sub[0]) * 2 == len(sub):
            sub_count += 1
            sub = ""
    # 반복문 후 남은 문자열이 있다면 +1
    return sub_count if sub == "" else sub_count + 1

결과

최적화 및 개선 방안

for c in s:
        sub += c
        # x와 x가 아닌 문자열의 개수가 같아지는 순간
        if sub.count(sub[0]) * 2 == len(sub):

· count는 O(n)의 시간복잡도를 가지므로, 반복문과 함께 사용하는 현 코드는 O(n**2)의 시간 복잡도를 가짐

for c in s:
        if x_count==not_x_count:
            sub_count+=1
            x=c
            
        if c==x:
            x_count+=1
        else:
            not_x=1

· count를 쓰지 않고 x와 x가 아닌 문자의 개수를 비교한다면, O(n)의 시간복잡도로 줄일 수 있음