1. 문제 정보
2. 손코딩
3. 어려웠던 부분
4. 코드
5. 다른 사람의 풀이
6. 어떤 부분이 / 스택/큐 로직과 연결되는지?
1. 문제 정보
1) 출처: https://school.programmers.co.kr/learn/courses/30/lessons/42587
2) 문제 설명
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.
예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.
3) 제한사항
4) 입출력 예
| priorities | location | return |
| [2, 1, 3, 2] | 2 | 1 |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
5) 입출력 예 설명
- 예제 #1
문제에 나온 예와 같습니다.
- 예제 #2
6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.
2. 손코딩
1) 입출력 예1 기준으로 상태 변화
- priorities [2, 1, 3, 2] => stack [{index: 0, value: 2}, {index: 1, value: 1}, {index: 2, value: 3}, {index: 3, value: 2}]
- 1번째 순회: stack [{index: 0, value: 2}, {index: 1, value: 1}, {index: 2, value: 3}, {index: 3, value: 2}] => stack [{index: 1, value: 1}, {index: 2, value: 3}, {index: 3, value: 2}, {index: 0, value: 2}]
- 2번째 순회: stack [{index: 1, value: 1}, {index: 2, value: 3}, {index: 3, value: 2}, {index: 0, value: 2}] => stack [{index: 2, value: 3}, {index: 3, value: 2}, {index: 0, value: 2}, {index: 1, value: 1}]
- 3번째 순회: stack [{index: 2, value: 3}, {index: 3, value: 2}, {index: 0, value: 2}, {index: 1, value: 1}] => stack [{index: 3, value: 2}, {index: 0, value: 2}, {index: 1, value: 1}], result [{index: 2, value: 3}]
- 4번째 순회: stack [{index: 3, value: 2}, {index: 0, value: 2}, {index: 1, value: 1}], result [{index: 2, value: 3}] => stack [{index: 0, value: 2}, {index: 1, value: 1}], result [{index: 2, value: 3}, {index: 3, value: 2}]
- 5번째 순회: stack [{index: 0, value: 2}, {index: 1, value: 1}], result [{index: 2, value: 3}, {index: 3, value: 2}] => stack [{index: 1, value: 1}], result [{index: 2, value: 3}, {index: 3, value: 2}, {index: 0, value: 2}]
- 6번째 순회: stack [{index: 1, value: 1}], result [{index: 2, value: 3}, {index: 3, value: 2}, {index: 0, value: 2}] => stack [], result [{index: 2, value: 3}, {index: 3, value: 2}, {index: 0, value: 2}, {index: 1, value: 1}]
2) 로직
- 1. priorites의 인덱스와 value를 함께 저장할 공간을 위해 const stack = []; 선언하고 빈 배열을 할당한다.
- 2. priorities 의 길이만큼 for 문을 돌면서 {index: xx, value: xx} 와 같은 형태로 데이터를 만들고 stack에 push 한다.
- 3. stack의 첫번째 요소를 꺼내서 firstElement 라는 변수에 할당한다.
- 4. stack의 첫 번째 요소의 value 값보다 큰 value가 있는지 filter 메서드를 이용해서 구하고 리턴된 배열의 length를 isBiggerOne에다가 할당한다.
- 5. isBiggerOne이 0이면( = 첫 번째 요소가 가장 큰 value이다는 말 ) result에다가 해당 요소를 넣는다.
- 6. isBiggerOne이 0이 아니라면( = 첫 번째 요소보다 큰 value를 가진 요소가 있다는 말 ) 첫번째 요소를 stack 리스트의 뒤로 보낸다.
- 7. 3, 4, 5, 6단계를 stack의 length가 0이 될 때까지 반복한다.
- 8. result 배열에서 요소의 value와 priorities배열의 location index에 해당하는 값이 일치하고 && 요소의 index와 location 이 일치하는 인덱스를 찾고 + 1을 해준다.
3) 푼 시간: 2시간 + 약 1시간 10분 경
3. 어려웠던 부분
- priorites[location] 의 값이 2라 가정햇을 때 priorities 배열에는 2라는 값이 여러개 있다. 이런 경우에 다른 인덱스의 값과 혼동하지 않기 위해서 index에 대한 정보를 저장할 필요가 있다고 생각을 했고 2단계에서 data의 형태를 {index: xx, value: xx} 이런 형태로 만들어서 저장했다. 이 단계가 어려웠다.
- 3단계 stack.shift(), 4단계 filter() 메서드로 리턴된 값을 변수에다가 할당하지 않고 바로 문제를 풀려고 했다. 처음 부터 바로 간결하게 푸려고 하지말고 일단은 정석대로 풀자. 필요한 값을 메서드 표현으로 바로 쓰지말고 변수에 할당하는 식으로 하자.
- 3, 4, 5, 6 단계를 반복하기 위해서 while문을 사용하는 것과 while 반복문을 어떤 조건에서 반복시키고 종료시켜야 할지 그 조건문을 쓰는 것이 어려웠다. 나는 주로 for 문의 경우는 특히 배열의 길이만큼 돌고 싶을 때, while문은 조건에 따라서 계속 반복하고 싶을 때 쓰더라. 그러니 무한 루프에 빠질까봐 while 문을 자꾸 배제하지 말고 적절하게 잘 쓰도록 해보자!
4. 코드
function solution(priorities, location) {
const stack = [];
const result = [];
for (let i = 0; i < priorities.length; i++) {
stack.push({index: i, value: priorities[i]});
}
while (stack.length !== 0) {
const firstElement = stack.shift();
const isBiggerOne = stack.filter((el) => el.value > firstElement.value).length;
if (isBiggerOne === 0) {
result.push(firstElement);
} else {
stack.push(firstElement);
}
}
return result.findIndex((el) => el.value === priorities[location] && el.index === location) + 1
}5. 다른 사람의 풀이
function solution(priorities, location) {
var list = priorities.map((t,i)=>({
my : i === location,
val : t
}));
var count = 0;
while(true){
var cur = list.shift();
if(list.some(t=> t.val > cur.val )){
list.push(cur);
}
else{
count++;
if(cur.my) return count;
}
}
}6. 이 문제의 어떤 부분이 스택/큐 문제에 해당하는지?
이번 문제는 Queue 문제라고 볼 수 있다.
- 배열 안의 첫 번째 요소를 탐색하는데
- 첫 번째 요소의 값보다 배열 안에 더 큰 값이 있다면 배열 마지막으로 다시 넣고,
- 첫 번째 요소의 값보다 배열 안에 더 큰 값이 없다면 첫 번째 요소를 배열에서 완전히 빼낸다.
즉 첫 번째 요소를 꺼내고 마지막에 집어넣는 이런 로직이 큐 로 풀 수 있는 것 같다.
'알고리즘' 카테고리의 다른 글
| [프로그래머스] n^2 배열 자르기 (0) | 2023.01.22 |
|---|---|
| [LeetCode] 스택 > 20. Valid Parentheses (0) | 2023.01.17 |
| [프로그래머스] 스택/큐 > 기능개발 문제 (0) | 2022.09.02 |