본문 바로가기
Algorithm/스택&큐&덱&힙

[프로그래머스 lv 2] 기능개발

by HANNI하니 2023. 1. 25.

사용 언어 - Python3

문제 - 기능개발

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

정답

스택 문제

(정답 맞춘 여부 O / 코드 풀이)

100-progresses/speeds를 올림하여 finishday라는 리스트에 저장한다. 이때, 올림은 import math의 ceil 함수를 사용했다. 

예) progresses = [93,30,55], speeds = [1,30,5]일 경우, finishday = [7,3,9]가 된다.

첫번째 finishday[0]을 먼저 stack 에 넣어준다.

finishday[1]부터 max(stack)과 비교해준다. max(stack)보다 값이 작아서 먼저 이미 작업이 완료된 경우, max(stack)을 초과할 때까지 계속 stack에 append해준다.

만약 max(stack) 을 초과한다면 지금까지의 stack 길이를 answer에 추가해주고, stack을 리셋해준다.

그리고 다시 현재 값부터 append 해준다.

answer에 추가된 값을 프린트해주면 되는데, 이때 마지막에 저장되어 있는 스택 길이는 저장이 안되었기 때문에, for문을 빠져나간 뒤에 len(stack)을 answer에 추가해준다.

# 내 정답
import math

def solution(progresses, speeds):    
    answer = []

    finishday = []
    for i in range(len(speeds)):
        finishday.append(math.ceil((100-progresses[i])/speeds[i]))

    stack = []
    stack.append(finishday[0])

    for f in finishday[1:]:
        if f > max(stack):
            answer.append(len(stack))
            stack = []
        stack.append(f)
    answer.append(len(stack))

    return answer


<다른 사람의 풀이>

1. zip을 이용

작업 속도 개선

2. math.ceil를 사용하지 않고 올림

(p-100) = 음수

(p-100)//s = 음수에서 내림은 절대값이 커지기 때문에 내림한 음수값

-((p-100)//s) = 올림한 양수

3. Q[i][0] : 해당 작업이 끝나기까지 필요한 일수

해당작업이 끝나기까지 필요한 일수가 해당 작업일자보다 큰 경우,

예를 들어, Q에 들어있는 마지막 작업의 작업일수는 1일인데, 해당 작업을 하려면 10일이 필요하다면

10일이 드는 작업은 배포하지 못하고, 현재 Q에 들어있는 1일짜리 작업만 배포하게 된다.

기본적으로 자기자신 1개는 배포가능하기 때문에 1을 append 한다.

 

그렇지 않은 경우,

배포가능한 기능수를 한개씩 추가한다. 앞작업에서 구했던 Q의 원소에서 기능수 +1을 해준다.

 

배포 가능한 기능수만 return 해준다.

# 다른 사람의 풀이

def solution(progresses, speeds):
    Q=[]
    
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0] < -((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
            
    return [q[1] for q in Q]

레퍼런스

  • 정답 깃허브
 

GitHub - yyeongeun/codingtest: 코딩테스트 공부

코딩테스트 공부. Contribute to yyeongeun/codingtest development by creating an account on GitHub.

github.com

 

댓글