데브코스 4일차
JS를 기반으로 큐와 해시 테이블, 그래프 등 전반적인 자료구조와 알고리즘에 대해 배웠다.
대부분 알았던 내용이었으나 큐를 직접 class를 이용해서 구현해 본 것은 처음이었다. 추가로 큐를 연결리스트를 이용하여 구현할 수 있다는 것도 처음 알았다.
오늘은 배운 자료구조와 알고리즘을 토대로 코딩테스트 문제를 풀었으므로 문제에 대한 리뷰를 적어보겠다.
프로그래머스 프린터
// 큐
class Queue {
constructor() {
this.queue = [];
this.front = 0;
this.rear = 0;
};
// 큐 삽입
enqueue(value) {
this.queue[this.rear++] = value;
};
// 큐 제거
dequeue() {
let value = this.queue[this.front];
delete this.queue[this.front];
this.front++;
return value;
};
// 큐 리턴
display() {
return this.queue;
};
// 큐 사이즈
size() {
return this.rear - this.front;
};
};
function solution(priorities, location) {
let answer = [];
let queue = new Queue();
// 큐에 넣어주기
priorities.forEach((e, i) => queue.enqueue([e, i]));
// 큰 순서대로 변경
priorities.sort((a, b) => b - a);
let i = 0;
while (queue.size()) {
let process = queue.dequeue(); // [프로세스 중요도, 고유 번호]
if (priorities[i] > process[0]) queue.enqueue(process);
else {
answer.push(process)
i ++;
}
};
// location 실행 순서 확인
for (let k = 0; k < answer.length; k ++) {
if (answer[k][1] === location) return k + 1;
};
};
처음에는 문제에 접근할 때 먼저 priorities의 길이를 변수에 담아준 뒤, 문제에서 요구하는 조건을 반영하여 반복문의 종료 조건을 큐의 길이가 priorities의 길이와 같아지면 종료 되도록 설정하였다.
하지만 종료 조건을 위처럼 설정해보니 반복문 내의 로직이 너무 복잡해지고, 어디서 데이터가 잘못 들어갔는지 히든 테스트케이스 중 3개 정도가 실패가 떴다.
그래서 다시 코드를 지우고,
- 큐에
priorities의 데이터를 넣어주고priorities을 내림차순 정렬한 뒤, i라는 변수를 0으로 선언하여priorities의 맨 첫번째 인덱스를 가리키게 하고,- 큐가 빌때까지 반복문을 통해 프로세스의 중요도를 비교해 전역에 선언한 answer 배열에 넣어 location을 확인하여 답을 추출
답안을 제출하고 히든 케이스를 모두 성공한 다음 강사님의 강의를 보았는데 다시 접근한 코드 설계가 어느정도 강사님의 코드 설계와 비슷해서 조금 뿌듯했다 ㅎㅎ
다시 한 번 느끼는 거지만 아이패드에 정말 꼼꼼하게 설계한 뒤 코드를 작성해야겠다. 코딩테스트 문제 해결 능력이 좋은건 아니지만, 한 동안 코딩테스트 연습을 안했더니 살짝 대충 설계하고 바로 키보드에 손이 올라간다..
다음 문제 프로그래머스 베스트앨범
function solution(genres, plays) {
let answer = [];
let genre = {}
// 장르별 고유 번호별 재생횟수와 총 횟수
genres.forEach((song, i) => {
if (!genre[song]) {
genre[song] = {
[i]: plays[i],
score: plays[i],
}
} else {
genre[song][i] = plays[i];
genre[song].score += plays[i];
}
});
// 총 재생횟수 기준 정렬
const object = Object.entries(genre);
object.sort((a, b) => b[1].score - a[1].score);
// 정렬된 객체 내의 재생횟수로 또 다시 정렬 후 재생횟수가 가장 많은 2가지 고유번호 answer에 push
object.forEach(e => {
let temp = Object.entries(e[1]);
// 재생횟수로 정렬 후 재생횟수가 같다면 고유번호로 정렬
temp.sort((a, b) => b[1] - a[1]);
// 장르에 속한 곡이 하나라면 그 곡 선택해서 push
if (temp.length === 2) answer.push(Number(temp[0][0]));
else {
// 정렬 상태가 맨 앞이 총 재생횟수이므로 index 1번부터 2개 탐색
for (let i = 1; i < 3; i ++) {
answer.push(Number(temp[i][0]));
}
}
});
return answer;
}코드가 생각보다 깔끔하지는 않다..! 우선 문제genres에 들어있는 데이터를 장르를 key로 고유번호 : 재생횟수와 score(총 재생횟수) : 총 재생횟수 로 value를 설정해 주었다.
ex) { classic: {'0': 50, '1': 60, '2': 100, '3': 30, score: 240 }
이후, genre 객체를 정렬해 주기 위해 배열 형태로 형변환을 해 주었고, 총 재생 횟수를 기준으로 내림차순 정렬을 해주었다.
이어서 총 재생 횟수를 기준으로 정렬된 object 변수를 순회하여 한 장르 속에서 재생횟수가 가장 많은 2가이 고유번호를 뽑기 위해 temp에 다시 배열로 형변환하여 넣어주고 재생횟수를 기준으로 오름차순 정렬하여 값을 뽑아주었다(곡이 1개일때 예외 처리도 포함).
느낀점
문제를 풀기전 항상 손으로 완벽하게 설계를 한 뒤에 키보드에 손을 대는 습관을 다시 길러야겠다. 그리고 문제를 풀었다면 다른 사람의 코드를 참고하여 다른 사람의 풀이를 보며 다양한 코드를 익히자(강사님의 풀이 과정을 보면서 너무너무 감탄했다...).
