[자료구조 - Stack] 브라우저 뒤로가기 앞으로가기

[ 문제 ]

문제를 해석하자면, actions라는 배열과, start라는 문자열을 입력받는다.

* actions : 

- 행동 순서를 나열한 것

- actions의 요소 중, "-1"은 뒤로 가기, "1"은 앞으로 가기, 문자열은 새로운 페이지에 접속하는 것이다.

* start : 시작 페이지

 

[ 풀이 ]

 

-1, 즉 뒤로가기를 하게되면 현재 페이지를 next Stack에 넣고 prev Stack의 제일 위에있는 페이지를 가지고 온다.

--> 여기서 자료구조 중, Stack인 걸 알수 있다. LIFO(Last In First Out)

여기서 prev Stack에 아무 페이지도 담겨있지않다면, 아무런 동작도 일어나지 않는다.

 

1, 즉 앞으로가기를 하게되면 현재 페이지를 prev Stack에 넣고, next Stack 제일 위에 있는 페이지(LIFO)를 가지고 온다.

여기서 next Stack에 아무 페이지도 담겨있지 않다면, 아무런 동작이 일어나지 않는다.

 

새로운 페이지에 접속하게 되면, 현재 페이지는 prev Stack에 넣고, next Stack은 아무 페이지도 없는, 빈 배열이 된다.

 

 

처음 이 문제를 봤을때 솔직히 무슨말인지 이해가 잘 가지 않았다..

그래서 입출력 예시를 보면서 하나하나 적어가며 이해를 했다.

(처음에 잘 이해가 가지 않으면, 이렇게 손으로 하나하나 써보는걸 강력 추천!!)

이 화면을 상상하며 하나하나 적어나갔다.

 

 

function browserStack(actions, start) {

  if(typeof start !== 'string') { //먼저, start의 타입이 string이 아닐 시, false를 반환한다.
    return false;
  }
  let prevStack = []; //이전 페이지를 담아놓는 배열
  let nextStack = []; //다음 페이지를 담아놓는 배열
  let cur = start; //현재 페이지. 초기 페이지는 start이다.
  for(let i = 0; i < actions.length; i++){ //actions배열을 반복문으로 돌린다.
    if(actions[i] === -1 && prevStack.length !== 0){ //만약 '뒤로가기'이고, prev Stack에 이전 페이지가 있다면!
        nextStack.push(cur); //현재 페이지는 next Stack에 넣어준다.
        cur = prevStack.pop(); //그리고 현재 페이지는 prev Stack의 제일 마지막 요소이고, prev Stack에서 그 요소는 제거한다.
      } else if(actions[i] === 1 && nextStack.length !== 0){ //만약 '앞으로가기'이고, next Stack에 다음 페이지가 있다면!
        prevStack.push(cur); //현재 페이지는 prev Stack의 마지막 요소로 추가시키고,
        cur = nextStack.pop(); //next Stack의 마지막 요소는 현재 페이지로 가져오고, 그 요소는 배열에서 제거한다.
      } else if(typeof actions[i] !== 'number'){ //-1,1도 아니라면(즉, 문자열이면)
        nextStack = []; //next Stack은 빈 배열로 만들고, 
        prevStack.push(cur); //현재 페이지는 prev Stack에 마지막 요소로 추가한다.
        cur = actions[i]; //그리고 현재 페이지는 해당 인덱스의 값이 된다.
      }
    }
    let result = []; // 변수 result에 빈 배열을 선언, 할당하여
    result.push(prevStack);
    result.push(cur);
    result.push(nextStack); //차례대로 이전페이지 배열, 현재 페이지, 다음페이지 배열을 넣어준 뒤,
    return result; //result값을 반환한다.
  }

 

내가 이전에 적어놓은 풀이를 보니, 로직은 거의 동일하고 조금씩 다른 코드들이 보인다. 

function browserStack(actions, start) {
 let prev = []; 
 let cur = start;
 let next = [];
  if(typeof start !== 'string') {
    return false;
  }
 for(let i = 0; i < actions.length; i++){
  if(typeof actions[i] === 'string'){
    prev.push(cur);
    next = [];
    cur = actions[i];
  }

  if(actions[i] === -1){
    if(prev.length === 0){ //굳이 이건 적어줄 필요가 없었다..!
      continue;
    } else {
      next.push(cur);
      cur = prev[prev.length-1]; //여기에 그냥 prev.pop()을 넣어줬어도 됐을듯!
      prev.pop();
    }
  }

  if(actions[i] === 1){
    if(next.length === 0){ //안적어줘도 되지만, 직관적이긴 하다!
      continue;
    } else {
      prev.push(cur);
      cur = next[next.length-1];
      next.pop();
    }
  }
}
return [prev, cur, next];
}

 

 

[ 레퍼런스 ]

레퍼런스는 아래와 같다.

나의 로직과 동일하다!

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

  // 뒤로 가기와 앞으로 가기 스택의 변수를 설정합니다
  let prevStack = [];
  let nextStack = [];
  let current = start;
  
  // actions 배열을 전부 탐색하기 위해 반복문을 설정합니다.
  for(let i = 0; i < actions.length; i++) {
    // 만약 actions 배열의 요소가 -1이고(뒤로가기를 눌렀고), prevStack의 길이가 0이 아닐 때(이전으로 돌아가는 페이지가 있다면)
    if(actions[i] === -1 && prevStack.length !== 0) {

      // prevStack에서 pop한 요소를 prevPage로 할당합니다.
      // nextStack에 current를 삽입합니다.
      // current를 prevPage에 할당합니다.
      let prevPage = prevStack.pop();
      nextStack.push(current);
      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();
      prevStack.push(current);
      current = nextPage;

      // 만약 actions 배열의 요소가 알파벳이라면 (새로운 페이지라면)
    } else if(typeof actions[i] === 'string') {
      
      // prevStack에 current를 삽입합니다.
      // current에 현재 알파벳 요소를 할당합니다.
      // 새로운 페이지는 앞으로 갈 수 없기 때문에 nextStack을 비웁니다.
      prevStack.push(current);
      current = actions[i];
      nextStack = [];
    }

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

 

 

**문제의 출처는 '코드스테이츠'입니다.