[프로그래머스 코딩테스트 kit] 스택 - 기능개발

기능개발

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

 

프로그래머스 알고리즘 고득점 kit의 스택/큐 문제 중 기능개발을 풀어보았다. 좋은 문제여서 오답을 작성한다. 

 

 

1️⃣ 분석

작업 진행도와 해당 작업의 속도를 담은 두 개의 배열이 주어진다. [90, 55], [1, 10] 이렇게 주어진다면 후자의 일이 더 빠르게 끝난다. 첫 번째 일이 끝나야 두 번째 일이 같이 배포될 수 있기 때문에 한 타임스탬프에 배포되는 일의 수는 2개이다. 이런식으로 배열이 주어진다면 각각의 타임스탬프마다 배포되는 일이 몇 개인지 구하는 문제이다.

 

우선 스택 혹은 큐를 사용할까 고민했고, 결론적으로 데큐를 사용하기로 했다. 그 이유는 주어진 작업에 순서가 있기 때문이다.

스택에 append를 사용하고 pop을 사용한다면, 마지막 일이 먼저 빠져나가기 때문에 앞 일과의 관계를 따질 수 없다.

그래서 일단 deque를 사용하기로 했다.

 

문제를 풀기 전 문제의 내용을 세부 부분으로 쪼갰다.

1. 일 수 계산
    - 대소 비교니까 하나씩 계산해서 비교하기

2. answer 배열 넣기
    - top보다 작거나 같으면 +1
    - top보다 크면 다음 원소

먼저 progresses와 speeds를 이용해 작업이 끝나는 일 수를 계산했다. 그리고 deque에다 하나씩 넣으면서 앞 일보다 뒷 일이 언제 끝나는지를 판단해 answer 배열을 작성했다.

 

 

2️⃣ 실제 코드 작성

처음 코드를 작성할 때 deque에 progresses와 speeds 이용해 계산한 끝나는 날짜를 모두 담으려고 했다. 그리고 하나씩 꺼내면서 어느 타임스탬프에 해당 일이 포함되는지 확인하려고 했다. 하지만 다음의 문제가 있었다.

 

1. 코드 길이가 길어짐
2. deque에서 원소 두 개를 비교해야하기 때문에 이걸 처리하기 위한 로직이 복잡해짐

그래서 끝나는 날짜를 계산하고 그 값을 바로 deque에 넣는게 아니라 넣기 전에 전 작업과 비교하는 로직을 추가했다.

이렇게 하니 deque에서 popleft하는 로직을 따로 추가하지 않아도 되어 편했다.

그럼 자료를 담는 deque도 사용하지 않아도 되니 차라리 리스트를 이용한 스택을 사용하기로 했다.

 

def solution(progresses, speeds):
    st = []
    answer = []
    cnt = 1
    for i in range(len(speeds)):
        # 일 수 계산
        temp = (100 - progresses[i]) % speeds[i]
        real = (100 - progresses[i]) // speeds[i]
        
        if temp: real += 1
        
        # answer 배열 넣기
        if i == 0: 
            st.append(real)
        elif st[-1] < real:
            st.append(real)
            answer.append(cnt)
            cnt = 1
        else: 
            cnt += 1
    
    answer.append(cnt)
    
    return answer

• 일 수 계산 파트에서 작업이 끝나는 일을 계산한다. 만약 나머지가 생긴다면 하루 더 걸린다는 뜻이기에 1을 더한다.
• 첫 번째 일은 비교할 일이 없기 때문에 바로 스택에 넣는다.
• 두 번째 일부터 첫 번째 일과 비교하고 어느 타임스탬프에 들어가는지 결정한다.
  • 만약 뒷 일이 앞 일보다 걸리는 시간이 길다면 다른 타임스탬프에 들어가므로 answer 배열에 추가한다.
  • 뒷 일이 앞 일보다 적게 걸리면 앞 타임스탬프에 포함되어 배포되므로 cnt를 1 증가시킨다.
• 마지막 일은 타임스탬프가 더해지지 않으므로 따로 타임스탬프를 더하는 로직을 추가한다.

 

 

💡 배운 점

• 자료구조에 넣기 전 원소를 판단하는 로직을 추가해 넣기
• 스택이나 데큐냐, 언제 어떻게 사용해야 하는지 느끼기