[큐]공주 구하기

문제

 

문제풀이

• 1번 왕자부터 8번 왕자까지 한 자리에 모여놓기 위해 각 왕자의 대표되는 번호들을 스택에 순서대로 저장
• 번호가 저장된 스택을 순회하면서 K 차례가 될때마다 해당 인덱스의 요소를 스택에서 삭제
• 만약에 해당 스택을 끝까지 돌았다면 다시 처음으로 회귀하기 위해 임의의 포인터를 인덱스 0으로 초기화
• 위와 같은 연산을 스택의 사이즈가 1(마지막에 남은 왕자)이 될때까지 반복 수행

코드

function solution(n, k) {
  let answer = 0;
  let stack = Array.from({ length: n }, (v, i) => i + 1); 
  let pt = 0; //스택의 인덱스 요소들을 참조하기 위한 임의의 포인터
  let call = 0; //K번째에 해당하는 인덱스 요소를 삭제해주기 위한 참조 변수

  while (stack.length !== 1) { //마지막 하나가 남을 때까지 반복
    call++;
    pt++;
    if (call === 3) { //K번째에 해당할 때
      stack.splice(pt - 1, 1); 
      call = 0; // 다음 왕자부터 다시 1부터 시작하기 위해 0으로 초기화
      pt--; splice()메서드를 사용함으로써 배열 요소들이 하나씩 앞으로 당겨지기 때문에 포인터가 다음 인덱스 요소를 정상적으로 참조하기 위해 1감산
    }
    if (stack[pt - 1] === stack[stack.length - 1]) { //포인터가 스택의 요소를 모두 순회했을 경우
      pt = 0; //다시 앞에서부터 참조해주기 위해 0으로 초기화
    }
  }

  answer = Number(stack.join(""));

  return answer;
}

console.log(solution(8, 3));

 

문제풀이_큐

큐(Queue)

• 큐는 한쪽 끝에서 자료를 추가하고 한쪽 끝에서 자료를 꺼내는 선형 자료 구조
• FIFO(First in First Out)_선입선출 방식

---

• 1번부터 8번까지 저장된 스택을 앞에서부터 차례대로 K번째가 될때까지 빼줌
• K번째 이전까지의 인덱스 요소는 순회 반복을 위해 다시 스택의 뒤에 저장
• K번째에 해당하는 인덱스 요소는 앞에서 그대로 빼서 삭제

코드

function solution(n, k) {
  let answer = 0;
  let queue = Array.from({ length: n }, (v, i) => i + 1);
  
  while(queue.length) {
    for(let i = 1; i < k; i++) queue.push(queue.shift()); //K번째 이전까지는 앞에서 추출하고 이를 다시 뒤에 적재
    queue.shift(); //K번째 일때는 그대로 추출하기만 함
    if(queue.length === 1) answer = queue.shift();
  }

  return answer;
}

console.log(solution(8, 3));