아무래도 X됐다.

그것이 부트캠프 3주차에 내가 심사숙고 끝에 내린 결론이다.

🥲
자료구조의 가장 기본적인 형식이라는 Stack, Queue를 배웠다.
역시나 처음 듣는말들이다.
비전공자 살려줘라.

Stack은 '쌓다'와 같은 뜻을 가지고 있다.
그냥 데이터를 순서대로 쌓는 자료구조를 뜻한다.

Queue는 '줄을 서서 기다리다'와 같은 뜻을 가지고 있다.
자동차가 한 줄로 서서 톨게이트를 빠져나가는 형식을 생각하면 된다.

개념은 정말 쉽다.

근데 이것을 코드로 구현하는건 전혀 다른 난이도의 문제다.
오늘도 문제가 주어졌는데 첫번재 문제를 보자마자 생각했다.
"오케이, 난 이거 풀 수 있는 레벨이 아님ㅇㅇ"

👨‍💻
문제를 보는데 어디서 부터 손대야할지 감도 오지 않았다.
하지만
시간안에 오늘 배운 내용들을 건져가야 하기 때문에,
고집부리지 않고 전략적 후퇴가 필요했다.
바로 Reference Code를 켠다.

오늘 하루 중
내 선택이 옳았음을 가장 크게 느꼈을 때가 Reference Code를 빨리 열었을 때다.
(그래도 안보고 풀려는 노력은 했음🙃)


열었더니 역시나, 봐도 모르겠는 문법들과 method들로 가득했다.
항상 느끼는 것이지만 나에게 Coding은 로직이 복잡하다기 보다 사소한 문법, 처음보는 method가 내 발목을 붙잡는다.
이거는 정답이 장기간의 시간을 두고 경험치 쌓는 것 밖에는 없는 것 같다.


아무튼, 오늘 하루 종일은 Reference Code를 보며 이해하는것에 대부분의 시간을 할애했다.
그래도 다행인 점은 한 문제당 몇 시간을 씨름한 끝에 이해가 되었다

💬

다 이해하고 느낀점은,

이런 알고리즘 모델을 뇌속에서 정리한다음 적을 수 있는 사람이 있는건가?

아래는 문제들이다.

📦 박스 포장

마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.

불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.

뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.

만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나가게 됩니다.

이때, 통틀어 최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현해 주세요.

findindex와 splice를 이용하는 방법

function paveBox(boxes) {
    let answer = [];
    
    // boxes 배열이 0보다 클 때까지 반복합니다. 반대로 boxes.length가 0이되면(splice를 통해 배열요소들을 순차적으로 내보내서 모두가 나갔을 때) 반복문을 중단한다.
    while(boxes.length > 0){
        //let finishIndex = boxes.findIndex(fn => boxes[0] < fn);
        let finishIndex = boxes.findIndex(function(el) {
          return boxes[0] < el;
        })
        // (참고)findindex함수는 배열메소드로서 배열의 요소를 순차적으로 순회하면서 조건에 일치하는 요소의 값을 즉시 반환한다. // https://developer-talk.tistory.com/151
        // 위의 작업은 while문을 통해 배열 boxes를 순회하며 첫번째 요소인 boxex[0]보다 뒤에 큰 값들이 있는지 찾는다. findindex를 썼기 때문에 만약 boxes[0]보다 큰 값이 없으면 -1을 반환하고, boxes[0]보다 큰 값이 있으면 그 모든 값들의 배열순서를 반환한다(3번째 값이 boxes[0]보다 크면 2를 반환한다).

        
        if(finishIndex === -1){
            // 만약 boxes[0]뒤에 더 큰 수가 없다면, 한 번에 모든 요소들을 내보낼 수 있다는 말이다(앞에 숫자가 제일 크니까 뒤에 애들은 다 기다렸다가 나감).
            // 그래서 boxes.length(배열요소의 갯수가 한번에 나갈 수 있는 answer가 됨)를 answer에 push하고 그만큼 배열을 내보내준다(splice).
            answer.push(boxes.length);
            boxes.splice(0, boxes.length);

        } else {
            // 만약 찾았다면, 해당 인덱스를 answer에 넣고, boxes에서 그만큼 제외합니다.
            // 만약 찾았다면 한 번에 모든 요소들을 내보낼 수 없다는 뜻이니, 어디까지 짤라서 배열의 요소를 내보내야 할지 결정한다.
            // 그리고 요소를 내보내는 기능을 splice를 통해 구현한다.(첫번째 요소보다 더 큰 요소 앞까지만 내보내면 됨)
            answer.push(finishIndex); // answer(몇명을 한번에 내보낼지 저장하는 곳)에 finishIndex(한번에 몇명을 내보낼지 결정하는 수)를 집어넣는다. 
            boxes.splice(0, finishIndex); // 어디까지 내보낼지 결정한다. 그리고는 다시 while문으로 돌아가 반복을 계속한다.
        }
        // (참고) splice는 배열의 매소드로써 배열에 요소를 추가, 삭제, 교체(추가와 삭제를 같이 진행하면 됨), 추출(제거의 원래와 같음) 할 수 있게 해준다.
        // arr.splice(몇 번째 배열에 무슨짓을 할건지 결정, 위치가 결정되면 기준으로부터 몇개를 제거할지 결정 , 무엇을 추가할건지 결정) 
    }

    // 결과물을 반환합니다.
    return Math.max(...answer);
}

