프로그래머스 다섯 번째 문제: 덧칠하기(Level 1)

 

안녕하세요. 오늘은  Level 1 문제인 덧칠하기 문제를 풀어보려고 합니다.

 

 

처음에 굉장히 단순하게 풀었으나, 시간 복잡도 이슈 때문에 추가적으로 고민이 필요했던 문제였습니다.

 

 

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

프로그래머스

 

 

처음에 풀었던 풀이:

def solution(n, m, section):
    answer = 0
    
    while section: # section이 남은 경우만 반복
        start_point = section[0] # 출발 지점
        
        # 출발 지점에서 m만큼 갔는데 이게 n을 넘기는 경우
        if start_point + (m-1) > n:
            start_point -= (start_point + (m-1)) - n # 넘친 만큼 빼줌
        
        # m만큼 진행하기 
        for i in range(m):
            arrival = start_point + i
            if arrival in section:
                section.remove(arrival) # 있으면 제거
        
        answer += 1    
    return answer

 

일단 section이 남은 경우에만 계속 진행하면 되기 때문에, while에서 section의 길이를 받아 1보다 클 때만 반복문이 진행되도록 하였습니다.

 

그 후, section은 오름차순 정렬 되어 있으므로, 첫 번째 요소를 start_point로 잡았습니다.

 

단, start_point에서 m만큼 갔을 때 이것이 n을 넘는 경우가 발생할 수 있습니다.

 

이런 경우 if 문으로 따로 빼서, start_point의 값을 조정해 주는 작업을 진행하였습니다.

 

예를 들어, n이 3이고 m이 3이면서 section이 [2]라면, start_point가 2로 잡힐 것이고, 여기서 3칸을 칠하게 되면 2, 3, 4의 3 칸을 칠해야 하는 상황이 되므로 n을 넘게 됩니다.

 

그래서, 넘친 만큼인 1 만큼을 빼줘서 start_point를 1로 조정하고, 여기서 3칸을 칠하게 만들면 됩니다.

 

 

다음으로는, m만큼 칠해야 하니 반복문을 통해서 진행해 주고, 도착지점을 arrival로 저장, 만약 arrival이 section에 있다면 이를 remove 해주는 방식으로 진행하였습니다.

 

하지만, 약 6개 정도의 test case에서 시간 에러가 나는 문제가 발생했습니다.

 

그래서 어떤 부분이 문제일까.. 하고 고민해 보니 arrival이 section에 있는지 판단하는 in이 문제가 될 수 있겠다고 판단했습니다.

 

왜냐하면 in의 경우 list 안의 위치를 찾아야 하는데, 만약 section이 매우 크다면 한번 작업에 많은 연산을 요구하게 됩니다.

 

문제에서 1 <= section의 길이 <= n로 되어 있는데, n이 최대 10만이 가능하니 remove 연산은 10만 개짜리 list에서 하나를 찾는 작업을 계속해서 반복해야 합니다.

 

따라서 이 부분을 개선하는 방향으로 고민하였습니다.

 

 

 

개선된 풀이:

def solution(n, m, section):
    answer = 0
    
    while section: # section이 남은 경우만 반복
        start_point = section[0] # 출발 지점
        
        # 출발 지점에서 m만큼 갔는데 이게 n을 넘기는 경우
        if start_point + (m-1) > n:
            start_point -= (start_point + (m-1)) - n # 넘친 만큼 빼줌
                
        target_section = section[:m] # section에서 최대한 지워져도 m개 까지만 가능하니까.
        
        # target_section에서 m개 범위 안에 들면 제거
        for tar in target_section:
            if start_point <= tar <= start_point + m - 1:
                section.remove(tar)

        answer += 1

    return answer

 

일단 모든 section을 다 돌지 않아야 한다는 게 이전 풀이에서의 교훈이기 때문에, 그럼 과연 section을 다 돌지 않으려면 어떻게 해야 하는가 를 고민했습니다.

 

start_point 지점 기준으로 결국 m개만 칠하게 되는 것이고, 이는 결국 section에서 m개만 검토하면 된다는 결론이 나옵니다. 왜냐면 section은 이미 오름차순 정렬이 되어 있기 때문에, m개보다 더 많은 양은 검토할 필요가 없습니다.

 

따라서 지울지 말지 검토해야 하는 section을 target_section으로 만들고, m개만 뽑아냈습니다.

 

section[:m]으로 하게 되면, 혹시라도 section이 m개 보다 작더라도 에러가 나지 않습니다. 

 

그리고 target_section에 있는 각각 요소들을 start_point 기준으로 m개 색칠하는 범위 내에 들어가 있는지를 판단해서 제거해 주는 방식으로 진행했습니다.

 

이렇게 수정하였더니, 시간 복잡도 문제가 해결되었습니다.

 

 

 

오늘 문제는 여기까지 하겠습니다.