[Algorithm] 1주차 스터디 - 시간복잡도&정렬(백준 11931, 10610, 11399, 11582, 1448)

A - 11931(수 정렬하기 4) 

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

11931번: 수 정렬하기 4

문제

N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램을 작성하시오.

풀이 

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}

int main(){
    int num;
    cin >> num; 
    vector<int> v;

    for (int i =0; i<num; i++){
        int input;
        cin>> input;
        v.insert(v.begin() + i, input);
    }

    sort(v.begin(), v.end(), greater<int>());

    for(int i : v){
        cout << i << '\n';
    }
}

입력받을 숫자의 개수(num)을 입력받은 뒤 반복문을 돌면서 num개의 숫자들을 입력받아 벡터에 삽입한다. 
sort 알고리즘을 사용하여 내림차순으로 정리한다. <functional>라이브러리에 있는 greater<int>() 함수를 사용하였다.
벡터에 있는 모든 element들을 출력하면 끝! 

B - 10610(30) 

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

10610번: 30

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

풀이 

#include <iostream>
#include <vector> 
#include <string>
#include <functional>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    string str; 
    cin >> str;
    vector<int> v; 
    
    //더해서 3의 배수인지 보기 
    int total =0; 
    for (int i=0; i<str.size();i++){
        total += str[i] - '0';
        v.push_back(str[i]-'0');
    }
    
    sort(v.begin(), v.end(), greater<int>());
    
    if(total%3==0 && v[str.size()-1]==0){
        for(auto i : v)
            cout << i; 
    } else{
        cout << -1; 
    }
}

숫자를 다 뜯어서 각 자릿수의 숫자를 따로 봐야하기 때문에 문자열로 입력받았다. 각 문자열을 돌면서 합(total)을 구하고 문자 하나하나 vector에 삽입한다. 그 다음에는 벡터를 내림차순으로 정렬해준다. 이렇게 정렬된 벡터는 맨 뒷자리 수(일의 자리 수)가 0이어야 하고, total이 3의 배수이어야 한다.(30의 배수인지 알 수 있는 방법) 해당 조건들을 만족하면, 이미 정렬된 벡터를 순서대로 출력하면 된다! 

C - 11399(치킨 TOP N)

 

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

11582번: 치킨 TOP N

문제

인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많아 혼자 정렬을 하기에는 많은 시간이 걸려 C.T.P 회원들을 활용하기로 했다. 치킨집이 N개 있다고 가정을 하자. N개의 치킨의 수치를 무작위로 놓은 뒤 N/2명의 C.T.P 회원이 차례대로 2개의 치킨집을 선택해  정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택 하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료한다.

예를 들어 8개의 치킨집의 점수가 (1, 5, 2, 4, 2, 9, 7, 3)과 같을 때, 첫 번째로 4명의 회원이(1, 5), (2, 4), (2, 9), (7, 3)을 각각 정렬하게 되면 (1, 5), (2, 4), (2, 9), (3, 7)이 되고, 두 번째로 2명의 회원이 ((1, 5), (2, 4))와 ((2, 9), (3, 7))을 정렬하면 (1, 2, 4, 5), (2, 3, 7, 9)가 되고, 최종적으로 1명의 회원이 ((1, 2, 4, 5), (2, 3, 7, 9))을 정렬하여 (1, 2, 2, 3, 4, 5, 7, 9)을 만들게 된다.

작업을 진행하던 중 문득 민호는 작업의 중간단계가 궁금해졌다. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력해라.

풀이 

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

using namespace std;

int sorted[1048576];
int N;
int stu;
int array[1048576];

void merge(int a[], int m, int middle, int n){
    if((n-m)>(N/stu)) return;
    int i = m; 
    int j = middle + 1;
    int k = m;
    
    while (i<=middle & j<=n){
        if(a[i]<=a[j]){
            sorted[k++] = a[i++];
        }
        else{
            sorted[k++]=a[j++];
        }
    }
    
    while(i<=middle) sorted[k++] = a[i++];
    while(j<=n) sorted[k++] = a[j++];
    for(int i=m; i<=n; i++) a[i] = sorted[i];

}

void mergeSort(int a[], int m, int n){
    if(m<n){
        int middle = (m+n)/2;
        mergeSort(a, m, middle);
        mergeSort(a, middle+1, n);
        merge(a, m, middle, n);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for(int i=0; i< N; i++){
        cin >> array[i];
    }
    cin >> stu; 
    mergeSort(array,0, N-1);
    
    for(int i=0 ;i<N;i++){
        cout << array[i] << ' ';
    }
}

이 문제는 merge sort를 사용하는 문제이다. 나동빈님의 merge sort영상을 참고하여 코드를 짰다. 정렬을 하는 코드는 짤 수 있었지만 중간에 어떻게 멈추면 좋을지 오랜 시간 고민했다. 치킨집의 갯수와 학생의 수 모두 2의 거듭제곱이기 때문에 이 조건을 사용하면 좋겠다는 생각이 들었다. 배열의 양 끝 index의 차가 전체 원소 갯수를 학생의 수만큼 나눈 것 보다 크다면 바로 return하여 그 때의 배열의 상태를 출력한다. 

D - 1448(삼각형 만들기)

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

1448번: 삼각형 만들기

문제

세준이는 N개의 빨대를 가지고 있다. N개의 빨대 중에 3개의 빨대를 선택했을 때, 이 빨대로 삼각형을 만들 수 있다면, 세 변의 길이의 합의 최댓값을 구하고 싶다.

풀이 

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

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    
    int N; 
    int array[1000000]; 
    
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> array[i];
    }
    
    sort(array, array+N, greater<int>());
    
    int i=0; 
    int total;
    while(i<N-2){
        int biggest = array[i];
        total =0;
        if(array[i+1] + array[i+2] > biggest){
            total = biggest+ array[i+1]+ array[i+2];
            
            break;
        } else {
            i++; 
            total = -1;
        }
    }
    cout << total;
    
    
}

N개의 빨대 중 3개를 뽑아 삼각형을 만든 뒤 세 변 길이의 합의 최댓값을 구하기 위해서는 일단 입력받은 수들을 정렬해야한다. 내림차순으로 정렬한 뒤 맨 앞의 수가 뒤의 두 수의 합보다 작으면 삼각형이 만들어지고 세 변의 길이의 최댓값을 구할 수 있다. 만약 맨 앞의 수가 뒤의 두 수의 합보다 크다면 index를 하나씩 뒤로 옮겨 다시 앞의 과정을 반복해본다.