Queue를 이용한 풀이

function paveBox(boxes){
    const queue = [...boxes]; //원본을 직접 변경하지 않기 위해 queue 생성
    const countArr = []; //한번에 나가는 인원을 요소로 갖는 배열
    let count = 1; //첫번째 사람을 포함하므로 1부터 시작, 이 숫자는 한번에 나가는 데이터가 많을수록 커질것임(반복문을 통해)
    
    let cur = queue.shift(); // queue에서 첫번째 요소를 잘라낸게 cur임 
    while(queue.length>0){
      if(cur>=queue[0]){
        count++;
        queue.shift();
      }else{
        countArr.push(count);
        count=1;
        cur = queue.shift();
      }
    }
    countArr.push(count); 
    //while문이 동작할때 cur >= queue 마지막 요소인 경우는 
    //while문이 끝나도 countArr에 count가 들어가지 않기 때문에
    //countArr.push(count)를 꼭 써줘야한다
    return Math.max(...countArr);
  }

인출값 예시

const boxes = [5, 1, 4, 6];
const output = paveBox(boxes);
console.log(output); // 3

const boxes2 = [1, 5, 7, 9];
const output2 = paveBox(boxes2);
console.log(output2); // 1

📡 브라우저 뒤로 가기 앞으로 가기

개발자가 되고 싶은 김코딩은 자료구조를 공부하고 있습니다. 인터넷 브라우저를 통해 스택에 대해 검색을 하면서 다양한 페이지에 접속하게 되었는데 "뒤로 가기", "앞으로 가기"를 반복하면서 여러 페이지를 참고하고 있었습니다.

그런데 새로운 페이지를 접속하게 되면 "앞으로 가기" 버튼이 비활성화돼서 다시 보고 싶던 페이지로 갈 수 없었습니다. 이러기를 반복하다가 김코딩은 스택 자료구조를 떠올리게 되었습니다.

브라우저에서 "뒤로 가기", "앞으로 가기" 기능이 어떻게 구현되는지 궁금해진 김코딩은 몇 가지 조건을 아래와 같이 작성하였지만, 막상 코드를 작성하지 못하고 있습니다.

