99클럽 코테 스터디 3일차 TIL - 스택/큐

오늘의 학습 키워드

스택

---

알고리즘 문제

• 프로그래머스 Level 2 - 기능개발
• https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

 

---

공부한 내용

List To Array

• Stream을 이용한 리스트 -> 배열로 형변환 문법

List<Integer> list = new ArrayList<>();
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
//int[] arr = list.stream().mapToInt(i -> i).toArray();

 

---

오늘의 회고

처음 시도

• 변수 progresses와 speeds는 % 단위여서 100을 기준으로 배포 날짜를 계산해야겠다고 생각했다.
• 반복문과 ArrayList를 활용해서 한 번에 배포되는 작업 개수를 카운트했다.

해결

• 처음에 실수로 배포 날짜를 나머지가 있으면 값+나머지, 없으면 값으로 해서 계산을 잘못했었고, 배포 날짜를 출력해서 디버깅해보고 배포 날짜 계산식을 바꿨다.
  • 수정한 배포 날짜 계산식  : 나머지가 있으면 값+1 해주고, 없으면 그대로 값으로 한다.
  • (100 - progresses[0]) / speeds[0] => 7 / 1 = 7 ... 0 => 7
  • (100 - progresses[1]) / speeds[1] => 70 / 30 = 2 ... 10 => 2 + 1 = 3
  • (100 - progresses[2]) / speeds[2] => 45 / 5 = 9 ... 0 => 9
• 반복문을 돌면서, 마지막 작업에 이후에 배포 결과를 반영이 되지 않아서 현재 작업 배열의 인덱스가 마지막 요소라면 배포 결과를 반영해주는 로직을 추가했다.
  • if (i == progresses.length - 1) { // 함께 배포 카운트 반영하는 로직 }: i는 현재 작업 배열의 인덱스

---

문제 풀이

ArrayList

• ArrayList 사용 이유: 작업 배열의 앞에서부터 순서대로 카운트를 세어서, 단순히 하루에 배포할 개수를 쌓아서 반환해야하기 때문에 시간복잡도가 O(1)로 빠르고, 마지막에 배열로 변환해주면 되기 때문에 편하다고 생각했다.
• 시간복잡도
  • 중간에 추가하지 않고 맨 마지막에 요소를 추가하는 경우 시간복잡도가 O(1)이다.
  • 중간 인덱스에 값을 추가하는 경우 시간복잡도가 O(n)이다. 해당 인덱스 뒤에 있는 요소들을 오른쪽으로 한 칸씩 옮겨서 추가할 공간을 만들어야 하기 때문이다.

계산

1. 변수 progresses와 speeds는 % 단위여서 100을 기준으로 배포 날짜를 계산해야겠다고 생각했다.
2. 입출력 예시 첫번째를 보고 100에서 각 progresses를 빼서 남은 작업량을 계산해봤다. 
   • 100 - progresses[0] => 100-93 = 7
   • 100 -  progresses[1] =>  100-30 = 70
   • 100 -  progresses[2] =>  100-55 = 45
3. speeds는 개발 속도이므로 남은 작업량을 나눠서 배포 날짜를 계산해봤다.
4. 변수 max에 초기값으로 처음 작업 배포 날짜를 정한다. 변수 max로 작업 배열 길이만큼 반복문을 돌면서, 배포 날짜와 비교하기 위해서 정했다.
5. loop를 돌며, 현재 계산된 배포 날짜와 max를 비교해서 새로운 max를 정하거나, 한 번에 배포할 카운트를 센다.
   • max보다 작거나 같으면 => 이전 작업보다 배포 날짜가 작거나 같다 => 이전 작업과 함께 배포된다. (카운트+1)
   • max보다 크면 => 이전 작업보다 배포 날짜가 크다 => 새로 배포를 해야한다. (카운트를 1 초기화)

github 풀이

Algorithm-Practice/프로그래머스/2/42586. 기능개발 at main · dev-jinius/Algorithm-Practice

 

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer;
		
        int max = 0;		//현재 작업 이전까지 최대 배포 날짜
        int count = 0;		//한 번에 배포할 작업 개수
        int deploy = 0;		//현재 작업 배포 날짜
       	List<Integer> counts = new ArrayList<>();	// 배포할 작업 개수 리스트
        
        for (int i = 0; i < progresses.length; i++) {
        	// 계산된 현재 작업 배포 날짜
            deploy = (100-progresses[i])%speeds[i]==0 ? (100-progresses[i])/speeds[i] : (100-progresses[i])/speeds[i] + 1;  
            
            // 작업 배열의 첫번째 요소라면 비교 max값이 없으므로 배포 날짜를 max로 초기화
            if (max == 0) {
                max = deploy;
            }
            
            // max와 현재 작업 배포날짜 비교해서 카운트 계산
            if (deploy <= max) {
                count += 1;
            } else {
                counts.add(count);  
                max = deploy;
                count = 1;
            }
            
            // 마지막 작업이라면 계산된 배포 작업 개수를 반영해야 한다.
            if (i == progresses.length - 1) {
                counts.add(count);
                break;
            }
        }
        
        answer = counts.stream().mapToInt(Integer::intValue).toArray();	//List to Array
        
        return answer;
    }
}

 

다른 풀이

Array

import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] dayOfend = new int[100];
        int day = -1;
        for(int i=0; i<progresses.length; i++) {
            while(progresses[i] + (day*speeds[i]) < 100) {
                day++;
            }
            dayOfend[day]++;
        }
        return Arrays.stream(dayOfend).filter(i -> i!=0).toArray();
    }
}