이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 69 번째 글 입니다.

  • Part 1 - 백준(1003번): 피보나치 함수
  • Part 2 - 백준(1010번): 다리놓기
  • Part 3 - 백준(1012번): 유기농 배추
  • Part 4 - 백준(10159번): 저울
  • Part 5 - 백준(10164번): 격자상의 경로
  • Part 6 - 백준(1018번): 체스판 다시 칠하기
  • Part 7 - 백준(1018번): 체스판 다시 칠하기
  • Part 8 - 백준(1022번): 소용돌이 예쁘게 출력하기
  • Part 9 - 백준(10775번): 공항
  • Part 10 - 백준(10816번): 숫자 카드2
  • Part 11 - 백준(10816번): 숫자카드 2
  • Part 12 - 백준(10819번): 차이를 최대로
  • Part 13 - 백준(10830번): 행렬 곱셈
  • Part 14 - 백준(10844번): 쉬운 계단수
  • Part 15 - 백준(10868번): 최소값
  • Part 16 - 백준(1092번): 배
  • Part 17 - 백준(11003번): 최솟값 찾기
  • Part 18 - 백준(1102번): 발전소
  • Part 19 - 백준(11048번): 이동하기
  • Part 20 - 백준(11053번): 가장 긴 증가하는 부분 수열
  • Part 21 - 백준(11054번): 가장 긴 바이토닉 부분 수열
  • Part 22 - 백준(11055번): 가장 긴 증가하는 부분 수열2
  • Part 23 - 백준(11057번): 오르막 수
  • Part 24 - 백준(1120번): 문자열
  • Part 25 - 백준(11403번): 경로 찾기
  • Part 26 - 백준(11404번): 플루이드
  • Part 27 - 백준(1149번): RGB 거리
  • Part 28 - 백준(11559번): puyo puyo
  • Part 29 - 백준(11655번): ROT13
  • Part 30 - 백준(1167번): 트리의 지름
  • Part 31 - 백준(11722번): 가장 감소하는 부분 수열
  • Part 32 - 백준(12015번): 가장 긴 증가하는 부분 수열(LIS) 2
  • Part 33 - 백준(12851번): 숨바꼭질2
  • Part 34 - 백준(12852번): 1로 만들기 2
  • Part 35 - 백준(12865번): 평범한 배낭
  • Part 36 - 백준(1300번): K번째 수
  • Part 37 - 백준(1325번): 효율적인 해킹
  • Part 38 - 백준(13549번): 숨바꼭질3
  • Part 39 - 백준(13913번): 숨바꼭질4
  • Part 40 - 백준(14002번): 가장 긴 증가하는 부분 수열 4
  • Part 41 - 백준(1431번): 시리얼 넘버
  • Part 42 - 백준(1436번): 영화감독 숌
  • Part 43 - 백준(14499번): 주사위 굴리기
  • Part 44 - 백준(14888번): 연산자 끼워넣기
  • Part 45 - 백준(14889번): 스타트와 링크
  • Part 46 - 백준(14891번): 톱니바퀴
  • Part 47 - 백준(15658번): 연산자 끼워넣기 2
  • Part 48 - 백준(15686번): 치킨 배달
  • Part 49 - 백준(1697번): 숨바꼭질
  • Part 50 - 백준(1697번): 숨바꼭질
  • Part 51 - 백준(1707번): 이분 그래프(Bipartite Graph)
  • Part 52 - 백준(1708번): 볼록 껍질
  • Part 53 - 백준(17136번): 색종이 붙이기
  • Part 54 - 백준(1717번): 집합의 표현
  • Part 55 - 백준(17298번): 오큰수
  • Part 56 - 백준(17626번): Four Squares
  • Part 57 - 백준(18870번): 좌표 압축
  • Part 58 - 백준(1890번): 점프
  • Part 59 - 백준(1918번): 후위 표기식
  • Part 60 - 백준(1929번): 소수 구하기
  • Part 61 - 백준(1963번): 소수 경로
  • Part 62 - 백준(1965번): 상자넣기
  • Part 63 - 백준(1976번): 여행가자
  • Part 64 - 백준(1987번): 알파벳
  • Part 65 - 백준(1992번): 쿼드트리
  • Part 66 - 백준(2003번): 수들의 합2
  • Part 67 - 백준(20040번): 사이클 게임
  • Part 68 - 백준(2042번): 구간 합 구하기
  • Part 69 - This Post
  • Part 70 - 백준(2110번): 공유기 설치
  • Part 71 - 백준(2156번): 포도주 시식
  • Part 72 - 백준(2193번): 이친수
  • Part 73 - 백준(2231번): 분해합
  • Part 74 - 백준(2250번): 트리의 높이와 너비
  • Part 75 - 백준(2293번): 동전 1
  • Part 76 - 백준(2294번): 동전 2
  • Part 77 - 백준(2343번): 기타 레슨
  • Part 78 - 백준(2468번): 안전 영역
  • Part 79 - 백준(2512번): 예산
  • Part 80 - 백준(2529번): 부등호
  • Part 81 - 백준(2565번): 전깃줄
  • Part 82 - 백준(2581번): 소수
  • Part 83 - 백준(2583번): 영역구하기
  • Part 84 - 백준(2630번): 색종이 만들기
  • Part 85 - 백준(2644번): 촌수계산
  • Part 86 - 백준(2667번): 단지번호붙이기
  • Part 87 - 백준(2751번): 수 정렬하기 2
  • Part 88 - 백준(2798번): 블랙잭
  • Part 89 - 백준(2904번): 수학은 너무 쉬워
  • Part 90 - 백준(2986번): 파스칼
  • Part 91 - 백준(3015번): 오아시스 재결합
  • Part 92 - 백준(3190번): 뱀
  • Part 93 - 백준(3190번): 벽 부수고 이동하기
  • Part 94 - 백준(4195번): 친구 네트워크
  • Part 95 - 백준(4948번): 베르트랑 공준
  • Part 96 - 백준(4963번): 섬의 개수
  • Part 97 - 백준(4991번): 로봇 청소기
  • Part 98 - 백준(5373번): 큐빙
  • Part 99 - 백준(5437번): 불
  • Part 100 - 백준(6171번): 땅따먹기
  • Part 101 - 백준(6603번): 로또
  • Part 102 - 백준(6603번): 로또
  • Part 103 - 백준(7562번): 나이트의 이동
  • Part 104 - 백준(7568번): 덩치
  • Part 105 - 백준(7576번): 토마토
  • Part 106 - 백준(7579번): 앱
  • Part 107 - 백준(7785번): 회사에 있는 사람
  • Part 108 - 백준(9012번): 괄호
  • Part 109 - 백준(9020번): 골드바흐의 추측
  • Part 110 - 백준(9184번): 신나는 함수 실행
  • Part 111 - 백준(9251번): LCS
  • Part 112 - 백준(9421번): 소수상근수
  • Part 113 - 프로그래머스: 가장 큰 정사각형 찾기