function browserStack(actions, start) {
  // start 인자가 string이 아닌 것들은 전부 false로 리턴합니다.
  if(typeof start !== 'string') return false;

  // 뒤로 가기와 앞으로 가기 스택의 변수를 설정합니다
  let prevStack = []; // 여기서는 Stack기능하는 storage를 array로 하기로 했다.
  let nextStack = [];
  let current = start;
  
  // actions 배열을 전부 탐색하기 위해 반복문을 설정합니다.
  // 들어가기 전에, 우리는 actions 배열의 요소들을 하나하나 순회하며 분기를 만들어 각 요소들을 처리하는 방식을 만든다.
  // 분기는 총 3가지다. (-1로서 뒤로가기를 하는 경우, 1로서 앞으로가기를 하는 경우, 알파벳으로써 새로운 페이지로 가는 경우) 
  for(let i = 0; i < actions.length; i++) {
    // 만약 actions 배열의 요소가 -1이고(뒤로가기를 눌렀고), prevStack의 길이가 0이 아닐 때(이전으로 돌아가는 페이지가 있다면)
    if(actions[i] === -1 && prevStack.length !== 0) {
      //여기서는 뒤로가기 기능을 구현한다.

      let prevPage = prevStack.pop(); // 1. prevStack에서 pop한것이 prevPage이다.(이름만 지어준 것임)
      nextStack.push(current); // 2. 우선 현재 접속해 있는 current자리를 비워줘야 하니까, nextStack에 currnet를 push해준다.
      current = prevPage; // 3. 자 그럼 이제 current자리가 비었으니(정확하게는 다른 값을 채워도 nextStack에 저장되어 있으니 지워줘도 상관 없음), current자리에 prevPage를 끌어온다.

      // 만약 actions 배열의 요소가 1이고(앞으로가기를 눌렀고), nextStack의 길이가 0이 아닐 때(다음으로 넘어가는 페이지가 있다면)
    } else if(actions[i] === 1 && nextStack.length !== 0) {
      //여기서는 앞으로 가기 기능을 구현한다.

      // nextStack에서 pop한 요소를 nextPage로 할당합니다.
      // prevStack에 current를 삽입합니다.
      // current를 nextPage에 할당합니다.
      let nextPage = nextStack.pop(); // 1. nextStack에서 pop한것이 nextPage이다. (이름만 지어줌)
      prevStack.push(current); // 2. 우선 접속해 있는 current자리를 비워줘야 하니까(currnet페이지를 prevStack로 옮겨 줘야함),  prevStack에 current를 push한다.
      current = nextPage; // 3. 자 이제 current자리에 다른 값을 넣어줘도 prevStack에 이전 페이지 데이터가 잘 저장되어 있으니, current자리에 nextPage를 끌어온다.

      // 만약 actions 배열의 요소가 알파벳이라면 (새로운 페이지라면)
    } else if(typeof actions[i] === 'string') {
      
      prevStack.push(current); // 1. 내가 지금 보고 있는 current를 바로 prevStack으로 이동시킨다. 
      current = actions[i]; // 2. 이제 current에 문자열로 들어온 actions[i]를 끌어온다.
      nextStack = []; // 3. 새로운 페이지를 불러오면 앞이 존재하지 않기 때문에 이전의 nextStack은 비워준다.
    }

    // 이외엔, 동작하지 않습니다.
  }
  
  // 배열에 prevStack, current, nextStack을 순서대로 담아 반환합니다.
  return [prevStack, current, nextStack];
}

인출값 예시

const actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1];
const start = "A";
const output = browserStack(actions, start);

console.log(output); // [["A"], "B", ["A", "D"]]

const actions2 = ["B", -1, "B", "A", "C", -1, -1, "D", -1, 1, "E", -1, -1, 1];
const start2 = "A";
const output2 = browserStack(actions2, start2);

console.log(output2); // [["A", "B"], "D", ["E"]]

🛣 Implementation Queue

Queue 구현을 위한 기본적인 코드가 작성되어 있습니다. Queue 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.

class Queue {
  constructor() { //constructor 매소드를 이용해서 queue의 구조과 값을 선언했다.
    this.storage = {};  //값을 저장할 객체
    this.front = 0; //첫 원소를 가리킬 포인터
    this.rear = 0;  //마지막 원소를 가리킬 포인터
  } //queue를 가장 기본적인 초기값으로 설정했다.
    //여기서 우리는 object에 값을 저장하기로 했고, 두개의 포인터 front, rear를 사용하기로 했다. 

  size() {
    if(this.storage[rear] === undefined) {
      return 0 ;
    }
    return this.rear - this.front + 1;
  } //배열이라면 array.length를 이용해서 길이를 구할 수 있을 것이다. 하지만 이렇게 하면 데이터 처리 시간이 길어진다.
    //우리에겐 포인터가 있음으로 이것을 이용해서 데이터의 길이를 구해본다.
    //근데 여기서 주의할 점은 포인터 front, rear가 같은 지점을 바라보고 있다면 데이터가 1개 남은 경우라는 것을 생각할 필요가 있다.
    //이러한 아이디어를 기반으로 this.storage[rear]가 undefined라면, 아무 데이터가 없는 0을 리턴한다. 그렇지 않다면 정상적으로 size를 구한다.
	
