오늘 하루의 개요
큐... 자료구조 구현한거 노드로 연결하는 구조가 이해가 안가서 거의 대부분을 삽질로 날렸다.
결국 마지막엔 물어봐서 이해함. 독학은 정말 괴롭다.. ㅎ
큐 다음 진도를 tree로 잡고 책을 봤더니
전위 순회(preorder traversal), 중위순회(inorder traversal), 후위순회(postorder traversal) 에서 진입장벽 느낌.. 근데 찾아보니 그렇게 안중요한거고 insertion 될때가 중요하다 함.
그래서 그냥.. 뭔가 모든 것들이 뇌에 들어오는 게 하나도 없었다.
일단 뭐라도 해야하니까 오늘은 편한 길 돌아가서 프로그래머스 문제 풀었다.
오늘 공부 망한 것 같다 ༼⁰o⁰；༽
프로그래머스 모의고사
1단계, javascript 풀이
const solution = (answers) => {
const length = answers.length;
const firstStudent = [1, 2, 3, 4, 5];
const secondStudent = [2, 1, 2, 3, 2, 4, 2, 5];
const thirdStudent = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
const students = [firstStudent, secondStudent, thirdStudent];
const correctCount = (studentAnswer) => {
let count = 0;
const studentAnswerLength = studentAnswer.length
for (let i = 0; i < length; i++) {
const idx = i % studentAnswerLength;
if (studentAnswer[idx] === answers[i]) {
count++;
}
}
return count;
}
const correctCounts = students.map((student) => {
return correctCount(student);
})
// 요소의 모든 항목 찾기
let answer = [];
const maxNumber = Math.max(...correctCounts);
let index = correctCounts.indexOf(maxNumber);
while (index != -1) {
answer.push(index);
index = correctCounts.indexOf(maxNumber, index + 1);
}
return answer.map(x => x + 1).sort((a, b) => a - b);
}
console.log('answer', solution([1, 2, 3, 4, 5, 2]));알고리즘 순서!
1. 정답을 세어주는 함수를 만든다.
이때 배열 수 이상 넘어가는건 % 연산자를 사용해서 다시 반복해준다.
만약 answer 배열과 같다면 count++ 해준다.
2. students 배열에 map 걸어서 해당 학생의 맞힌 문제 개수를 배열에 리턴해준다.
3. spread 연산자를 사용해서 배열 내 최대 값을 구해준다
4. indexOf, while문을 사용해서 answer 배열에 push 해준다
-> indexOf에서 인자가 없을 경우에는 -1을 리턴한다는 점을 이용하면 된다.
괜히 문제 글자 길이 수에 압도되어서 쫄았는데 풀이는 생각보다 쉬웠다.
근데 이거 엄청난 삽질을 했다
거의 2시간을 넘게 질문하기 란에 있는 글 다 읽어보고 반례나 로직에 뭐 문제있나 계속 디버깅 돌리고 멘탈 살짝 터졌는데..
(예제는 다 맞다 뜨는데 제출하기에서는 실패 뜨니까.. )
아 때려치워~ 밥 먹고와서 보니까 설마설마하고 제일 처음 변수선언한 부분이 눈에 딱 들어와서 .. 보니까
실수로 마지막 3번째 학생 배열에서 마지막 인자를 빼먹은거다..
진심 어이없고 웃겨서 얼굴 시뻘개져서 바닥에 엎어져서 oTL 이러고 있었다 정말로...
그래도 해결해서 기분이 좋다..
큐 자료 구조 구현
코드 출처: https://blue-jay.tistory.com/30?category=1175776
백준 10845
이해가 힘들어서.. 물어봤다.
요기 큐 구조도 진짜 처음 끝 노드만 읽을 수 있다는걸 몰랐다.
아 어려워
노드 head - tail로 연결되는 그게 이해가 안갔다
집가서 읽어야지..
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let input = [];
rl.on('line', function (line) {
input.push(line)
})
.on('close', function () {
//console.log(input);
solve();
process.exit();
});
class NodeQueue{
constructor(value){
this.next = null;
this.value = value;
}
}
class Queue{
constructor (){
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(value){
let nodeQueue = new NodeQueue(value);
if(this.size == 0){
this.head = nodeQueue;
}else{
this.tail.next = nodeQueue;
}
this.tail = nodeQueue;
this.size++;
}
dequeue(){
if(this.size== 0){
return null;
}
let value = this.head.value;
this.head = this.head.next;
this.size--;
if(this.size == 0){
this.tail = null;
}
return value;
}
isEmpty(){
return this.size == 0;
}
front(){
if(this.size == 0){
return null;
}
return this.head.value;
}
back(){
if(this.size == 0){
return null;
}
return this.tail.value;
}
getSize(){
return this.size;
}
}
//Array로 구현 pop의 시간복잡도가 O(n)임
class Queue2{
constructor(){
this.q = [];
}
enqueue(value){
this.q.push(value);
}
dequeue(){
if(this.q.length == 0){
return null;
}
return this.q.shift();
}
isEmpty(){
return this.q.length == 0;
}
front(){
if(this.q.length == 0){
return null;
}
return this.q[0];
}
back(){
if(this.q.length == 0){
return null;
}
return this.q[this.q.length - 1];
}
getSize(){
return this.q.length;
}
}
function solve(){
let output = "";
let q = new Queue();
for(let i = 1; i < input.length; i ++){
let line = input[i];
if(line.startsWith("push")){
let spt = line.split(" ");
q.enqueue(spt[1]);
}else if(line.startsWith("pop")){
if(q.isEmpty()){
output += -1 + "\n";
}else{
output += q.dequeue() +"\n";
}
}else if(line.startsWith("front")){
if(q.isEmpty()){
output += -1 + "\n";
}else{
output += q.front() + "\n";
}
}else if(line.startsWith("size")){
output += q.getSize() + "\n";
}else if(line.startsWith("empty")){
if(q.isEmpty())
output+= 1 + "\n";
else{
output+= 0 + "\n";
}
}else if(line.startsWith("back")){
if(q.isEmpty()){
output+= -1 + "\n";
}else{
output+= q.back() + "\n";
}
}
}
console.log(output.trimEnd());
}클래스 구조로 node를 잇는다는게 너무 낯설고 생소해서 이해하는게 힘든 것 같다
그치만 내일의 내가 알아서 이해해주겠지~
영 시간 날리는 것 같고 아니다 싶을 때 여기 보면서 기본 지식들 공부해야지
https://github.com/JaeYeopHan/Interview_Question_for_Beginner
