[스택/큐] 프로그래머스 코딩테스트 문제[기능개발] 알고리즘 공부 - JAVA

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력예시

입출력 예 설명

입출력 예 #1

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.

두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.

세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

문제해결방법

1) progresses와 speeds 정보로 각 작업이 완료되는 데 필요한 일수를 계산하여 ArrayList에 저장합니다.

2) HashMap을 이용하여 각 완료 일수의 빈도를 계산하여 저장합니다.

3) 빈도를 저장한 값을 정렬하여 각 배포마다 몇 개의 기능이 배포되는지 계산합니다.

스택/큐 카테고리에 있는 문제인 만큼 스택/큐를 이용하여 문제를 해결하여야 하나, 알고리즘에 대한 지식이 부족하여 위와 같이 어찌저찌하여 해결은 하였으나

다른사람들의 답안지를 확인하면서 큐를 이용한 풀이법을 확인하였다.

큐사용 시 알아야 할 부분

q.offer(1); //값추가

q.add(1); // 값추가

q.peek(); //첫번째값 참조

q.poll(); //첫번째값 반환

q.remove(); //첫번째 값 제거

q.clear(); //초기화

progresses와 speeds 정보로 각 작업이 완료되는 데 필요한 일수를 계산하여 큐에 저장합니다.

큐의 첫 번째 값보다 큰 값이 나오면, 그동안의 큐의 크기를 저장하고 큐를 초기화합니다.

마지막 남은 큐의 크기를 저장하여 결과 배열에 추가합니다.

내가 푼 풀이는 HashMap과 ArrayList를 사용하여 각 작업이 완료되는 데 필요한 일수를 계산하고, 빈도를 계산하여 해결했습니다.

다른 사람의 풀이에서는 Queue를 사용하여 큐의 첫 번째 값보다 큰 값이 나올 때마다 큐의 크기를 저장하고, 마지막 남은 큐의 크기를 저장하여 해결했습니다.

두 방법 모두 유효하지만, 큐를 이용한 방법이 더 직관적이고 코드가 간결합니다. 이러한 문제를 풀 때는 큐와 같은 자료구조를 잘 활용하는 것이 중요할 것으로 보입니다.

이 포스팅이 도움이 되셨길 바랍니다. 앞으로도 유익한 정보를 제공하기 위해 노력하겠습니다. 읽어주셔서 감사합니다.