글 읽기 - 틀렸습니다 반례를 못찾겠습니다. 고수님들 도와주세요..!

dbgh9129 2년 전 0

기타 코딩 컨벤션이나 고쳐야 하는 점도 지적 부탁드립니다!!

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string.h>
#include <cmath>
#define MAX 500001

bool comp(std::pair<int32_t,int32_t> &ref1, std::pair<int32_t,int32_t> &ref2)
{
  return (ref1.second > ref2.second) ? true : false;
}

int main()
{
  int32_t N = 0, tmp = 0;
  int32_t max = -4000, min = 4000;

  std::cin >> N;
  std::vector<int32_t> arr(N);

  for(int32_t i = 0; i < N; i++)
  {
    std::cin >> tmp;
    if(tmp > max) max = tmp;
    if(tmp < min) min = tmp;
    arr[i] = tmp;
  }


  /* =====try impelementing the quick sort!!===== */
  std::sort(arr.begin(), arr.end());

  int32_t tot = 0;
  int32_t range = max-min+1;
  std::vector<std::pair<int32_t,int32_t>> cnt(range);
  
  for(int32_t i = 0; i < range; i++) cnt[i].first = i;  /* init for indecies */

  if(min>0)
  {
    for(int32_t i = 0; i < N; i++)
    {
      cnt[arr[i]-min].second++;
      tot += arr[i];
    }
  }
  else
  {
    for(int32_t i = 0; i < N; i++)
    {
      cnt[arr[i]+std::abs(min)].second++;
      tot += arr[i];
    }
  }
  
  std::sort(cnt.begin(), cnt.end(), comp);

  int32_t most_freq = 0;
  std::pair<int32_t,int32_t> prev_freq = cnt[range-1];
  int32_t it = 0;
  if(cnt[it].second == cnt[it+1].second) it++;

  /* print out the solution */
  std::cout << std::round((tot/(double_t)N)) << "\n";      /* arithematic avg */
  std::cout << arr[N/2] << "\n";              /* median */
  if(min>0) std::cout << cnt[it].first+min << "\n";             /* second most frequent */
  else      std::cout << cnt[it].first-std::abs(min) << "\n";   /* second most frequent */
  std::cout << (max-min) << "\n";             /* range */
}

flyjb 2년 전 1

예제 4번이 반례네요.

그리고 40~55 줄이랑 67~68 줄에 min 양수일때랑 음수일때 구분하셨는데,

어짜피 min<=0 일때 -abs(min) = min 이기 때문에 나눌 필요 없어 보입니다.

dbgh9129 2년 전 0

감사합니다!

아래 같이 고쳤는데, 그래도 틀렸다고 나오네요..

여러 예제를 넣어봤는데 고려하지 못한 사항이 있을까요?

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string.h>
#include <cmath>

bool comp(std::pair<int32_t,int32_t> ref1, std::pair<int32_t,int32_t> ref2)
{
  return (ref1.second > ref2.second) ? true : false;
}

int main()
{
  int32_t N = 0, tmp = 0;
  int32_t max = -4000, min = 4000;
  int32_t tot = 0;

  std::cin >> N;
  std::vector<int32_t> arr(N);

  for(int32_t i = 0; i < N; i++)
  {
    std::cin >> tmp;
    if(tmp > max) max = tmp;
    if(tmp < min) min = tmp;
    arr[i] = tmp;
    tot += tmp;
  }

  std::sort(arr.begin(), arr.end());

  int32_t range = max-min+1;
  std::vector<std::pair<int32_t,int32_t>> cnt(range);
  
  for(int32_t i = 0; i < range; i++) cnt[i] = std::pair<int32_t,int32_t>(i,0); 

  for(int32_t i = 0; i < N; i++) cnt[arr[i]-min].second++;
  
  std::sort(cnt.begin(), cnt.end(), comp);

  int32_t it = 0;
  if(cnt[0].second == cnt[1].second) it = 1;

  /* print out the solution */
  int32_t avg = std::round((tot/(double)N));
  std::cout << avg << "\n";      /* arithematic avg */
  std::cout << arr[N/2] << "\n";              /* median */
  std::cout << cnt[it].first+min << "\n";             /* second most frequent */
  std::cout << (max-min) << "\n";             /* range */
}

flyjb 2년 전 1

우선 43번째줄에서 cnt[1]을 확인하는데,

range=1일 경우에는 (입력 숫자가 1종류) 오류가 날 수 있네요.

그리고 40번째 줄에 std::sort 사용하셨는데,

sort는 second값이 같을 때에 원래 순서를 보장해주지 않아서 (= unstable 하다) 문제가 생기네요.

예를 들어서

를 입력하면,

sort 함수를 사용한 뒤에 cnt를 보면

cnt[0].first=1

cnt[1].first=4000

cnt[2].first=0

...

처럼 크기 순대로 정렬이 안될 수도 있습니다.

이런 경우에는 std::stable_sort 함수를 쓰시면 해결될겁니다.

dbgh9129 2년 전 1

정말 감사합니다!

덕분에 해결했어요!^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸습니다 반례를 못찾겠습니다. 고수님들 도와주세요..!

dbgh9129 2년 전 0

flyjb 2년 전 1

dbgh9129 2년 전 0

flyjb 2년 전 1

dbgh9129 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말