[프로그래머스] 덧칠하기

 

📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

 

✅ 내 풀이(Success) :

 

🧐 Review:

 n의 길이만 보고 단순하게 완전탐색으로 접근한다면 시간 복잡도가 매우 클 것으로 예상했고, 롤러의 길이는 m으로 고정되어 있으니 슬라이딩 윈도우를 이용해서 문제를 해결하면 되겠다고 생각했다. 해당 아이디어로 풀이를 구현했으나 내 예상과는 달리 시간초과가 발생하는 테스트 케이스도 있었다. 내가 처음 생각했던 방향이 아닌 다른 방향으로 접근해야겠다는 생각이 들었고,

결국 문제에서 원하는 답은 페인트 칠의 횟수를 최소화하고, 페인트 칠이 필요한 부분을 적어도 한 번은 칠하면 되는 것이다. 따라서 덧칠이 필요한 구역이 롤러의 길이 m에 포함되는지는 찾도록 했고, 풀이를 구현하는데 두 개의 포인터 변수를 이용해서 m에 포함되면 포인터를 옮기는 식으로 문제를 해결했다. 문제를 해결하고 나서 다른 사람의 풀이를 보니 데큐를 이용한 풀이가 많았고, 해당 풀이가 내 풀이보다 더 이해하기 쉽다는 생각이 들었다. 몇 달 동안 코테 공부에 손을 놓았다 보니 문제를 해결하는 것에만 급급했는데, 더욱 간결한 풀이는 없을지 꾸준히 연구해야겠다는 생각이 들었다.