[알튜비튜] 정렬 - 백준 2750, 2751, 10825번

알튜비튜

[알튜비튜] 정렬 - 백준 2750, 2751, 10825번

shinyunha 2026. 3. 9. 23:53

맨날 까먹는 C++ 기본 준비

#include <iostream>

using namespace std;

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

    return 0;
}

백준 2750번 : 수 정렬하기

입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

C++은 1초에 10억번 연산 가능

-> Bubble Sort(O(n^2))를 사용해도 시간초과가 발생하지 않는다.

내가 풀기

1. 배열보다 vector를 쓴다

2. algorithm안에 swap() 함수가 있다

3. vector 범위 벗어나지 않게 for문 범위 n-1 주의!

4. 줄바꿈 '\n' 잊지 않고 추가하기

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

using namespace std;

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

    int n;
    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n-1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }

        }

    }

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}

설명 듣고 수정

1. 함수로 분리하기

2. i번째 for문은 돌아갈 필요 없음. 제일 작은 애 혼자 남아서 -> 바깥쪽 for문 전체길이 - 1 만큼만 돌기

3. 안쪽 for문 진입할 때, i만큼은 정렬된 상태 -> 안쪽 for문은 전체길이 - 1 - i 만큼만 돌기

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

using namespace std;

void bubbleSort(vector<int> &arr) {
    int len = arr.size();

    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

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

    int n;
    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    bubbleSort(arr);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}

백준 2751번 : 수 정렬하기 2

입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

O(n^2) 알고리즘으로는 시간초과

-> O(nlogn)인 merge sort 사용

내가 풀기

자료구조 정리해 둔 글 참고해서 풀었다

https://shinyunha.tistory.com/30

[자료구조] 정렬

record단위로 정렬record는 field로 이루어짐key field로 record를 구별Internal Sorting: 모든 데이터가 주기억장치에 저장된 상태에서 정렬External Sorting: 외부기억장치에 대부분의 데이터가 있고 일부만 주

shinyunha.tistory.com

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

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int sorted_left = left;
    int sorted_right = mid + 1;
    int merged = left;

    vector<int> sorted(arr.size());

    while (sorted_left <= mid && sorted_right <= right) {
        if (arr[sorted_left] < arr[sorted_right]) 
            sorted[merged++] = arr[sorted_left];        
        else 
            sorted[merged++] = arr[sorted_right];        
    }

    if(sorted_left > mid)
        for (int i = sorted_right; i <= right; i++)
            sorted[merged++] = arr[i];
    else
        for (int i = sorted_left; i <= mid; i++)
            sorted[merged++] = arr[i];

    for (int i = 0; i < right; i++)
        arr[i] = sorted[i];
}

void mergeSort(vector<int> &arr, int left, int right) {   
    int mid;

    if (left < right) {
        mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

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

    int n;
    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

   mergeSort(arr, 0, n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}

Visual Studio에서 한 단계씩 돌리는 것도 해봤는데 입력받다가 멈춰버림 믿을수가 없음

Gemini한테 물어봄

1. while문 안에서 sorted_left와 sorted_right를 증가시키지 않음

while (sorted_left <= mid && sorted_right <= right) {
    if (arr[sorted_left] < arr[sorted_right]) 
        sorted[merged++] = arr[sorted_left++];        
    else 
        sorted[merged++] = arr[sorted_right++];        
}

2. main에서 mergeSort 호출할 때, right 값 n이 아니라 n-1

mergeSort(arr, 0, n-1);

3. merge에서 덮어쓰기 할 때, left에서 right까지 덮어써야함

for (int i = left; i <= right; i++)
    arr[i] = sorted[i];
}

제출했더니 시간 초과

다시 Gemini한테 물어봤다. 메모리 할당에 시간이 소요 되니, 임시 vector를 하나만 만들고 그걸 계속 쓰란다.

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

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right, vector<int>& sorted) {
    int sorted_left = left;
    int sorted_right = mid + 1;
    int merged = left;  

    while (sorted_left <= mid && sorted_right <= right) {
        if (arr[sorted_left] < arr[sorted_right]) 
            sorted[merged++] = arr[sorted_left++];        
        else 
            sorted[merged++] = arr[sorted_right++];        
    }

    if(sorted_left > mid)
        for (int i = sorted_right; i <= right; i++)
            sorted[merged++] = arr[i];
    else
        for (int i = sorted_left; i <= mid; i++)
            sorted[merged++] = arr[i];

    for (int i = left; i <= right; i++)
        arr[i] = sorted[i];
}

void mergeSort(vector<int> &arr, int left, int right, vector<int> &sorted) {   
    int mid;

    if (left < right) {
        mid = (left + right) / 2;

        mergeSort(arr, left, mid, sorted);
        mergeSort(arr, mid + 1, right, sorted);
        merge(arr, left, mid, right , sorted);
    }
}

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

    int n;
    cin >> n;

    vector<int> arr(n);
    vector<int> sorted(n);

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

   mergeSort(arr, 0, n-1, sorted);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}

설명 듣고 수정

1. 임시 vector를 전역 변수로 선언

2. assign() 함수로 sorted에게 메모리 할당

3. sorted_left, sorted_right 변수가 너무 길어서 가독성이 안 좋음, pl, pr로 변경

4. merge에서 while문 끝나고 남은 것들을 while문으로 채우기

- if와 for문을 쓰는 방식보다 뭐가 더 좋은지 궁금해서 Gemini에게 물어봄

코드가 더 짧아 가독성이 좋고, 조건문과 변수가 덜 쓰이기 때문에 버그를 만들 확률도 낮다고 한다

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

