2024 - 11- 14 C++ 코딩테스트 10주완성 D+62

그리다 알고리즘 실습문제 - 큰돌 교수님의 과제는 너무 어려워!!!

 

큰돌 교수님은 데이터 분석 과목을 담당하고 있으며, 학생들의 성적 분석을 과제로 내주었습니다.

 

교수님은 과제에서 최하위 성적을 받은 7명의 학생에게 추가적인 지도를 해주기로 결정했습니다.

 

이들 중 성적이 좋지 않은 7명을 선발하여 따로 지도를 해주려 합니다.

 

교수님을 돕기 위해 학생들의 최종 성적이 주어질 때, 성적이 좋지 않은 5명의 학생을 선택하여

 

성적이 낮은 순서대로 출력하는 프로그램을 작성하세요.

 

입력

 

첫째 줄에 학생의 수 N이 주어집니다.(6 <= n <= 50,000,000)

둘째 줄부터 N개의 줄에는 학생들의 성적이 무작위로 주어진다.
(성적은 최소 0점부터 최대 100점까지 0.001점 단위로 부여된다.)

출력

 

하위 7명의 성적을 점수가 낮은 순으로 각 줄마다 출력한다.

하위 7명의 성적 커트 라인에 동점자가 있을 경우에도 7명만 출력하면 된다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

int n;
double temp;
priority_queue<double> qd;
vector<double> v;

int main()
{
    scanf("%d", &n);

    

    for(int i=0; i < n; i++)
    {
        scanf("%lf", &temp);
        
        if(qd.size() == 7)
        {
            qd.push(temp); qd.pop();
        }     
        else qd.push(temp);
    }   

    while(qd.size())
    {
        v.push_back(qd.top()); qd.pop();
    }
    reverse(v.begin(),v.end());
    for(double i : v) printf("%.3lf\n",i);    

    return 0;

}

 

이 문제의 로직은 간단하다.

 

priority_queue 로 학생들의 성적을 특정 사이즈까지만 저장한 뒤,

 

특정 사이즈까지 push 됐을 때, pop()을 해주면

 

priority_queue 클래스에서 자동으로 오름차순으로 정렬되어서 큰 수는 pop되고, 작은 수는 push되게 된다.

 

모든 학생성적을 입력받고 queue에 저장이 되면, 반전할 수 없으므로 Vector를 이용하여 반전시킨 뒤

 

출력시켜주면 된다!

 

---

 

라인 스위핑

 

하나의 라인을 한번에 빗자루 쓸 듯이 탐색하는 것만으로

 

점과의 집합, 선과의 집합등 탐색을 끝내는 것을 라인스위핑이라고 한다.

 

사실 이는 굉장히 고급 알고리즘에 속한다.

 

교차점, 점과 점의 집합 찾기 등 기하문제를 풀 때 사용되는데 코딩테스트에는 그정도 기하수준은 나오지 않기 때문에

 

한번에 무언가 점이나 선들을 쓸어버리면서 문제를 푸는 것이다. 라고 생각하면 된다.

 

예시로 문제를 풀어보자!

 

 

백준 2170 문제 - 선 긋기

 

매우 큰 도화지에 자를 대고 선을 그으려고 한다.

 

선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.

 

선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데,

 

여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

 

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오.

(선이 여러 번 그려진 곳은 한 번씩만 계산한다.)

 

입력

첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

 

출력

 

첫째 줄에 그은 선의 총 길이를 출력한다.

 

실습코드

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std; 
typedef pair<int, int> P;
P L[1000004];
int n, from, to, l, r, ret; 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    cin >> n; 
    for(int i = 0; i < n; i++){ 
        cin >> from >> to;
        L[i] = P(from, to);
    }
    sort(L, L + n); 
    l = L[0].first; r = L[0].second; 
    for(int i = 1; i < n; i++){ 
        //만약 이번 X가 이전 Y보다 크면 l과 r을 새로갱신해주고
        //이전 길이를 더해줌
        if(r < L[i].first){ 
            ret += (r - l); 
            l = L[i].first;
            r = L[i].second;
        //만약 
        }else if(L[i].first <= r && L[i].second >= r){ 
            r = L[i].second;
        }
    }
    ret += r - l;
    cout << ret << '\n';
}

 

이 코드의 핵심은 배열을 쓰지못한다는 것에 있다.

 

원래라면 visited 배열을 선언하여 받은 x,y의 범위만큼 1을 만든 다음, visited 안의 값이 1인값만 더해주면 길이가 나온다.

 

하지만 조건에서 x,y 값이 최소 -1,000,000,000, 최대 1,000,000,000 이라는 무자막지한 조건이 있다..!!

 

이 경우를 해소하려면 먼저 선의 길이를 담을 Pair<int,int> L을 선언하여준다!

 

그 다음에 내부 정수형 변수 r 과 l을 이용하여 이전 선의 x,y 를 담은 뒤, 현재의 선의 x,y 와 비교하여 준다.

 

만약 이전 y보다 현재의 x가 더 작을 경우, 중복되는 선이 있는 것이므로

 

이전 선의 길이를 ret에 더해준다음, l과 r을 현재의 선 x,y로 대입해준다.

 

만약 이전 y가 현재의 x보다 크고, 현재의 y보다 작은 경우 중복되는 선만 제거하면 되기때문에 r = 현재의 y 로 대입하여준다.

 

이렇게 반복문이 끝나면 마지막 탐색에서의 길이는 더해주지 않았기때문에 ret에 r - 1 을 더해주면 된다!