17. 덧칠하기 ★

 

유형 : 그리디? 구현?

풀이 시간 : 25-30분, 스스로 해결 

 

1. 기본 구현

def solution(n, m, section):
    answer = 0
    for i in range(1, n+1):
        if i in section:
            answer += 1
            for j in range(i, i+m):
                if j in section and j < n+1:
                    del section(section.index(j))
    return answer

 

일단 위 풀이에서는 시간 초과가 났다. (50/100)

시간 초과를 해결하기 위해서.. 코드를 수정해 보자. 

 

2. dictionary를 사용해봤는데 이 문제는 이렇게 푸는 게 아닌 것 같다.

def solution(n, m, section):
    answer = 0
    section_dict = dict([[section[i], i] for i in range(len(section))])
    for i in range(1, n+1):
        if i in section:
            answer += 1
            for j in range(i, i+m):
                if j in section and j < n+1:
                    idx = section_dict[j]
                    del section[idx]
                    section_dict = dict([[section[i], i] for i in range(len(section))])
    return answer

 

이중 루프가 역시 문제인걸까.. 다시 해보자. 

 

3. for문에서 건너뛰기를 사용해보았다. 

def solution(n, m, section):
    answer = 0
    next = 1
    for i in range(1, n+1, next):
        if i in section:
            answer += 1
            next = 1
            for j in range(i, i+m):
                next += 1
                if j in section and j < n+1:
                    del section[section.index(j)]
    return answer

 

마찬가지로 50/100...

 

4. 이중 루프가 문제인 것 같아, n이나 m에 루프를 걸지 말고 section을 제거하는 것을 중심으로 하는 코드를 짰다. 

def solution(n, m, section):
    answer = 0
    next = 1
    while section:
        answer += 1
        start = section.pop(0)
        limit = start + m 
        while start < limit and section:
            if section[0] >= limit:
                break
            start = section.pop(0)
    return answer

 

1. section이 존재한다면 : 일단 칠을 한 번 하므로 answer += 1 

  1) 먼저 pop() 을 통해 첫 번째 원소를 지정

  2) limit 설정 (한 번 칠하는 범위)

  3) section의 원소를 순회, 종료 조건은 1) 범위를 벗어나거나 2) section이 비거나 (= 끝)

     - 이 때, section[0] 즉 이번에 pop 될 첫 번째 원소가 limit과 같거나 크다면, break로 종료하고 pop을 하지 않음. 

2. 반복한다. 

 

이중 루프는 시간 제한에 걸릴 확률이 높으므로 사용에 유의해야 할 것 같다. 

그래도 이번 문제는 스스로 해결해서 굳