프로그래머스 알고리즘, 기능개발 swift 배열큐 문제풀이

 

 

안녕하세요? iOS Developer, 멍구입니다. 
오늘은 프로그래머스의 스택/큐 고득점킷에 있는 중제 중 하나인 기능개발 문제를 Swift언어로 풀어보도록 하겠습니다. 🤗

바로 문제 설명 가보겠습니다.

 

 

---

프로그래머스 고득점킷 기능개발 문제설명

 

 

기능개발 문제 설명입니다. 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%에 도달하면 서비스에 반영할 수 있는데요. 각각의 작업은 서비스 개발속도가 다릅니다. 또한 앞의 서비스작업을 끝내야 순차적으로 이후의 서비스를 배포할 수 있습니다. 

이때 각각의 배포에서 몇개의 기능이 배포되는지를 확인하는 문제입니다. 가령, 두번째 작업이 하루만에 개발된다 하더라도, 첫번째 배포할 작업이 3일이 걸린다면, 첫번째 작업이 배포되는 3일 시점에 두번째 작업이 함께 배포가 되겠습니다.

 

 

 

 

제한사항입니다. 작업의 개수는 100개 이하로, N^2의 복잡도여도 1초 이내에 뚝딱할 수 있는 문제입니다. 물론 그래도 효율적인 방법을 사용해야겠죠?

 

 

 

 

입력값은 위와 같습니다. 
- progress : 각 작업의 초기 진행상황 퍼센테이지를 배열로 입력받습니다. [93%, 30%, 55%] 가 되겠네요.
- speeds : 각 서비스 작업 속도입니다. 하루에 해당 퍼센트만큼 작업을 하게 되고, 100%에 도달하는 날짜에 서비스개발이 완료됩니다. (무론 앞선 서비스가 개발되지 않았으면 배포는 미뤄지겠죠?)

출력값은 배열을 반환하면 됩니다. 
- return : 각 배포마다 배포되는 갯수를 반환하면 됩니다. 첫 배포에 2개의 서비스가, 두번째 배포에 1개의 서비스가 배포됩니다. 

이제 Swift언어로 기능개발 문제를 풀어보겠습니다!

 

 

---

프로그래머스 고득점킷 기능개발 스위프트 풀이

 

 

- Q : 각 작업의 작업완료 소요 수가 들어갑니다.
- Ans : 답이 들어갈 배열입니다. 

이 문제의 핵심은 각 기능이 완료하는데 필요한 일 수를 구하고, 해당 일 수를 기준으로 각 배포마다 배포되는 서비스 갯수를 파악하는 것입니다. 그렇다면 그 완료에 필요한 일 수는 어떻게 구할 까요? 

바로 [(100 - 초기 개발% - 1) / 개발속도 + 1] 가 됩니다. -> 해당 올림값이 작업완료하는데 필요한 일 수가 됩니다. 

여기에서 분자에 -1 을 하고, 나누기 연산 후 +1 을 해주면, (100 - 초기 개발%) / 개발속도 값의 올림값이 됩니다. 이는 Int 타입의 나머지 연산이 결과값에 내림처리하는 것을 방지하기 위함입니다. 

 

따라서, progresses.indices 반복문 내에서 Q 배열에는 각각의 작업에 대한 작업완료 필요 일수가 들어가게 됩니다. 

 

 

---

배열큐 O(N^2) 시간복잡도 문제풀이

 

 

먼저, 단순 배열큐를 통한 문제 풀이입니다. 모든 작업이 끝나는 Q 배열큐가 텅텅 비는 시점(while Q.isEmpty)동안 연산을 수행합니다. 가장 앞서 수행되어야 할 작업은 Q.first!에 위치하므로, 그로부터 nowDelay 값을 가져옵니다. 

while !Q.isEmpty && Q.first! <= nowDelay 반복문 구간에서 이제 가장 앞선 서비스가 배포될 때 함께 배포될 수 있는 서비스들을 카운트 하게 됩니다. nowDelay 일 수가 지났을때 이미 완료된 모든 서비스들을 카운트(taskCnt += 1)하고, 작업큐에서 빼내게 되는 것입니다. (Q.removeFirst())

그렇게 한번의 배포가 완료되면 Ans 배열에 해당 카운트를 넣어줍니다. (Ans.append(taskCnt)) 

이렇게 반복분을 수행해서 Q 배열큐가 비게 되면 반복연산을 종료하고, 최종정답, Ans 배열을 리턴하게 됩니다. 

 

 

 

 

해당 알고리즘의 시간 복잡도는 O(N^2)입니다. 왜일까요? 바로 스위프트 배열의 removeFirst() 연산은 큐의 pop()과 달리 O(N)의 복잡도를 가지며 이를 최대 N번 반복 수행하기 때문입니다. 

해당 문제의 입력값 범위가 최대 100이라 망정이지, 만약 10만의 시간복잡도라면 1초 이상의 이상이 걸리게 되는 코드입니다. 
그렇다면 스위프트에서 어떻게 보다 효율적인 코드로 큐를 구현할 수 있을까요? 방법은 더블스택큐나 커서를 사용한 배열큐 사용등이 있습니다.

저는 배열큐와 커서를 사용해서 구현해보겠습니다. 

 

 

---

배열큐+커서 O(N) 시간복잡도 문제풀이

 

 

이번에는 배열큐에 커서를 활용한 코드인데요. 차이가 보이시나요?? 배열큐인 Q의 first! 프로퍼티와 removeFirst() 메서드 사용이 없어지고, 대신 cur 라는 커서변수를 사용하고 있습니다.

배열의 첨자접근 소요 시간복잡도는 O(1)이기때문에 removeFirst() 메서드 사용시보다 효율적인 시간복잡도 성능을 보이게 됩니다. 

 

 

 

 

위의 O(N^2) 시간복잡도 코드 결과와 해당 코드 결과를 보면 극명한 효율성 차이를 보입니다. 최대 100개의 입력범위인데도 말이지요. (수십배 차이나는 것도 보이네요.)
그런만큼, 단순 배열큐를 사용할때, removeFirst() 등의 메서드 사용에는 많은 고민을 해보시기 바랍니다. 🥰

 

 

---

지금까지 스위프트 언어를 통해서 프로그래머스 고득점킷 알고리즘 문제, 기능개발 문제를 풀어보았습니다. 많은 의견, 댓글 환영합니다. 감사합니다. 😆