(C++) - 백준(BOJ) 14729 : 칠무해

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

14729번: 칠무해

정렬문제였습니다.

📕 풀이방법

📔 입력 및 초기화

n, 학생의 점수 * 1000을 저장할 일차원 배열 counting, cnt를 선언해줍니다. 이후 학생의 점수를 double형으로 입력받은 후 해당 값의 * 1000을 index로해 저장합니다. type casting에 유의해 저장합니다.

📔 풀이과정

1. 시간제한이 1초인 경우 n의 크기가 1천만이므로 counting sort를 사용해야 시간초과가 나지 않습니다.

최소 점수의 학생을 7명 뽑았을 때 for loop를 break해줘야 시간초과가 나지 않습니다.

2. 시간제한이 10초인 경우 O(1천만log1천만) < 10억이므로 단순 std sort함수로 정렬한 뒤 출력해도 됩니다.

 

📔 정답출력

아직 7명이 채워지지 않았고 현재 학생 점수가 counting에 존재한다면 1000으로 나눠 소수점 3자리까지 출력해줍니다.

---

📕 Code

시간 제한이 1초라면 

#include <bits/stdc++.h>
using namespace std;

int counting[100001], n, cnt;

int main(){
    cin >> n;

    for(int i = 0; i < n; i++){
        double score;
        cin >> score;
        counting[(int)(score*1000)]++;
    }

    for(int i = 0; i <= 100000; i++){
        if(!counting[i]) continue;
        if(cnt >= 7) break;
        while(counting[i]-- && cnt++ < 7){
            printf("%.3f\n", (double)i/1000);
        }
    }
}

 

시간 제한이 10초라면

#include <bits/stdc++.h>
using namespace std;
int n;
vector <double> s;
int main(){
    cin >> n;
    s.resize(n);
    for(int i = 0; i < n; i++) cin >> s[i];
    sort(s.begin(), s.end());
    for(int i = 0; i < 7; i++) printf("%.3f\n", s[i]);
}