[프로그래머스]Lv2. 우박수열 정적분(Python)

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

프로그래머스

 

문제 접근

 

난이도가 높지 않은 단순 구현 문제이다.

문제를 읽으며 주의해야 할 부분을 우선 정리했다.

 

1. 구간 설정 주의

주어진 ranges의 원소를 x=a, x=n-b로 꼼꼼하게 잘 바꿔주기

2. 사다리꼴의 높이는 무조건 1이므로 전체 넓이를 구하기 위해서는 사다리꼴의 넓이를 누적시켜야한다. 

3. 주어진 범위 a > b인 경우에는 -1.0을 반환하는 예외 신경쓰기

 

<시간 복잡도>

O(N^2)

 

코드

def solution(k, ranges):
    answer = []
    graph = []
    x = 0 
    graph.append([x, k])
    
    while k != 1:   # 그래프 완성하기
        x += 1
        if k % 2 == 0:
            graph.append([x, k//2])
            k = k//2
        else:
            graph.append([x, k*3+1])
            k = k*3+1
    
    n = len(graph)-1    # 가로구간의 길이 
        
    for i in ranges:
        a = i[0]    
        b = n+i[1]  
        k = b-a # 사다리꼴의 개수(=반복 횟수)
        area = 0    # 누적할 공간변수 선언 
        if a <= b:  
            for j in range(k):
                area += 0.5 * (graph[a][1]+graph[a+1][1])   # 사다리꼴 넓이 공식 적용 
                a += 1  # 우측으로 1씩 이동 
        else:
            area = -1.0
        answer.append(area) 
        
    return answer

 

문제 회고

 

단순 구현 문제임에도 40분 걸려서 현타옴... ㅋ