[코딩테스트]프로그래머스 : 스택/큐 기능개발

김은지·2022년 6월 19일
0

코딩테스트

목록 보기
13/17

내 첫 번째 답

def solution(progresses, speeds):
    answer = []
    start = 0 #나가지 못 한 원소 중 가장 첫 번째 인덱스 
    days = 0 #원소가 100이 되려면 걸리는 날짜
    count = 0 #해당 완료일에 나가는 수

    while sum(answer) != len(progresses):
      if (100 - progresses[start])%speeds[start] == 0:
        days += (100 - progresses[start])//speeds[start]
      else:
        days += (100 - progresses[start])//speeds[start] + 1

      for i in range(start, len(progresses)):
        progresses[i] += speeds[i]*days
        if progresses[i] >= 100:
          count += 1
        else:
          break
          
      answer.append(count)
      
      count = 0
      start = sum(answer)
          
    return answer

첫 번 째 답은, 맨 첫번째 인덱스가 100 이상이 되는 'days' 수를 찾고,
Progresses를 순서대로 돌면서 speed *'days'한 값을 각각에 모두 더한다.
다시 첫 번째 인덱스부터 연속적으로 100이상인 원소의 수를 count에 저장한다.
100 미만인 원소를 만나면 count를 answer에 더하고,
모든 원소가 나갈 때 까지(답안에 저장된 숫자의 합이 progresses의 길이와 같을 때 까지) 반복한다.

함께 공부하는 친구와 같은 문제를 각자 푸는 경우가 많기 때문에
문제를 푼 후 접근 방법을 공유하고는 하는데,
예솔님은 100%가 되기까지 필요한 '날짜'에 집중해서 푸셨다고 했다.
좋은 접근인 것 같아서 작성해 본 또 다른 답안

import math

def solution(progresses, speeds):
    answer = [1]
    days = [math.ceil((100-p)/s) for p,s in zip(progresses, speeds)]
    temp = days[0]
    for i in range(1, len(days)):
      if temp >= days[i]:
        answer[len(answer)-1] += 1
      else:
        answer.append(1)
        temp = days[i]
  
    return answer

##아래는 테스트를 위한 코드입니다.
progresses = [93, 30, 55]
speeds     = [1, 30, 5]

# progresses = [95, 90, 99, 99, 80, 99]
# speeds     = [1, 1, 1, 1, 1, 1]

# progresses = [90,90,90,90,90,90]
# speeds     = [10,10,10,1,10,1] #[3,3]

print(solution(progresses, speeds))

여튼 두 번째 답안에서 간과했던 것은 'temp'로 표현된 날짜 비교의 기준이다.
원래는 바로 이전의 인덱스에 저장된 날짜와 그 다음 인덱스의 날짜를 비교했었는데, 잘 못 하고 있었다. ㅎㅎㅎ...

..여튼 이제 그건 문제가 아니고
math 모듈을 import하지 않고싶어서 아래와 같이

def solution(progresses, speeds):
    answer = [1]
    days = [(100-p)//s+1 if p%s else (100-p)//s for p,s in zip(progresses, speeds)]
    temp = days[0]
    for i in range(1, len(days)):
      if temp >= days[i]:
        answer[len(answer)-1] += 1
      else:
        answer.append(1)
        temp = days[i]
  
    return answer

똑같은 코드에 days 부분만 나눠서 딱 떨어지면 몫을 리턴하고, 아니면 내림 된 몫에서 +1 하는 if 문으로 바꿨는데, 테스트케이스 2개가 실패하는 결과가 나왔다.

print(99//100) #0

거의 1에 가까운 값을 나눠도 0으로 떨어지는데, 왜 실패가 나는건지 모르겠다.
찾아봐도 이유를 알아내지 못했다.

일단 오늘은 이쯤하고 다른 사람들의 답을 찾아봤다.

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]

문제 설명에 '스택/큐' 이렇게 써있었는데,
문제를 풀면서 큐를 어떻게 활용하라는거지? 인덱스를 활용하라는건가
이렇게 생각했다.

일단 적어놓고 이해하면서 익혀야 할 것 같다.

다른 답들도 확인해보자...
또 다른 답

0개의 댓글