[백준_2531] 회전초밥 ( 투포인터 - 자바스크립트 )

문제

https://www.acmicpc.net/problem/2531

2531번: 회전 초밥

 

 

How to Solve ?

 

문제

 

연속된 K개의 초밥을 고를 때, 주어진 "보너스 초밥 쿠폰이" 있으면 무료, 없으면 "추가 제공"

[ => 연속된 K개의 초밥에 중복과 보너스 초밥이 포함 되지 않으면, 최대 값을 얻을 수 있음 ]

 

 

미션 1- 연속된 4개의 초밥을 고르는 것

 

결과적으로 K개가 포함된 부분 수열을 구하는 것이기에, [ 투포인터 ] 알고리즘을 풀었다. 하지만, 이전과 다른 점이라고 한다면 부분 수열의 길이인 "K"가 사전에 정해져 있다는 점 때문에 배열을 통해서 이를 제한하였다.

 

또한, 회전 초밥의 트랙은 원형으로 되어 있기 때문에  포인터가 길이보다 더 길더라도  중단 하지 않아야 하기에,

만약 초과 됬다면  end 포인터의 위치를 길이로 나누어 다시 앞쪽으로 이동시켜 줘야한다.

 

[ 이해가 안됬다면, 아래의 그림 중 3,4번째 예시를 보면 된다 ! ]

 

   while (sequence.length <= k) {
      sequence.push(lane[end]);
      end === lane_length ? (end = (end % lane_length) + 1) : (end += 1);
    }

 

 

 

 

전체 코드

// 중복을 제거 해주는 함수
function setDuplicate(arr) {
  arr = arr.filter((item, index) => arr.indexOf(item) === index);
  return arr;
}

function solve() {

  let end = 0;
  let max = -Infinity;
  let lane_length = lane.length - 1;
  const sequence = [];
 
  // 투포인터 
  for (let i = 0; i < lane_length; i++) {
    
    // K개까지 연속된 초밥을 Sequence 함수에 담는다.
    while (sequence.length <= k) {
      sequence.push(lane[end]);
      end === lane_length ? (end = (end % lane_length) + 1) : (end += 1);
    }
	
    // 중복된 초밥을 제거
    const removeDup = setDuplicate(sequence);
    let size = removeDup.length;
	
    // 만약에 보너스 초밥이, 선택된 초밥 안에 없으면
    if (removeDup.indexOf(c) === -1) {
      size += 1;
    }

	// 이전보다 더 큰 값이라면, 최대 초밥 개수 초기화
    if (max < size) {
      max = size;
    }
    
	// start 포인터 제거 (= 한 칸 뒤로 이동 ) 
    sequence.shift(); 
  }

  console.log(max);
}

let [n, d, k, c] = [8, 30, 4, 30];
const lane = [7, 9, 7, 30, 2, 7, 9, 25];
solve();

 

ps. 부족한 점이 보인다면, 편하게 댓글 남겨주세요 ! :D