🎀 본 게시물은 프로그래머스 연습문제 풀이 게시물입니다. 🎀

---

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

문제 설명

어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다.

넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.

벽에 페인트를 칠하는 롤러의 길이는 m미터

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.

정수 n, m 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.

입출력 예

n	m	section	result
8	4	[2,3,6]	2
5	4	[1,3]	1
4	1	[1,2,3,4]	4

입출력 예 설명

그림 참고

---

🚀 풀이 ⭕

나의 풀이

def solution(n, m, section):    
    answer=0
    painted=0
    for wall in section:            # 칠할 벽을 모두 확인
        if wall >= painted:         # 칠할 벽이 안칠해져있으면
            painted = wall + m      # 현재 벽 + 롤러길이 = painted만큼 칠해져있음 
            answer += 1             # 한번 칠함 
            
    return answer

다른사람 풀이1

def solution(n, m, section):    # n미터의 벽4, m미터의 롤러1, [1,2,3,4] 
    answer = 0
    idx=0   # 관심있는 칠할 벽 순서 
    pos = section[0]    # 먼저 칠해야할 첫번째 벽부터 보기로 초기화 
    while idx < len(section) and pos <= n:  # idx는 1씩 증가시킬건데 section개수 끝날때까지 반복 그리고 칠할 벽 다 하면 그만
        if pos <= section[idx]:     # 현재 벽(section[idx])가 안칠해져있으면
            pos = section[idx] + m  # 첫번째 벽(ex.2) + m미터 롤러(ex.4)=6까지 색을 칠함 
            answer += 1
        else:                       # 칠해져 있으면 
            idx += 1                # 다음 벽을 보자 
    return answer

• 빈칸이 있으면
  • 페인트를 칠하고 [현재 벽위치 + 롤러길이]위치로 이동한다
• 빈칸이 없으면
  • 계속 탐색

다른사람 풀이2

def solution(n, m, section):    # n미터의 벽4, m미터의 롤러1, [1,2,3,4] 
    answer = 0
    
    # 칠해야할 벽을 다 칠할 때까지 반복 
    while section:
        
        # 칠해야할 첫 벽 + 롤러의 길이
        length = section[0] + m
        
        # 칠해야할 벽이 아직 남아 있고, section 첫값이 (벽위치+롤러길이) 이내에 있으면
        while section and section[0] < length:
            section.pop(0)  # 벽 칠함, 칠해야할 벽에서 제거   
        # 이제 벽위치가 length(이전 벽위치 + 벽롤러길이)보다 크면 while문에서 벗어남  
        answer += 1

    return answer

1. 칠해야할 벽[section]을 다 칠할 때까지 반복 –> 칠하면 section 값을 하나씩 빼자 1-1. section의 첫값 + 롤러길이 m = length정의 1-2. length이내의 벽위치를 값는 벽은 pop으로 제거 1-3. length보다 더 큰 벽위치가 나타나면 while문을 벗어나고 answer에 1을 더하고 새로운 length 정의 (1-1 반복)
2. answer 반환

다른사람 풀이3

from collections import deque

def solution(n, m , section):
    
    answer = 0					# 페인트를 칠해야하는 최소 횟수
    section = deque(section)	# 앞에서부터 차례로 칠하기 위해 데큐 선언
    
    # 페인트 칠을 전부다 할 때까지 반복
    while section:
        start = section.popleft()	# 페인트칠 시작 지점
        
        while section and start + m > section[0]: 
            section.popleft()
        answer += 1
    
    return answer

페인트칠 시작 지점(start)부터 해서 롤러의 길이만큼(m)은 무조건 칠해지게 되있다 (여기 범위 안에 들어오게 되면 동시에 다 칠할 수 있다)

만약 롤러의 길이만큼 전부 다 칠한다음, 새로 페인트칠을 시작할 부분(section[0])이 아직도 우리가 롤러의 길이만큼 칠했던 것(start+m)보다 작다면 이미 칠한 것이므로 계속 popleft 해준다.