백준 2822 점수계산 (실버 5) / <algorithm>_sort()

티스토리 너무 어렵다...

백준보다 어려운거같다..

 

어쨌든 내가 오늘 리뷰할 문제는 2822번이다. 난이도도 실버 5로 별로 어렵지도 않고 시간 제약도 없다.

편안하게 풀면 되는데 sort() 에 대해 궁금한게 생겨서 이거 저거 찾아보고 느낀점과 코드 리뷰도 같이 하면 좋을 것 같아서 적어봤다.

 

우선 sort() 함수는 #include <algorithm> 헤더의 내장함수이다.

sort 뜻 그대로 정렬 해준다는 뜻 이며 오름차순이 Default이다. 

사용법은 sort(array, array+10) 하면 a배열에 대해 오름차순 정렬을 해준다.  정말 간단하다.

내림차순은 sort(array, array, greater<자료형>()) 과 같은 형식이다.  greater<자료형>() 뒤의 괄호()는 필수이다!!.

또한 greater<자료형>() 부분에 사용자 지정함수를 넣어 내맘대로 정렬이 가능하다.

sort(array, array+n, greater<int>());  이런느낌

 

실버문제라 시간복잡도를 계산하지 않아도 되는데 sort 함수의 시간복잡도는 얼마일까라는 생각이 들어 sort 함수에 대해 찾아보았다

sort() 함수는 퀵 정렬을 사용하므로 시간복잡도는 NlogN이 된다고 한다. 

(코딩을 하며 퀵 정렬을 짜야하는데.. 내장함수만 사용하는 나.. 어쨌든 빠르게 잘 돌아가면 된거잖아..? ^_^;;;) 

또한 벡터에서도 사용되어 찾아보았는데 메모리 기반 정렬이기 때문에 배열 혹은 vector에 사용될 수 있다. 라고 한다.

 

이정도 알아보았으니 이제 2822번 소스코드를 리뷰하자면 백준의 친구, 취업걱정은 안해도 될만큼 직업이 많은 같은 상근이가 여자친구와 통화를 하다가 점수 계산을 우리에게 넘겼다. 문제는 어렵지 않다. 

 

 

입력도 간단하다 8개의 숫자를 받아서 총 합과 가장 큰 점수 5개를 적으면 된다.

 

문제를 보고 직관적으로 생각하며 풀면 반복문 2개만 쓰면 끝난다. 라는 생각이 강하게 든다. 실버5라서 반복문 2번 쓰면 끝날텐데.. 라는 생각이 강했지만 sort() 함수에 대한 궁금증이 너무 강했다.

 

반복문을 2번 써야하는 상황에서 (정렬하기, 인덱스 찾기..  때문에) 반복문을 한번만 쓰려면 어떻게 할까 라는 생각이 들어서 고민을 해보게 되었다. 퀵 정렬에서 기준값을 가지고 정렬하는걸 응용하여 배열을 하나 더 만들고 키값을 주었다.

 

정렬을 하게되면 나오는 이중 반복문은 sort() 함수를 통해 O(N^2)-> O(NlogN)의 시간 복잡도로 바꿔주었고, 배열을 복사해서 6번째 값 보다 크면 인덱스를 출력 및 sum값에 더해주는 반복문을 하나 더 추가하였다.

 

배열의 크기는 int score[8], sort5[8]; 이렇게 2개니까 하나당 4byte *8인 32Byte 2개.. 

32Byte짜리 배열이 하나가 더 늘어나 필요가 없어보이지만. 그래도 2중 for문을 안쓸 수 있다면 좋다고 생각한다.

 

소스코드가 매우 더럽다.! 그래서 필요하신 부분만 골라서 사용하시면 좋을 것 같다.

좋은 습관은 아닌것 같지만 c++은 변수의 선언부가 없어서 필요한 블록위에 선언하고 사용하면

더욱 직관적으로 이 변수의 쓰임새를 알 수 있다고 해야할까?

이 습관도 차근차근 고쳐나가봐야 할 것 같다.

 

- 피드백은 언제나 환영합니다.

 

- 위에 소스코드가 맘에 들면 복사 하기 쉽게 글자도 붙여넣어 보았다. 

(삼성 멀티캠퍼스에서 교육해주신 킹갓짱짱기민 강사님께서 복붙을 마음껏 해보고 자기꺼로 만드라고 하셨으니까..)

 

#include <iostream>

#include <stdio.h>

#include <algorithm>

using namespace std;

 

int main() {

    

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    

    int score[8];

    int sort5[8];

    int *index = new int[5];

 

    for(int i=0; i<8; i++) {

        cin >> score[i];

        sort5[i] = score[i];

    }

    

    

    sort(sort5, sort5+8);

    int mid = sort5[2];

 

    int cnt=0;

    int sum=0;

    for(int i=0; i<8; i++) {

        if (score[i] > mid) {

            index[cnt++] = i;

            sum += score[i];

        }

    }

    

    cout <<sum << "\n";

    for(int i=0; i<5; i++) {

        cout << index[i]+1  << " ";

    }

}