▼ 목록 보기

목차

▼ 내리기

실버4 : 정렬

생각

최빈값 구할 때, 머리를 좀 써야한다. map구조를 잘 써볼 것. 그리고 정렬하는 방법도 고민해볼 것.

Code

//
//  main.cpp
//  test2
//
//  Created by 최완식 on 2021/03/29.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N = 0;
int input[500001] = {0,};
int temp[500001] = {0,};
int a = 0;
int b = 0;
int c = 0;
int d = 0;


bool comp(const pair<int, int> &p1, const pair<int, int> &p2){
    if (p1.second == p2.second) {
        return p1.first < p2.first;
    }
    return p1.second > p2.second;
}


void merge(int left, int right){
    int mid = int((left+right)/2);
    int i = left, j = mid+1, k = left;
    
    while (i <= mid && j <= right) {
        if (input[i] <= input[j]) {
            temp[k] = input[i];
            i++;
        } else {
            temp[k] = input[j];
            j++;
        }
        k++;
    }
    
    int tmp = (i > mid) ? j : i;
    
    while(k <= right){
        temp[k] = input[tmp];
        k++;
        tmp++;
    }
    
    for (int i = left; i <= right; i++) {
        input[i] = temp[i];
    }
}

void partition(int left, int right){
    if (left >= right) {
        return;
    }
    int mid = int((left+right)/2);
    partition(left, mid);
    partition(mid+1, right);
    merge(left, right);
}



int main(){
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input[i];
        a += input[i];
    }
    a = int(round(float(a)/N)); // 산술 평균
    
    partition(0, N-1); // 정렬
    
    b = input[int(N/2)]; // 중앙값
    
    // 최빈값
    vector<pair<int, int>> st;
    for (int i = 0; i < N; i++) {
        if (st.empty()) {
            st.push_back(pair<int, int>(input[i], 1));
            continue;
        }
        if (st.back().first == input[i]) {
            pair<int, int> tmp = st.back();
            tmp.second++;
            st.pop_back();
            st.push_back(tmp);
        } else {
            st.push_back(pair<int, int>(input[i], 1));
        }
    }
    sort(st.begin(), st.end(), comp);

    if (st[0].second == st[1].second) {
        c = st[1].first;
    } else {
        c = st[0].first;
    }
    
    // 범위
    d = input[N-1] - input[0];
    
    cout << a << '\n';
    cout << b << '\n';
    cout << c << '\n';
    cout << d << '\n';

    return 0;
}

Reference

백준(2108번) - 통계학