[알고리즘/Swift] 스택/큐 문제풀이 - 프로그래머스 기능개발, 프린터, 다리를 지나는 트럭

Swift 스터디 9주차 6/15 .

스터디 3주차 챕터였던 "고급 데이터 구조의 활용" 에서 스택, 큐, 순환 버퍼, 우선순위 큐, 연결 리스트에 대해 학습했었습니다. 이와 관련되서 알고리즘 문제 풀이를 진행했고, 프로그래머스의 스택/큐 챕터를 풀었습니다. 

[Swift] 스터디 3주차 - 스위프트 데이터 구조와 알고리즘

---

 

✔︎ 기능개발

 

💡 참고 사항

 

• "뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다." -> Queue 자료구조를 떠올림
• "작업의 개수는 100개 이하이다." -> 시간복잡도에 큰 영향을 받지 않는다.

 

👀 풀이 과정

 

• progresses, speeds 배열을 Queue 형태로 생각해서, 작업이 끝난 경우에는 pop 해주도록 한다. 
• progresses 배열이 비어있을 때 까지 아래 작업을 반복한다. (모든 작업이 끝날때까지)
• 하루가 지날 때 마다 작업의 진도를 계산한다.
• 배포가 가능한 경우 (progresses.first 가 max 인 경우), 배포할 수 있는 작업을 카운팅한다.

 

👇 코드

 

• Queue 를 직접 구현하지 않고 요소 추가시에는 Array.append, 요소 삭제시에는 Array.removeFirst 메서드를 이용했다.
• removeFirst 메서드는 시간복잡도가 O(n) 이므로, 입력 데이터가 커질 경우에는 신경쓰자.
• progresses 배열에서 첫번째 요소를 가져올 때에는 Array.first 프로퍼티를 이용했다. 
• first 프로퍼티는 Optional 값을 리턴하므로, nil 처리를 해주어야 한다는 점을 신경쓰자.

 

songda515/SwiftAlgorithm

 

---

 

✔︎ 프린터

 

💡 풀이 과정

 

• "일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄" -> FIFO 구조, Queue 를 떠올릴 수 있음
• "중요도가 높은 문서를 먼저 출력하도록 한다." -> 작성된 요구사항에 맞게 코드를 구현하면 된다.
• "내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶다" -> 문서의 순서가 변경될 때마다 index 값을 변경하면 된다.
• (2) 가장 앞에 있는 문서(J) 가 맨 뒤로 가는 경우 -> 내가 요청한 문서라면? location = priorities.count - 1 : location - 1
• (3) 가장 앞에 있는 문서(J) 가 출력되는 경우 -> 내가 요청한 문서라면? break , 아니라면? index -= 1 

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

 

👇 코드

songda515/SwiftAlgorithm

 

 

✔︎ 다리를 지나는 트럭

 

💡 풀이 과정

 

• 다리를 건너고 있는 트럭의 무게와 위치를 저장하기 위한 큐 (배열) 을 각자 만든다. -> bridgeQueue, truckTime
• 대기 트럭의 첫번째가 다리에 올라갈 수 있을 때, 무게를 더하고 bridgeQueue 와 truckTime 에 값을 추가한다.
• 다리를 건너고 있는 트럭의 위치를 계산해준다. -> truckTime 전부 1씩 더함
• 다리를 건너는 중인 첫번째 트럭이 다리를 다 건넜을때, 무게를 빼고 bridgeQueue 와 truckTime 에 값을 제외한다. 

 

👀 참고 사항

 

• 처음에 코드를 작성할 때에는 다리위의 트럭의 무게를 더할 때, 매번 배열의 합을 계산했다.
• 누적합의 개념이 떠올라서 트럭의 무게를 매번 계산하는 것이 아닌, 추가되고 제외될 때에만 계산하도록 했다.
• 왼쪽 결과 (매번 sum 을 계산) vs 오른쪽 결과 (누적합을 이용) 시 최대 503 ms -> 최대 131 ms 로 줄었다.

매번 sum 을 계산하는 것은 비효율적이다.

 

👇 코드

songda515/SwiftAlgorithm