  enqueue(element) {
    if(this.size === 0) {
      this.storage['0'] = value; //['0']으로 키를 설정한 이유는 자바스크립트 객체는 키 값으로 오직 문자열과 symbol만 허용하기 때문임.
    }
    this.rear += 1;
    this.storage[this.rear] = element;
  }
  //만약 queue에 데이터가 삽입된다면, rear포인터가 바라보는 값이 조정될 것이다. 당연히 데이터가 하나씩 들어올 때마다 rear값이 +1된다.
  //근데 삭제할려고 하는데 데이터가 아무것도 없는 경우를 생각해봐야 한다. 경우는 두가지가 있다. 1.초기화된 상태, 2.데이터를 이미 모두 꺼낸 상태(뒤에서 부터)
  //2번을 더 생각해보면, 만약 front와 rear가 같은 위치를 바라보고 있다면 두 포인터를 0번 위치로 재조정 시켜줄 수 있다.(queue는 앞에서부터 데이터가 빠지기 때문에 데이터가 다 삭제되었을 때 front rear가 0이 아닐 수 있다.)
  //그래서 queue에 아무런 데이터가 없을 때(this.size === 0), 0번 위치에 값을 넣고 포인터는 건드리지 않는다.
  //그 외의 경우에는 rear위치를 1만큼 늘리고 해당 위치에 값을 삽입한다.
  

  dequeue() {
    let temp;	// 첫 원소 값을 임시로 담을 변수
    // 두 포인터의 값이 같은 경우 (데이터가 1개 남은 경우)
    // 물론 초기 상태에서 아무런 데이터가 없는 상황일 수도 있으나
    // 이때 front의 값을 가져오고 제거하는 과정에서
    // 자바스크립트 특성 상 에러가 발생하지 않고
    // 두 포인터의 값을 계속 0으로 유지시켜 주기 때문에
    // 별도로 이 부분에 대한 처리를 해줄 필요는 없지만
    // 좀 더 호환성 높은 코드를 위해서는 사실 하는 편을 추천
    if (this.front === this.rear) {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      // 이 부분이 없었다면 이 시점에서 front는
      // rear의 값 보다 1보다 더 큰 역설에 빠지게 되므로
      // 데이터가 없는 경우를 다시 0으로 초기화
      this.front = 0;
      this.rear = 0;
    } else {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
    }
    return temp;
  }
  //데이터를 꺼내는 경우도 추가하는 것(rear + 1)과 마찬가지로 front가 -1 될것이다. 그리고 front의 위치를 재조정 해주기 이전에 값을 제거하는 과정 역시 필요하다.
  //여기 역시 데이터가 존재하지 않는 경우를 생각해야 한다. 이 시점은 데이터가 딱 1개 존재(front와 rear의 값이 동일한 지점)하고 그것을 꺼낸 직후이다.
  //따라서 두 포인터의 값이 동일한 경우에 이것을 초기화 시켜 0을 바라보도록 만든다.
}

인출값 예시

const queue = new Queue();

queue.size(); // 0
for(let i = 1; i < 10; i++) {
  	queue.enqueue(i);
}
queue.dequeue(); // 1
queue.dequeue(); // 2
queue.size(); // 7
queue.enqueue(10);
queue.size(); // 8
queue.dequeue(); // 3
queue.dequeue(); // 4
queue.size(); // 6
...

🪙 Implementation Stack

Stack 구현을 위한 기본적인 코드가 작성되어 있습니다. Stack 자료구조의 특성을 이해하고 FILL_ME_IN을 채워 테스트를 통과해 주세요.

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
  }

  size() {
    return this.top;
  }

	// 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
    this.storage[this.top] = element; //this.top을 key로, 요소를 값으로 하여 storage에 할당
    this.top += 1;
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() <= 0) {
      return; //size가 0이라면 아무 일도 일어나지 않음
    }

    const result = this.storage[this.top - 1]; //여기서 array[this.top - 1] 이 최상단인거임.  
                                              //ex)만약 하나를 넣어서 this.top = 1이면 array[0]이 최상단이 됨.
    delete this.storage[this.top - 1]; //마찬가지로 최상단에 있는 this.storage[0]을 빼줌
    this.top -= 1;  //size를 나타내는 top정보에도 반영이 되어야 하니까 -1해줌
    
    return result;  //이렇게 pop으로 인해 수정된 this.storage를 return함
  }
}

인출값 예시

const stack = new Stack();

stack.size(); // 0
for(let i = 1; i < 10; i++) {
  	stack.push(i);
}
stack.pop(); // 9
stack.pop(); // 8
stack.size(); // 7
stack.push(8);
stack.size(); // 8
...

💬
코드보고 모르는 부분 주석으로 정리했고
로직도 내가 이해하는 방식을 말로 풀어서 설명했다.
점점 주석이 사라지는 날이 오기를 바란다.


래퍼런스 코드 처음 열었을 때
봐도 뭔말인지 몰랐었는데
그래도 이해하니 성취감이 생긴다.
새로운 부트캠프 목표가 생겼는데,
그냥 포기하지 말고 따라가기만 하자🙃