[문제풀이] 백준 1713 - 후보 추천하기

📢 문제

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

📢 알고리즘

구현

📢 풀이

#include <iostream>

using namespace std;

int recommend[101] = {0};
int date[101] = {0};

int main()
{

  int N, M;       // 사진틀 개수, 총 추천 횟수
  int frames = 0; // 사용중인 사진틀 개수
  cin >> N >> M;
  for (int i = 1; i <= M; i++)
  {
    int num;
    cin >> num;

    // 같은 번호가 있다면
    if (recommend[num] > 0)
    {
      recommend[num]++;
      continue;
    }

    // 같은 번호가 없고, 사진틀이 넉넉한 경우
    if (frames < N)
    {
      recommend[num]++;
      date[num] = i;
      frames++;
    }
    else // 같은 번호가 없고, 사용중인 사진틀을 빼야하는 경우
    {
      int minRec = 1001; // 최소추천수
      int minRecIdx;     // 최소추천수 번호
      for (int j = 1; j <= 100; j++)
      {
        if (recommend[j] == 0)
          continue;
        // 추천수 제일 적은
        if (recommend[j] < minRec)
        {
          minRec = recommend[j];
          minRecIdx = j;
        }
        else if (recommend[j] == minRec)
        {
          // 추천수 같으면 게시일 비교
          if (date[j] < date[minRecIdx])
          {
            minRecIdx = j;
          }
        }
      }

      recommend[minRecIdx] = 0;
      date[minRecIdx] = 0;
      recommend[num] = 1;
      date[num] = i;
    }
  }
  for (int i = 1; i <= 100; i++)
  {
    if (date[i] > 0)
      cout << i << " ";
  }
}

• 처음엔 큐를 생각했는데(사진틀에 게시된 사진을 큐에 넣는 방식), 큐에 들어가는 순간 내용물 탐색이 불가능해서 추천수, 게시일 비교등을 못하니 x

• 사진틀 배열을 따로 만들어 사진틀에 게시되는 번호만 배열에 넣고 뺄 생각을 했는데, push_back 연산 등으로 효율이 떨어짐
  👉 배열에 끊임없이 넣다 빼는 연산은 99% 뭔가 잘못된 방향의 풀이

• 사진틀 배열을 굳이 따로 만들어 관리할 필요x. 추천수>0 이면 사진틀에 게시된 것으로 간주

• 같은 번호가 있는지 -> 있으면 추천수++
  없으면, 추천수 제일 적은 것 빼기 -> 최소 추천수가 여러개면 제일 오래된(게시일 최소) 것 빼기

  • 굵은 글씨 부분을 한번의 for문으로 해결할 수 있음!

  • 	if (recommend[j] == 0)
            continue;
          // 추천수 제일 적은
          if (recommend[j] < minRec)
          {
            minRec = recommend[j];
            minRecIdx = j;
          }
          else if (recommend[j] == minRec)
          {
            // 추천수 같으면 게시일 비교
            if (date[j] < date[minRecIdx])
            {
              minRecIdx = j;
            }
          }
        }

• 항상 한글로 로직 써두고 코드로 옮기자

참고
https://mapocodingpark.blogspot.com/2020/02/BOJ-1713.html