[99클럽 코테 스터디 3일차 TIL] Queue + map

📒 Queue

• 선입선출, FIFO 기반의 자료구조이다
• python에서는 list, deque등의 자료구조로 구현이 가능하다
• java에서는 LinkedList를 활용한 Queue로 구현이 가능하다

 

✏️  오늘의 문제 : 기능개발

 

 

📌 의식의 흐름

1. 별다른 알고리즘 없이, naive하게 접근하면 해결될 것 같다.
2. 배포가능날짜(작업 완료 소요기간) 리스트를 구하고, 처음부터 순서대로 만료되는 작업, 그 작업의 배포날짜보다 작은 배포날짜의 작업들은 동시 배포한다.
3. 더 큰 배포날짜의 작업에 대해서는 2의 과정을 반복한다.
4. 남은 진행도와 속도는, 하루 끝 기준으로 판단하기 때문에 (100 - progresses) / speed 의 올림값 리스트를 하나 만들어 순서대로 판단한다.
5. index를 하나씩 밀어가며 배포 날짜 큐를 순회하는 방법, list에서 값을 제거하며 큐를 순회하는 방법, deque에서 값을 제거하며 큐를 순회하는 방법이 있다.
6. index 밀어가는 방법이 제일 간단해 보인다. list에서 값을 제거하는 방법은 list[0]을 빼주는 작업이기에 한번 뺄때 O(n))의 시간복잡도가 소요되고, deque에서 값을 제거하는 방법은 O(1)이기에 두번째보단 세번째가 조금 더 효율적이다.

 

📌 문제점

• 올림의 방법을 제대로 파악하지 못했다.
• queue 순회 방법을 간결하게 작성하지 못했다.

 

📌 해결방법

• math.ceil() 올림, math.round() 반올림, math.floor() 내림
  • ceil은 천장(ceiling), floor는 바닥을 의미하는거로 외우자
• queue는 한번만 순회하며 loop의 기준은 queue.pop (popleft) 이다. 그 안에서 조건을 세우고 비교하자.

 

📌 공부해야 할 것

• zip
• 올림의 효율적인 표현 -((p-100)//s) : 음수에서의 나머지를 버린 나눗셈은 (내림 나눗셈) 양수 기준 절대값과 동일하다