[프로그래머스][PYTHON] Lv. 1 덧칠하기
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/161989
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
처음 시도한 풀이
## 틀린 풀이
def solution(n, m, section):
answer = 0
# 페인트가 칠해진 구역은 1로, 페인트가 벗겨진 구역은 0으로 지정
wall = [1] * n
for i in section:
wall[i-1] = 0
# wall 안에 0이 있으면 페인트질 반복
while wall.count(0) > 0:
# 롤러의 길이만큼 모두 1로 변경. 1은 페인트칠이 되었다는 의미
tmp = wall.index(0)
wall[tmp:tmp+m] = [1] * m
answer += 1
return answer
리스트의 인덱스를 이용하여 페인트가 칠해진 구역은 1로, 페인트가 벗겨진 구역은 0으로 지정하여 풀어보았다.
wall 배열 안에 페인트가 안칠해진 구역(0)이 있으면, 페인트질을 반복하는 형식으로 풀어보았다.
50개의 테스트 케이스 중 12, 17, 35번에서 시간초과가 발생하였다.
count를 통해 배열의 순회를 하는 것이 시간이 오래걸리기 때문에 시간초과가 발생했던 것이였다.
(count 함수의 시간복잡도는 O(n)이다)
따라서, 배열을 이용하는 것이 아닌 다른 풀이를 생각해야했다.
정답 풀이
## 맞은 풀이
def solution(n, m, section):
n_painted, answer = 0, 0
for s in section:
if s > n_painted:
n_painted = s + m - 1
answer += 1
return answer
다른 사람의 풀이를 참고한 코드이다ㅠ
사실 처음에 보고 좀 이해하기 어려웠다.
n_painted는 페인트가 칠해진 구역의 끝을 나타낸다.
section 안의 값들만을 순회하며, m만큼의 페인트 칠을 해주고,
다음 section의 원소가 이미 칠해진 구역(n_painted)보다 클 때만 n_painted를 갱신하고, answer을 더한다.
각 section의 원소가 n_painted보다 작거나 같으면, 이미 페인트가 칠해져있기 때문이다.
-> 하나씩 써보며 풀이해보니 이해가 되었다!
다른 사람 풀이
def solution(n, m, section):
answer = 1 # 칠하는 횟수
paint = section[0] # 덧칠 시작점
for i in range(1, len(section)):
if section[i] - paint >= m:
answer += 1
paint = section[i]
return answer
위의 코드와 굉장히 유사한 풀이이다!
이는 전체 section의 범위를 이용하는 것이 아닌, 덧칠을 해야하는 구간인 secion 요소들 간의 범위를 구한 코드이다.
덧칠 시작점인 paint를 section[0]으로 정해놓고, for문을 통해 paint와 section[i] 간의 간격을 구한다.
즉, 롤러의 길이 m=4이면 1, 2, 3, 4를 1번의 페인트칠로 칠할 수 있으므로,
1번의 칠로 가능한 범위는 4-1=3이다. 즉, m-1 이다.
따라서, m-1의 범위까지는 1번의 페인트칠로 가능하므로, m부터는 2번의 페인트칠이 필요하다.
그러므로 section[i] - paint가 m 이상이면 answer+1을 해주어야 한다.
이렇게되면 1번의 페인트칠을 완료했으므로, 다음 칠할 구간을 찾게 된다.
다음 칠할 구간을 찾기 위해 section[i]를 paint 시작점으로 바꾸고, 다시 범위를 찾는 과정인 for문을 반복한다.
느낀점
1단계 문제를 풀고있긴한데,, 알고리즘 강의를 먼저 듣는게 좋을 것 같다.
생각보다 알고리즘 지식이 많이 떨어지는듯하다.
유튜브 나동빈님의 '이테코' 강의를 먼저 들으면서, 그 알고리즘에 맞는 문제들을 풀어보는 형식으로 해봐야겠다!