728x90
https://school.programmers.co.kr/learn/courses/30/lessons/161989
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 접근
전체 구역 개수(n), 한번에 칠할 수 있는 개수(m), 칠해야하는 구역(section)이 주어질 때, 위와 같이 페인트를 덧칠하려는데 다시 칠해야하는 최소 횟수를 구하는 문제
작성한 코드(시간초과)
def solution(n, m, section):
answer = 0
#전체 구역
s = [1] * n
#칠해야할 구역
for i in section:
s[i-1] = 0
#안 칠한 구혁이 없을 때까지
a = 0
while 0 in s:
if s[a] == 0:
answer += 1
for i in range(m):
if a+i < n:
s[a+i] = 1
else:
continue
a += 1
return answer그리디 느낌으로 안칠해져있는 부분을 발견하면 m만큼 칠해주는 식으로 접근
제한 사항이 100,000이라 시간초과(제한사항을 안보고 구현해버림;)
좀 더 최적화 시킬 방안을 생각해봐야겠다.(최소 O(n))
수정 코드(다른 사람 코드 가져옴)
from collections import deque
def solution(n, m, section):
answer = 0
section = deque(section)
#페인트 칠을 전부 다 할 때까지 반복
while section:
#페인트 칠 시작지점
start = section.popleft()
#m만큼 페인트 칠하기
while section and start + m > section[0]:
section.popleft()
answer += 1
return answer나처럼 접근하면 시간초과가 날 수 밖에 없을 것같아 다른 사람 코드를 가져옴
deque를 이용하였는데, 제일 가독성이 좋아보여서 가져옴
정답 코드 해석
- section을 deque로 선언
- 나처럼 n만큼 배열을 선언해서 처리하면 시간초과가 되므로 section을 탐색함
- section에서 하나씩 pop을 해주는데, +m 미만까지 전부 pop을 해줌
- section이 전부 비어있으면 모든 구역을 덧칠해준것으로 간주
출저:
프로그래머스 - 덧칠하기 (python)
deque를 활용해서 풀 수 있었던 문제
velog.io
느낀점
- 작성하기전에 시간복잡도 계산을 어느순간 안하고있었음
- 너무 직관적으로만 해석하려하는듯 좀 더 유동적으로 생각할 수 있어야할 듯(위 문제로 치면 n으로 구역을 전부 선언해 주는 것이 아닌 section을 전부 해결하면 되는 것이였음)