Today Eunji Learned

# [힙][Lv3] 디스크 컨트롤러 - 자바스크립트 js

# 프로그래머스 문제

https://programmers.co.kr/learn/courses/30/lessons/42627?language=javascript (opens new window)

# 시도 1.

length 를 자꾸 lenght 로 써서.. 에러가 났다... 오타때문에 난지도 모르고 이상한 거 수정하다가 시간날림..ㅎㅎ ^^.. 이런 내가 싫다,,,

로직ㅈ ㅏ체는 레벨3치고 쉽다고 생각했음.. 처음에 생각한대로 짰더니 잘 돌아갔다.

  1. 문제에 작업이 요청시간 순으로 들어온다는 말이 없어서 jobs 배열을 정렬했음. 일단 요청시간 순으로 정렬을 하고, 요청시간이 같다면 작업시간이 작은 게 앞에 위치하도록 정렬했다.

  2. 첫 작업이 0ms에 들어온다는 보장이 없으므로 now를 정렬한 jobs의 첫번째 값으로 init.

  3. now보다 같거나 작은 시점에 들어온 작업들을 모두 대기열에 추가해준다. 1번에서 jobs 배열을 정렬했기 때문에 중간에 break 가능!

  4. 3번에서 작업이 추가됐다면 대기열을 작업시간이 작은 순으로 정렬한다.

    이때, isChanged 변수를 활용해 작업이 추가 된 경우만 정렬을 해 불필요한 정렬을 피한다.

  5. 대기열의 첫번째 작업을 수행한다.

  6. 3~5의 작업을 대기열 배열과 jobs 배열이 빌때까지 반복한다.

function solution(jobs) {
    var answer = 0;
    const jobsLength = jobs.length;
    let now = 0;
    let watingJobs = [];
    let isChanged = false;
    
    // order by 요청시간, 작업시간
    jobs.sort((a, b) => {
        if(a[0] === b[0]) return a[1]-b[1];
        return a[0]-b[0];
    });
    
    // 첫 작업이 들어오는 시간으로 초기 값 설정
    now = jobs[0][0];
    
    while( true ){
        // 작업이 남아 있는지 체크
        if (jobs.length === 0 && watingJobs.length === 0) break;
        
        // now 시점에 들어온 작업들 대기 리스트에 추가
        var len = jobs.length;
        isChanged = false;
        for(var i=0; i<len; i++){
            if( jobs[0][0] <= now ){
                watingJobs.push(jobs.shift());
                isChanged = true;
            } else {
                break;
            }
        }
        
        // watingJobs 작업시간순으로 정렬
        if(isChanged) watingJobs.sort((a, b) => a[1]-b[1]);
        
        // 맨 앞 작업 수행
        var job = watingJobs.shift();
        answer += (now-job[0]+job[1]);
        now += job[1];

    }
    
    return Math.floor(answer/jobsLength);
}

제출하니 테스트19번빼고 다 통과했다. 다른 케이스들의 수행시간이 짧은 걸 보니 시간때문에 그런건 아닌 것 같고 뭔가 예외적인 케이스에 내 코드가 에러를 유발하나보다 싶었음.

채점을 시작합니다.
정확성  테스트
테스트 1 〉	통과 (1.04ms, 30.1MB)
테스트 2 〉	통과 (1.22ms, 30.1MB)
테스트 3 〉	통과 (0.82ms, 30MB)
테스트 4 〉	통과 (0.68ms, 30MB)
테스트 5 〉	통과 (1.33ms, 30.1MB)
테스트 6 〉	통과 (0.18ms, 30.1MB)
테스트 7 〉	통과 (0.95ms, 30.2MB)
테스트 8 〉	통과 (0.76ms, 30MB)
테스트 9 〉	통과 (0.42ms, 30MB)
테스트 10 〉	통과 (1.47ms, 30.3MB)
테스트 11 〉	통과 (0.12ms, 30.1MB)
테스트 12 〉	통과 (0.15ms, 30.1MB)
테스트 13 〉	통과 (0.16ms, 30.2MB)
테스트 14 〉	통과 (0.14ms, 30.3MB)
테스트 15 〉	통과 (0.15ms, 30.2MB)
테스트 16 〉	통과 (0.14ms, 30MB)
테스트 17 〉	통과 (0.13ms, 30.1MB)
테스트 18 〉	통과 (0.15ms, 30.1MB)
테스트 19 〉	실패 (런타임 에러)
테스트 20 〉	통과 (0.13ms, 30.1MB)
채점 결과
정확성: 95.0
합계: 95.0 / 100.0

# 시도 2.

테스트19가 에러나는 이유를 찾았다.

작업을 수행 하다가 다음 작업이 들어오는 시간이 now보다 큰 시간이라면 대기열에 추가하지 못해 런타임 에러가 났던 것..!

(ex) [0, 3] [1, 9] [100, 1] 
⇒ 1,2번째 작업을 모두 수행해도 100ms가 아님 
⇒ 대기열이 빈 상태에서 watingJobs.shift() 수행하여 job은 undefined 
⇒ 결국 런타임에러 발생

