TIL 29일차

자료구조에 대해 학습했다. 배운 개념을 활용하여 Stack, Queue, Tree, Grap 코플릿 문제를 풀어야한다. 개념은 어떤것인지 알겠는데 알고리즘 문제 푸는것이 어려웠다. 같은 문제를 계속 붙들고 있는데 문득 "내 길이 아닌가"란 생각이 들었다. 또 "내 머리가 나쁘구나" 란 생각도 들었다. 너무 힘이 빠져서 그 코플릿 문제에서 나와서 머리를 식힐겸 section2를 마친 어느분의 회고를 보았는데 "자료구조를 처음 배우던 날, 나의 두뇌를 의심하면서 ‘개발자는 내 길이 아닌 것인가’라는 생각에 머리가 복잡해졌다"는 글을 읽을 수 있었다. "나만 어렵게 느끼고 있는 것이 아니라는 사실을 상기해야 한다."고도 적혀 있었다. 그 분은 어렵지만 잘 해내고 section3으로 넘어가신듯 하다. 나도 좌절하지 말고 이해될때까지, 풀 수 있을때까지 보고 또 보아야 겠다고 다짐했다. 어려웠던 코플릿 문제를 한번 기록해보려고 한다. 

 

1번 문제 [Stack] 구현

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

맴버 변수
데이터를 저장할 Object 타입의 storage
스택의 가장 상단을 가리키는 Number 타입의 포인터 top

메서드
size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다.
push(): 스택에 데이터를 추가할 수 있어야 합니다.
pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다.

주의사항
내장 객체 Array.prototype에 정의된 메서드는 사용하면 안됩니다.
포인터 변수 top의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만 여기서는 0으로 하여 데이터가 추가될 위치를 가리키도록 합니다.

사용 예시
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
...

나의 풀이

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

  // size는 this.top에 채워진 수다.
  size() {
    return this.top
  }

	// 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
  //데이터를 추가할때 가장 상단에 데이터가 추가 된다.
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() <= 0) {
      return;
    }
	
    // 데이터를 추출할때 가장 상단에 있는것이 추출된다.
    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    
    return result;
  }
}

2번 문제 [Queue] 구현

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

맴버 변수
데이터를 저장할 Object 타입의 storage
큐의 가장 앞을 가리키는 Number 타입의 포인터 front
큐의 가장 뒤를 가리키는 Number 타입의 포인터 rear

메서드
size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다.
enqueue(): 큐에 데이터를 추가할 수 있어야 합니다.
dequeue(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다.

주의사항
내장 객체 Array.prototype에 정의된 메서드는 사용하면 안됩니다.
포인터 변수 front, rear의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만 여기서는 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
...

나의 풀이

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return  this.rear - this.front
  }
	
	// 큐에 데이터를 추가 할 수 있어야 합니다.
  enqueue(element) {
  //데이터를 뒤에 추가한다.
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() <= 0) {
      return;
    }
	//데이터의 앞부분이 추출된다.
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

3번 문제 [Stack] 브라우저 뒤로가기 앞으로가기

문제
개발자가 되고 싶은 김코딩은 자료구조를 공부하고 있습니다. 인터넷 브라우저를 통해 스택에 대한 검색을 하면서 다양한 페이지에 접속하게 되었는데 "뒤로 가기", "앞으로 가기"를 반복하면서 여러 페이지를 참고하고 있었습니다.
그런데 새로운 페이지를 접속하게 되면 "앞으로 가기" 버튼이 비활성화돼서 다시 보고 싶던 페이지로 갈 수 없었습니다. 이러기를 반복하다가 김코딩은 스택 자료구조를 떠올리게 되었습니다.

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

조건
새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.
뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고 prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고 next 스택의 top에 있는 페이지로 이동한 뒤 next 스택의 값을 pop 합니다.
브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않습니다.
인터넷 브라우저에서 행동한 순서가 들어있는 배열 actions와 시작 페이지 start가 주어질 때 마지막에 접속해 있는 페이지와 방문했던 페이지들이 담긴 스택을 반환하는 솔루션을 만들어 김코딩의 궁금증을 풀어주세요.

입력
인자 1: actions
String과 Number 타입을 요소로 갖는 브라우저에서 행동한 순서를 차례대로 나열한 배열
인자 2: start
String 타입의 시작 페이지를 나타내는 현재 접속해 있는 대문자 알파벳

출력
Array 타입을 리턴해야 합니다.

주의사항
새로운 페이지 접속은 알파벳 대문자로 표기합니다.
뒤로 가기 버튼을 누른 행동은 -1로 표기합니다.
앞으로 가기 버튼을 누른 행동은 1로 표기합니다.
다음 방문할 페이지는 항상 현재 페이지와 다른 페이지로 접속합니다.
방문한 페이지의 개수는 100개 이하입니다.
반환되는 출력값 배열의 첫 번째 요소 prev 스택, 세 번째 요소 next 스택은 배열입니다. 스택을 사용자 정의한다면 출력에서는 배열로 변환해야 합니다.

입출력 예시
let actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1];
let start = "A";

let output = browserStack(actions, start);
console.log(output); // [["A"], "B", ["A", "D"]]

actions = ["B", -1, "B", "A", "C", -1, -1, "D", -1, 1, "E", -1, -1, 1];
output = browserStack(actions, start);
console.log(output); // [ ["A", "B"], "D", ["E"]]

나의 풀이

function browserStack(actions, start) {
  // actions 행동 start 시작 페이지가 주어진다.
  //마지막에 접속해 있는 페이지와 방문했던 페이지들이 담긴 스택을 반환
  let prev = []
  let next = []
  let cur = start

  for(let i = 0; i < actions.length; i++){
   //페이지가 뒤로 갔을때
   if(actions[i] === -1 && prev.length !== 0 ){
     let pop = prev.pop()
     next.push(cur)
     cur = pop
    //페이지가 앞으로 갔을때
   }else if(actions[i] === 1 && next.length !== 0){
     let pop = next.pop()
     prev.push(cur)
     cur = pop
   }else{
    //새 페이지를 열었을때
     prev.push(cur)
     next = []
     cur = actions[i]
   }
  }
  return [prev, cur, next]
}