[프로그래머스] 스택 (stack) / 큐 (queue) _ 프린터

2021_08_15 알고리즘 스터디 문제 풀이

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/42587?language=javascript 

코딩테스트 연습 - 프린터

 

문제

 

문제를 파악했을 때 stack의 shift, push 메소드를 통해 문제를 해결할 수 있을 거라는 생각이 들었다.

처음에는 문제를 보고 array map 메소드를 통해 { priority : number; index: number } 객체 형식을 원소로 갖는 배열로 맵핑을 한 후 sort 메소드를 통해 priority를 기준, 내림차순 정렬하고 값을 비교하기 어려운 상태라면 Index가 작은 것을 기준으로 정렬하면 해결이 될 것이라고 생각했는데, 이 문제에서의 요구사항을 간과하고 있었다.

위와 같은 로직으로 정렬을 하게 되면 스택의 shift 메소드로 제거한 원소가 배열의 마지막에 Push 로 추가되는 것이 아닌 그저 index 값으로만 정렬이 되는 것이기 때문에 문제의 요구사항을 충족하지 못하는 문제가 생긴다.

고민을 하다가 외부함수를 사용해 배열의 제일 앞부분보다 높은 우선순위 요소가 있는 지 판별 후 없다면 배열에서 제거, 있다면 제거 후 뒤에 추가하는 로직을 세웠다.

 

수도 코드

// 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
// 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
// 3. 그렇지 않으면 J를 인쇄합니다.

// priorities배열을 map 메소드로 맵핑한다. ex){ priority : priorities[i], index: i}


// 새로운 외부함수를 만든다. 인자로 맨앞의 요소를 비교하고 뒤에 넣은 배열을 리턴하는 함수 ( stack )
  // 배열의 0번째 요소를 찾음
  // 그 요소보다 큰 게 하나라도 있다면, 배열의 0번째 요소를 shift로 없애고 push로 끝에 넣은 후 그 배열을 리턴

// while 문으로 newPrior의 길이만큼 반복문을 수행한다
    // newPrior에 외부함수의 실행값을 할당한다

// newPrior를 (j) 순회하면서 newPrior[i].index가 location과 일치하는 인덱스를 찾아 + 1한 값을 리턴한다

 

 

풀이

function getCheckingStackArray(arr, count, location) {
    const value = arr[0];
    
    // 첫번째 priority를 초과하는 요소가 배열에 하나라도 존재하는 경우 true를 리턴
    const isHigh = arr.some((item) => item.priority > value.priority);
    if (isHigh) {
        // 제일 앞에 있는 요소를 제거하고, 배열의 끝에 추가한다. 
        arr.push(value);  
        arr.shift()
    } else {
        // 더 높은 우선순위가 없다면, 출력이 가능한 상태
        // count의 값을 1 증가시키고, 배열에서 제거한다
        let validPrint = arr.shift()
        count = count + 1;
        
        // 만약, 제거한 원소의 원배열 인덱스가 location과 동일할 경우, isResult의 값을 추가로 리턴하여 감지할 수 있도록 만듦
        if (validPrint.index === location) {
            return {arr, count, isResult: true}
        }
    }
    return {arr, count};
}

function solution(priorities, location) {
    // priorities 원배열의 인덱스를 확인할 수 있도록 객체 형식으로 맵핑한다
    let newPrior = priorities.map((item, index) => {
        return { priority: item, index};
    })
    // 출력된 인쇄물의 갯수
    let count = 0;

    // newPrior의 길이가 0이 될때까지 진행 
    while(newPrior.length > 0) {
        const data = getCheckingStackArray(newPrior, count, location);
        newPrior = data.arr;
        count = data.count;
        
        // data.isResult가 true인 경우 location의 값이 일치하는 원소가 출력된 상태
        if (data.isResult) {
            // 결과 리턴
            return count;
        }

    }
}

 

시간 복잡도 : O(n)의 코드를 구현했다.

isResult로 체크 하는 부분을 꼭 넣어야만 하는 가하는 의문은 있지만 getCheckingStackArray 함수 자체가 arr과 카운트를 리턴하는 역할을 담당하고 있기 때문에 구분할 수 있는 프로퍼티를 추가하는 쪽으로 구현을 했다.