알고리즘 공부 18일차

오늘은 프로그래머스 2단계 5문제를 풀어보았다. 항상 풀면서 느끼지만 같은 2단계지만 난이도가 많이 차이나는 것 같다. 풀었던 5문제 중 가장 시간이 오래 걸렸던 유사 칸토어 문제를 오답노트 해보자.

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

프로그래머스

처음에는 r과 l 사이 모든 값에 대해서 0인지 1인지를 확인해 주는 방법을 생각했다. 둘은 최대 차이가 10,000,000에 확인하는 방법은 최대 20이라고 생각했기 때문이다. 그래서 약 2억의 시간 복잡도가 예상되 충분할 것이라 생각했다.

def solution(n, l, r):
    answer = 0
    one_cnt=0
    for i in range(l-1,r):
        k=n
        while n:
            a, b = divmod(i, 5 ** (n - 1))
            if a==2:
                break
            i=b
            n-=1
            if n==0 and i!=2:
                one_cnt+=1
        n=k
        
    
    return one_cnt

하지만 제출했을 때 시간초과가 자꾸 났고 나는 다른 방법을 생각해야 했다. 그 다음 방법이 바로 k번째 까지의 1의 개수를 세는 함수를 이용해 r과 l사이의 1의 갯수를 구하는 것이었다. 구현은 이분의 블로그를 참고했다      https://velog.io/@cis07385/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9C%A0%EC%82%AC-%EC%B9%B8%ED%86%A0%EC%96%B4-%EB%B9%84%ED%8A%B8%EC%97%B4

[프로그래머스] 유사 칸토어 비트열

이론상으로는 이해가 되지만 아직 구현이 많이 부족한 것 같다. 특히 재귀함수를 이용할 때 자주 막히는 것을 느낀다. 코딩테스트에 더 시간을 많이 투자해야 한다고 생각한다. 내일은 8문제를 목표로 풀어보아야겠다!