developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테기출자바풀이
  • c++디자인패턴
  • 삼성코테자바준비
  • c++ 빌더 패턴
  • 삼성코테파이썬
  • 통계학
  • Arima
  • 삼성코테구현문제추천
  • 시계열분석
  • 삼성코테준비
  • 운영체제인터럽트
  • 시계열
  • 삼성코테기출
  • 카카오코테
  • 삼성코테자바꿀팁
  • BOJ파이썬풀이
  • 백준파이썬풀이
  • 삼성코테자바풀이
  • 삼성코테파이썬풀이
  • 카카오코테java풀이
  • AR모형
  • 통계분석
  • SW역량테스트파이썬풀이
  • 삼성코테구현풀이
  • MA모형
  • 데이터분석
  • ARIMA모형
  • SW역량테스트파이썬
  • 삼성코테파이썬준비
  • 코테파이썬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

프로그래머스 코딩테스트 연습 - 디스크컨트롤러 (JAVA)
알고리즘/알고리즘문풀

프로그래머스 코딩테스트 연습 - 디스크컨트롤러 (JAVA)

2022. 10. 30. 14:24

❓ 문제 - 프로그래머스 코딩테스트 연습 디스크컨트롤러- JAVA 풀이법

출처

(https://school.programmers.co.kr/learn/courses/30/lessons/42627)

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

 

📝 문제해결법

1. 문제

  • 디스크 작업 처리 요청이 (요청시점, 소요되는 시간)을 배열 형태로 주어질 때 한 시점에는 하나의 작업만 수행할 수 있어서 전체 작업을 처리하는 평균의 최소값을 반환해야 합니다.
  • 한 작업이 걸리는 시간은 (한 작업을 수행하기 까지 기다리는 시간 + 그 작업이 소요되는 시간)으로 계산됩니다.

 

2. 해결 방법

  • 자바 내에서 우선순위 큐와 배열의 오름차순 정렬을 활용해서 문제를 해결할 수 있습니다.
  • 우선 jobs의 배열을 일이 요청되는 시점을 기준으로 오름차순 정렬을 하고 우선순위 큐에 들어가는 데이터들은 일이 소요되는 시간을 기준으로 최소힙을 구성해줍니다.
  • 일이 끝나는 시점인 end와 현재 몇 개의 디스크를 처리했는지를 cnt로 세어주고, idx로 현재 처리할 수 있는 작업의 인덱스를 가리키도록 해줍니다.
  • 정렬된 jobs배열을 기준으로 현재 작업 완료된 시점(end) 기준으로 작업이 요청이 이미 와있는 것들을 모두 우선순위 큐에 넣어줍니다.
  • 만약 우선순위 큐에 아무런 값이 들어가 있지 않다면 처리할 수 있는 작업이 없기 때문에, 현재 시점을 기준으로는 아직 요청이 들어오지 않았지만 바로 다음에 처리할 작업 요청 시간을 end로 바꿔줍니다.
  • 만약 우선순위 큐에 값이 들어가 있다면 하나를 꺼내면 현재시점을 기준으로 가장 작업이 적게 걸리는 것이며, answer에 그 작업을 소요하는데 걸리는 시간 + (현재시점을 기준으로 처리되기까지 작업이 기다린 시간)을 더해줍니다.
  • 그리고 현재 시점을 이 작업이 소요하는데 걸리는 시간으로 더해주고 처리한 cnt의 값을 1증가시켜줍니다.

 

 

 

3. 느낀점

  • 처음에 백트래킹이나 완전탐색으로 구해야 하는 건가 생각했는데 jobs의 크기가 최대 500이고, 우선순위 큐를 사용한다면 탐색없이 할 수 있다라고 생각해서 구현을 시작했다.
  • 나는 현재까지 기다린 시간 + 작업처리 시간을 기준으로 최소힙을 만들어서 구현을 했는데.. 이런 식으로 하면 현재시점을 기준으로 처리되지 않기 때문에 계속 고민하다가 다른사람의 풀이를 참고했다.
  • 문제의 핵심은 우선순위 큐를 이용하면서, 시점을 기준으로 큐에 넣고, 일을 처리하고의 핵심 로직이 들어야한다라는 걸 빠르게 캐치했다.

 

💻 소스코드 (JAVA)

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int end = 0;
        int idx = 0;
        int cnt = 0;
        
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        
        while(cnt < jobs.length){
            while(idx < jobs.length && jobs[idx][0] <= end){
                pq.add(jobs[idx++]);
            }
            
            if(pq.isEmpty()){
                end = jobs[idx][0];
            } else {
                int[] array = pq.poll();
                answer += (array[1] + end - array[0]);
                end += array[1];
                cnt++;
            }
        }
        
        return answer / jobs.length;
    }
}

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)  (0) 2022.11.29
프로그래머스 코딩테스트 연습 - 카펫 (JAVA)  (0) 2022.11.22
2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기 (JAVA)  (0) 2022.10.23
코드 트리 - 나무 박멸(46번)  (0) 2022.10.09
코드 트리 - 예술성(45번)  (0) 2022.10.09
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • 프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)
    • 프로그래머스 코딩테스트 연습 - 카펫 (JAVA)
    • 2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기 (JAVA)
    • 코드 트리 - 나무 박멸(46번)
    developer-ellen
    developer-ellen

    티스토리툴바