9088. 다이아몬드

링크

난이도 : d4
정답률 : _41%

설계

자료구조

다이아몬드 무게의 범위가 1 ~ 10,000 이므로 10001 크기의 배열을 선언한다.

알고리즘

다이아몬드 무게 입력시 무게를 index로 하는 배열의 count를 증가시킨다.

배열을 순회하며 현재 inex ~ 현재 inex + K 까지의 수를 count하며 max를 갱신한다.

정리

내 코드	빠른 코드
29 ms	6 ms

고생한 점

문제의 이해가 어려웠다.

처음엔 다이아몬드 쌍을 구하는 줄 알고, 정답이 모두 짝수로 나오는 경우로 생각함.

그것이 아닌 묶음이므로 한정된 범위 내의 다이아몬드의 최대 갯수를 구하는 문제였다.

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void solution(int test_case) {
  int answer = 0, N, K, temp, MAX = 0, MIN = 10000;
  int dias[10001] = {
      0,
  };

  cin >> N >> K;

  for (int i = 0; i < N; i++) {
    cin >> temp;
    dias[temp] += 1;
    MAX = max(MAX, temp);
    MIN = min(MIN, temp);
  }

  for (int i = MIN; i <= MAX; i++) {
    if (dias[i] == 0) {
      continue;
    }
    temp = 0;
    for (int j = i; j <= min(MAX, i + K); j++) {
      temp += dias[j];
    }
    answer = max(answer, temp);
  }

  cout << "#" << test_case << " " << answer << "\n";
}

int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  cin >> T;

  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }

  return 0;
}