using namespace std;

vector<int> sorted;

void merge(vector<int>& arr, int left, int mid, int right) {
    int pl = left;
    int pr = mid + 1;
    int merged = left;  

    while (pl <= mid && pr <= right) {
        if (arr[pl] < arr[pr]) 
            sorted[merged++] = arr[pl++];        
        else 
            sorted[merged++] = arr[pr++];        
    }

    while (pl <= mid)
        sorted[merged++] = arr[pl++];
    while (pr <= right)
        sorted[merged++] = arr[pr++];   

    for (int i = left; i <= right; i++)
        arr[i] = sorted[i];
}

void mergeSort(vector<int> &arr, int left, int right) {   
    int mid;

    if (left < right) {
        mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

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

    int n;
    cin >> n;

    vector<int> arr(n);
    sorted.assign(n, 0);

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

   mergeSort(arr, 0, n-1);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}

5. algorithm에 sort() 함수가 있었다! 세상에

역시 무식하면 몸이, 아니 손가락이 고생한다

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

using namespace std;

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

    int n;
    cin >> n;

    vector<int> arr(n);
   
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

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

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}

백준 10825 : 국영수

내가 풀기

1. map 쓰려다가, map sort를 찾아보니 다시 vector로 변환해야한다고 한다.

2. pair라는 새로운 친구를 만났다. map이랑 거의 똑같다

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

static bool comp(pair<string, int>& a, pair<string, int>& b) {
    return a.second  > b.second;
}

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

    int n;
    cin >> n;

    vector<pair<string, int>>kor(n);
    map<string, int> eng;   
    map<string, int> math;  

    for (int i = 0; i < n; i++)
    {
        string name;
        cin >> name;

        int score;
        
        cin >> score;
        kor.push_back({ name, score });
        cin >> score;
        eng.insert({ name, score });
        cin >> score;
        math.insert({ name, score });
    }

    sort(kor.begin(), kor.end(), comp);

    for (int i = 0; i < n; i++)
    {
        if (kor[i].second == kor[i + 1].second) {
            if (eng[kor[i].first] == eng[kor[i + 1].first])
            {
                if (math[kor[i].first] == math[kor[i + 1].first])
                {
                    if (kor[i].first > kor[i + 1].first) 
                        swap(kor[i], kor[i + 1]);
                }
                else 
                {
                    if (math[kor[i].first] < math[kor[i + 1].first])
                        swap(kor[i], kor[i + 1]);
                }                            
            }
            else 
            {
                if (eng[kor[i].first]  > eng[kor[i + 1].first])
                    swap(kor[i], kor[i + 1]);
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout << kor[i].first << '\n';
    }

    return 0;
}

결과가 안 맞는다. sort 후에 어떻게 되는지 찍어봤다.

내 코드는 점수 같은 사람이 많아야 2명인 상황에만 먹힐 것 같다.

점수 같은 애들끼리 따로 빼서 국어 점수는 무시하고 다시 sort? 그 로직은 함수로 빼고?

점수 같은 애들끼리 어떻게 따로 뺄건데....ㅎ

Gemini한테 백준 10825 문제 뭔지 아냐고 물어봤더니 알고 있다. struct를 만들어서 풀면 쉽다는 점도 알려줬다. 아 세상에 struct는 C에도 있는데 왜 나는 여태 생각을 못했지.....

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct Score
{
    string name;
    int kor;
    int eng;
    int math;
};

static bool comp(const Score& a, const Score& b) {
    if (a.kor == b.kor) {
        if (a.eng == b.eng) {
            if (a.math == b.math)
                return a.name < b.name;
            else
                return a.math > b.math;
        }
        return a.eng < b.eng;
    }
    return a.kor > b.kor;
}

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

    int n;
    cin >> n;

    vector<Score> score(n);    

    for (int i = 0; i < n; i++)
    {
        string name;
        cin >> name;
        score[i].name = name;

        int num;
        
        cin >> num;
        score[i].kor = num;
        cin >> num;
        score[i].eng = num;
        cin >> num;
        score[i].math = num;
    }

    sort(score.begin(), score.end(), comp);       

    for (int i = 0; i < n; i++)
    {
        cout << score[i].name << '\n';
    }

    return 0;
}

설명 듣고 수정

1. 입력 받을 때, 변수에 받아서 그거 다시 구조체에 넣지 말고 cin에서 바로 넣기

2. compare 함수 만들 때, if 안에, if 안에 if 이런 식으로 만들지 말고 조건문을 != 로 걸어서 간결하게 - 이거 진짜 너무 멋지다

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct score
{
    string name;
    int kor;
    int eng;
    int math;
};

static bool comp(const score& a, const score& b) {
    if(a.kor !=  b.kor) return a.kor > b.kor;
    if(a.eng != b.eng)  return a.eng < b.eng;
    if(a.math != b.math) return a.math > b.math;
    return a.name < b.name;
}

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

    int n;
    cin >> n;

    vector<score> score(n);    

    for (int i = 0; i < n; i++)
        cin >> score[i].name >> score[i].kor >> score[i].eng >> score[i].math;      

    sort(score.begin(), score.end(), comp);       

    for (int i = 0; i < n; i++)
    {
        cout << score[i].name << '\n';
    }

    return 0;
}

현재글[알튜비튜] 정렬 - 백준 2750, 2751, 10825번

shinyunha 님의 블로그

shinyunha 님의 블로그 입니다.

Today :
Yesterday :

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

shinyunha 님의 블로그