[알고리즘] Swift -프로그래머스 연습문제 #161989(덧칠하기)

문제링크

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

프로그래머스

 

 

 

 

 

분석

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

벽에 포스터를 게시하기 위해 테이프로 붙였다가 철거할 때 페인트가 벗겨진다. 이를 덧칠하기로 했다.

전체를 새로 칠하는 것이 아닌 구역을 나누어 일부만 페인트를 새로 칠하려 한다.

이를 위해 벽을 1미터 길이의 구역 n개로 나누고,

각 구역에 외쪽부터 순서대로 1번부터 n번까지 번호를 붙였다.

그리고 페인트를 다시 칠해야할 구역들을 정했다.

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

롤러가 벽에서 벗어나면 안된다.

구역의 일부부만 포함되도록 칠하면 안된다.

즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠한다.

현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의한다.

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 된다.

다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야한다. 

롤러로 페인트칠을 하는 횟수를 최소화하려고 한다.

정수 n, m과 다시 페인트를 칠하기로 정한 구역들이 번호가 담긴 배열로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 구하는 문제이다.

 

풀이 과정

예제를 보면 n=8(벽의 길이), m=4(롤러의 길이)

배열로 주어진 수는 다시 칠해야할 구역들이다.

그림을 보면 벽의 길이가 8이고 롤러의 길이가 4인데 2를 채우기위해서 페인트2를 칠하면 6이 남아 1번 더 칠해야하기 때문에 최소 2번의 페인트칠을 해야한다.

 

내가 생각한 풀이는

처음 칠해야할 구역에서 롤러의 길이만큼 구역을 더해서 마지막 구역을 구한 후 그 마지막 구역과 칠해야할 구역을 비교한다.

var last = sections.first! + m - 1

처음에 section 의 배열이 오름차순인 것을 몰라서 min()을 활용하여 최소값을 구해서 실행했다가 시간초과가 났다.

 

배열의 요소를 하나씩 지우면서 비울 때까지 반복한다.

마지막 롤러가 칠해진 구역과 다음 칠해야할 구역을 비교한다.

마지막 롤러가 칠해진 구역보다 다음 칠해야할 구역이 작다면 이미 롤러가 칠해진 구역이기 때문에 배열에서 지워준다.

다음 칠해야할 구역이 크다면 다음 롤러로 칠해야할 구역인 것이므로 마지막 롤러가 칠해야칠 구역을 변경해준다.

while !sections.isEmpty {
    result += 1
    for sec in sections {
        if last < sec {
            last = sections.first! + m - 1
            break
        } else {
            sections.removeFirst()
        }
    }
}

처음에는 .count != 0 으로 했는데 isEmpty를 사용하는 게 더 효율적이라 변경하였다.

 

 

풀이

import Foundation

func solution(_ n:Int, _ m:Int, _ section:[Int]) -> Int {
    var result = 0
    var sections = section
    
    var last = sections.first! + m - 1
    
    while !sections.isEmpty {
        result += 1
        for sec in sections {
            if last < sec {
                last = sections.first! + m - 1
                break
            } else {
                sections.removeFirst()
            }
        }
    }
    return result
}

 

결과

print(solution(4, 1, [1,2,3,4]))

 

 

---

📂  정리

처음에 시간초과가 나와서 당황했다... 

문제에 오름차순이라고 나와있는 것을 빨리 확인했으면 더 빨리 해결했을 텐데 고민을 조금 했던... ㅎㅎ

문제를 제발 똑바로 읽자 ㅎㅎ!!