그래서 // 시간차가 나는 작업만 남았을 때 하단의 if문을 추가해주었다.

function solution(jobs) {
    var answer = 0;
    const jobsLength = jobs.length;
    let now = 0;
    let watingJobs = [];
    let isChanged = false;
    
    // order by 요청시간, 작업시간
    jobs.sort((a, b) => {
        if(a[0] === b[0]) return a[1]-b[1];
        return a[0]-b[0];
    });
    
    // 첫 작업이 들어오는 시간으로 초기 값 설정
    now = jobs[0][0];
    
    while( true ){
        // 작업이 남아 있는지 체크
        if (jobs.length === 0 && watingJobs.length === 0) break;
        
        // now 시점에 들어온 작업들 대기 리스트에 추가
        var len = jobs.length;
        isChanged = false;
        for(var i=0; i<len; i++){
            if( jobs[0][0] <= now ){
                watingJobs.push(jobs.shift());
                isChanged = true;
            } else {
                break;
            }
        }
        
        // watingJobs 작업시간순으로 정렬
        if(isChanged) watingJobs.sort((a, b) => a[1]-b[1]);
        
        // 시간차가 나는 작업만 남았을 때
        if( jobs.length !== 0 && watingJobs.length === 0 ){
            var job = jobs.shift();
            watingJobs.push(job);
            now = job[0];
        }
        
        // 맨 앞 작업 수행
        var job = watingJobs.shift();
        answer += (now-job[0]+job[1]);
        now += job[1];
        
    }
    
    return Math.floor(answer/jobsLength);
}

채점을 시작합니다.
정확성  테스트
테스트 1 〉	통과 (1.11ms, 30.2MB)
테스트 2 〉	통과 (1.18ms, 30MB)
테스트 3 〉	통과 (1.10ms, 30MB)
테스트 4 〉	통과 (0.70ms, 29.8MB)
테스트 5 〉	통과 (1.17ms, 30.1MB)
테스트 6 〉	통과 (0.23ms, 29.9MB)
테스트 7 〉	통과 (1.05ms, 30.1MB)
테스트 8 〉	통과 (0.80ms, 29.9MB)
테스트 9 〉	통과 (0.24ms, 30.2MB)
테스트 10 〉	통과 (1.39ms, 30MB)
테스트 11 〉	통과 (0.16ms, 30MB)
테스트 12 〉	통과 (0.17ms, 30MB)
테스트 13 〉	통과 (0.17ms, 30.1MB)
테스트 14 〉	통과 (0.15ms, 29.8MB)
테스트 15 〉	통과 (0.15ms, 29.9MB)
테스트 16 〉	통과 (0.16ms, 30MB)
테스트 17 〉	통과 (0.13ms, 29.9MB)
테스트 18 〉	통과 (0.17ms, 30MB)
테스트 19 〉	통과 (0.16ms, 29.9MB)
테스트 20 〉	통과 (0.13ms, 30.2MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

성공적~~ 근데 문제가 힙으로 분류 되어있음에도 나는 힙이라는 자료구조의 특성(부모노드..자식노드.. 부분정렬등등..)을 사용하지 않고 문제를 해결한 느낌이다...

그리고 시간차가 많이 나는 작업을 처음부터 고려했다면 더 깔끔하게 짤 수 있지 않았을까 싶음

# 다른 사람 답변 통해 배워보기

로직은 아니고, 마지막 Math.floor(answer/jobsLength); 을 ~~(total / len) 이렇게 쓰신 분이 계셔서 물결연산자는 뭐지? 하고 찾아봤다!

  • ~ 연산자 : 비트연산자, NOT. 2진수일때 0과 1을 바꾼 값을 보여준다.
  • ~~ 연산자 : ~ 연산을 두번한다.

    1. Math.floor() 대신 사용가능 : ~ 연산을 하면 소수점들이 버려지게 되기 때문이다. 속도는 ~~가 제일 빠르지만 가독성 차원에서 좋지 않다.

    2. undefined 또는 null을 0으로 변환할 때 사용 ⇒ 사실 이게 더 흥미로웠음..!!

      const arr = [1,1,1,2,2,3,3,3,3]
const obj1 = {}

arr.forEach(v=>{
  if(obj1[v]) obj1[v]+=1
  else obj1[v]=1
})
//obj1 {1: 3, 2: 2, 3: 4}

이 코드를 다음처럼 쓸 수 있다

const obj2 = {}
arr.forEach(v=>obj2[v]= ~~obj2[v]+1)
//obj2 {1: 3, 2: 2, 3: 4}

출처

https://stackoverflow.com/questions/4055633/what-does-double-tilde-do-in-javascript (opens new window)

https://velog.io/@proshy/JS-tilde과-double-tilde연산자 (opens new window)

Last Updated: 8/11/2022, 5:17:02 AM

← [힙][Lv3] 이중우선순위큐 - 자바스크립트 js →