백준_과일 탕후루_30804, 백준_후보 추천하기_1713

과일 탕후루

문제

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 $S_1$,$S_2$,⋯,$S_N$번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a개, 뒤에서 b개의 과일을 빼면 $S_{a+1}$,$S_{a+2}$,⋯,$S_{N−b}$번 과일, 총 N−(a+b)개가 꽂혀있는 탕후루가 됩니다. (0≤a,b; a+b<N)

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200000)

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 $S_1$,⋯,$S_N$이 공백으로 구분되어 주어집니다. (1≤$S_i$≤9)

출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

예제 입력

5
5 1 1 2 1

예제 출력

4

시간초과의 늪..ㅠ

• 처음에는 집합 Set 이용해서 풀었지만 시간 초과로 실패..
• 그 다음 배열로 start와 end로 slice해서 includes함수와 max와 min 이용해서 풀이했지만 시간 초과로 실패..

⇒ 해시 Map을 이용해서 풀면 시간 초과 해결!

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 과일의 개수
const fruits = input[1].split(' ').map(Number); // 탕후루에 꽂힌 과일

let start = 0;
let end = fruits.findIndex((fruit) => fruits[0] !== fruit); // 맨 처음 과일이랑 다른 과일의 첫 인덱스 찾기

if (end === -1) return console.log(fruits.length); // 종류가 1개인 경우이므로 그대로 과일 수 리턴
let maxCnt = end - start + 1;

const sliceFruits = new Map();
sliceFruits.set(fruits[start], end - start); // start 과일 해시 Map에 넣기
sliceFruits.set(fruits[end], 1); // end 과일 해시 Map에 넣기

end += 1;
while (end < N) {
  // Map에 있는 과일의 종류가 2개이고, 새로운 과일이 추가될 경우
  if (sliceFruits.size === 2 && !sliceFruits.has(fruits[end])) {
    sliceFruits.set(fruits[start], sliceFruits.get(fruits[start]) - 1); // 앞에 있던 과일 하나 제거
    if (sliceFruits.get(fruits[start]) === 0) sliceFruits.delete(fruits[start]); // 해당 과일 개수가 0개가 되면 Map에서 삭제
    start += 1; // 시작점 변경
    continue;
  }
  // Map에 이미 존재하는 과일 종류인 경우
  else if (sliceFruits.has(fruits[end])) {
    sliceFruits.set(fruits[end], sliceFruits.get(fruits[end]) + 1); // 개수 추가
  }
  // 새로운 과일인데 Map에 과일 종류가 1개인 경우
  else {
    sliceFruits.set(fruits[end], 1);
  }
  maxCnt = Math.max(maxCnt, end - start + 1); // 최대 과일의 수 갱신
  end += 1;
}

console.log(maxCnt);

풀이 및 해설

• 탕후루의 과일 종류가 2개 이하면서 개수가 가장 많은 탕후루의 과일 개수 리턴
• 투포인터 이용 + 해시 Map이용

  1. 첫 과일과 다른 종류의 과일이 처음 나오는 인덱스 추출하여 end로 설정

  2. 해시 Map에 첫번째 과일과 end로 나온 과일 넣기

  3. Map에 이미 있는 과일인 경우 해당 과일의 개수 + 1, Map에 없는 새로운 과일이지만, Map에 들어있는 과일 종류가 1개인 경우 새로운 과일 집어 넣기

     ⇒ 이때, max값 업데이트하고, end값 1 증가

  4. Map에 2개의 과일 종류가 들어있는 상황에서 새로운 과일 종류가 들어온 경우

     ⇒ start에 있는 과일 빼고, start값 1 증가

---

후보 추천하기

문제

월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

입력

첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

출력

사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.

예제 입력

3
9
2 1 4 3 5 6 2 7 2

예제 출력

2 6 7

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 사진틀의 개수
const totalRecommendCnt = +input[1]; // 전체 학생의 총 추천 횟수
const recommendList = input[2].split(' ').map(Number); // 추천받은 학생들

const pictures = new Map(); // 사진틀
recommendList.forEach((recommend, idx) => {
  // 이미 존재하는 후보인 경우
  if (pictures.has(recommend)) {
    const [cnt, time] = pictures.get(recommend);
    pictures.set(recommend, [cnt + 1, time]); // 추천 수 + 1
  } else if (pictures.size < N)
    pictures.set(recommend, [1, idx]); // 사진틀이 남아있고, 새로운 후보인 경우
  else {
    // 추천수 오름차순 정렬 || 같다면 시간 기준 오름차순 정렬 후 가장 맨 앞에 오는 값 Map에서 삭제
    const target = [...pictures.entries()].sort(
      (a, b) => a[1][0] - b[1][0] || a[1][1] - b[1][1]
    )[0];
    pictures.delete(target[0]);
    pictures.set(recommend, [1, idx]); // 새로운 후보 등록
  }
});

console.log(...[...pictures.keys()].sort((a, b) => a - b)); // 후보 번호 기준 오름차순 정렬 후 최종 후보 출력

풀이 및 해설

• 최종 후보 구하기
• 사진틀(N) 관리 조건
  • 사진틀에 이미 존재하는 학생인 경우 추천 수 + 1
  • 사진틀에 없는 학생인 경우
    • 사진틀에 공간 남아있는 경우, 추가
    • 사진틀에 공간 없는 경우, 추천이 가장 적은 학생 삭제 후 집어넣기(이때, 추천이 가장 적은 학생이 여러명인 경우 오래된 사진 먼저 삭제)
• Map 이용 ⇒ { 후보학생이름: [추천 수, 게시 시간]}