https://programmers.co.kr/learn/courses/30/lessons/42587
코딩테스트 연습 - 프린터
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린
programmers.co.kr
문제 설명
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
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 함수를 작성해주세요.
접근방법
으으음.....
으으으으음.....
stack/queue문제니까..
매개변수를 변경하지 않기 위해 똑같은 배열을 slice로 만들고
count선언한 뒤, 1을 할당해주고
배열 안에서 제일 큰 수를 구한 다음에
배열의 0번째 값와 비교해서
큰수가 더 크면
shift로 제거하고 그걸 push로 뒤로 보내고
일치하면 인쇄하고.
그게 priorities[location] 과 일치하면 리턴 하고
일치하지 않으면 카운트를 1씩 늘려주고 shift로 제거 하면 되지 않을까..?
function solution(priorities, location) {
const waitingRoom = priorities.slice();
let count = 1;
let mostImportant = Math.max.apply(null, priorities);
while (true) {
console.log(waitingRoom, mostImportant);
if (
priorities[location] === waitingRoom[0] &&
mostImportant === waitingRoom[0]
) {
break;
}
if (mostImportant > waitingRoom[0]) {
waitingRoom.push(waitingRoom.shift());
continue;
}
if (mostImportant === waitingRoom[0]) {
count += 1;
waitingRoom.shift();
mostImportant = Math.max.apply(null, waitingRoom);
}
}
return count;
}
const test = [2, 1, 3, 2, 3];
console.log(solution(test, 4)); // 1
생각한대로 코드를 짜고 돌려봤는데,
밑에 케이스를 걸러내질 못한다.
prioritiese[2] 의 값도 3이고 prioritiese[4]의 값도 3이라서,
2의 3이 맨 앞으로 나오게 되면 priorities[4] 와 일치하는 값이라
리턴을 해버린다.
곤란하다.
한 30분은 혼자 더 고민을 해봤는데 아무리 생각해도 모르겠다.
우리집 시니어 한테 힌트좀 달라 그랬다.
priorities의 값들을 인덱스를 포함한 객체나 배열로 만들어서 해보란다.
호옹....
maps를 이용해서 prioritiese의 value와 index를 value로 갖는 배열을 value로 갖는 배열을 만들었다.
와 라임 지려따리;;
그니까 위 코드의 test인 [2, 1, 3, 2, 3] 을
[[2, 0], [1,1], [3,2], [2,3], [3,4]]
로 만드는 거지
치면서 개헷갈려서 계속 틀림 ㅎ;;
function solution(priorities, location) {
const waitingRoom = priorities.map((v, i) => [v, i]);
let count = 1;
let mostImportant = Math.max.apply(null, priorities);
while (true) {
console.log(waitingRoom, mostImportant);
if (location === waitingRoom[0][1] && mostImportant === waitingRoom[0][0]) {
break;
}
if (mostImportant > waitingRoom[0][0]) {
waitingRoom.push(waitingRoom.shift());
continue;
}
if (mostImportant === waitingRoom[0][0]) {
count += 1;
waitingRoom.shift();
mostImportant = Math.max.apply(
null,
waitingRoom.map((v) => v[0]),
);
}
}
return count;
}
const test = [2, 1, 3, 2, 3];
console.log(solution(test, 4)); // 2코드 마지막에 mostImportant를 변경해주는 코드에서 v[0] 으로 배열을 만들어서 그중에서 제일 큰수를 뽑아냈다.
이렇게 하니까 잘 돌아감
아 중간에 console.log는 코드 어떻게 돌아가나 확인해본거임;
그리고 Math.max.apply대신에
spread 연산자 써도 된당...
function solution(priorities, location) {
const waitingRoom = priorities.map((v, i) => [v, i]);
let count = 1;
let mostImportant = Math.max.(...priorities);
while (true) {
console.log(waitingRoom, mostImportant);
if (location === waitingRoom[0][1] && mostImportant === waitingRoom[0][0]) {
break;
}
if (mostImportant > waitingRoom[0][0]) {
waitingRoom.push(waitingRoom.shift());
continue;
}
if (mostImportant === waitingRoom[0][0]) {
count += 1;
waitingRoom.shift();
mostImportant = Math.max(...waitingRoom.map((v) => v[0]);
}
}
return count;
}
const test = [2, 1, 3, 2, 3];
console.log(solution(test, 4)); // 2이렇게.
복잡한가..?
나름 괜찮은 거 같은데...
다른사람 답을 한번 볼까
function solution(priorities, location) {
const list = priorities.map((value, index) => ({
target: index === location,
val: value,
}));
let count = 0;
while (true) {
const cur = list.splice(0, 1)[0];
if (list.some((t) => t.val > cur.val)) {
list.push(cur);
continue;
}
if (list.some((t) => t.val <= cur.val)) {
count += 1;
if (cur.target) return count;
}
}
}
const test = [2, 1, 3, 2, 3];
console.log(solution(test, 4));
이 코드는 배열이 아니라 객체를 이용했고,
나처럼 제일 큰 값과 비교를 한게 아니라,
맨 앞에 있는 값 뽑아서,
그거랑 나머지 값들을 비교해서
하나라도 큰게 있으면
뽑은 값을 다시 뒤로 보낸다.
그리고 뽑은 값이 나머지 값들보다 크거나 같으면
카운트에 1을 추가하고,
location 과 index가 일치하는지 확인하고
일치하면 count를 리턴하고
일치하지 않으면 다시 반복.
음 얼추 비슷한가...?
원래 나와있던 코드는 이거랑은 조금 달랐는데,
var를 let이나 const로 변경했고,
객체의 프로퍼티 도 조금더 명확하게 변경했다.
else 도
if 문 안에 continue를 넣어서
한줄 더 띄어서 조금 더 보기 편하게 바꿨더니
전체적인 느낌은 비슷한듯..?
근데 우리집 시니어가 객체를 이용해서 하는 것과
배열을 이용해서 하는 것이 차이가 있다했는데
시간복잡도다.
배열을 이용해서 하는게 시간복잡도가 낮다고 한다.
그래서 왼쪽의 결과가 내가 짠 코드고
오른쪽의 결과가 남의 코든데
ㅎ 내가이김 헿;
내가 더 잘한거 아닐까..?
댓글