[프로그래머스 Lv.1 / C++] Day10. 정수 내림차순으로 배치하기

2024. 05. 27 - 코딩테스트 스터디 Day10

 

 

01. 문제 설명

함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다.

 

 

02. 제한사항

• n은 1이상 8000000000 이하인 자연수입니다.

 

03. 입출력 예

n	return
118372	873211

 

 

04-1. 풀이 및 답 - 배열, 버블 정렬 사용

#include <string>
#include <vector>

using namespace std;

long long solution(long long n) {
    long long answer = 0;
    int array[10];
    int temp = 0;
    int i = 0;
    
    while (n) {
        array[i++] = n % 10;
        n /= 10;
    }
    
    for (int j = 0; j < i-1; j++) {
        for (int k = 0; k < i-1-j; k++) {
            if (array[k] < array[k+1]) {
                temp = array[k];
                array[k] = array[k+1];
                array[k+1] = temp;
            }
        }
    }
    
    for (int j = 0; j < i; j++) {
        answer *= 10;
        answer += array[j];
    }
    
    return answer;
}

배열을 사용하여 문제를 풀어보았다.

제한사항에서 n은 10자리수인 8000000000 이하라고 했으므로 크기가 10인 배열 array를 선언해주었다.

 

우선 n이 0이 될 때까지 while문을 돌면서 array 배열에 n의 맨 마지막 자리수를 넣어주었다.

그러고서 버블 정렬을 사용하여 array 배열 요소들을 내림차순으로 정렬하였다.

여기서 i는 while문을 돌 때 계산된 array의 size이다.

 

answer에 10을 곱하고, array 배열의 요소를 하나씩 차례대로 answer에 넣는 작업을 총 i번 반복한다.

(answer에 배열 요소 값들을 넣은 뒤 10을 곱하면 안된다!)

 

야호

 

 

04-2. 풀이 및 답 - vector, sort() 함수 사용 ★

문제에서 주어진 초기 코드 최상단에 <vector>를 include 하고 있기 때문에 vector를 사용하여 문제를 풀이해보았다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(long long n) {
    long long answer = 0;
    vector<int> v;
    int temp = 0;
    
    while (n) {
        v.push_back(n % 10);
        n /= 10;
    }

    sort(v.begin(), v.end(), greater<int>());
    
    for (int i = 0; i < v.size(); i++) {
        answer *= 10;
        answer += v[i];
    }
    
    return answer;
}

int 형의 벡터 v를 선언한다.

우선 n이 0이 될 때까지 while문을 돌면서 push_back() 함수를 사용하여 v에 n의 맨 마지막 자리수를 넣어주었다.

 

sort 함수를 통해 v 안의 요소들을 정렬한다.

sort 함수의 첫번째 인자로 v의 첫 번째 데이터를, 두번째 인자로 v의 두번째 데이터를 넣어주고, 세번째 인자로 greater<int>()를 넣어주어 내림차순으로 정렬하도록 해준다.

 

answer에 10을 곱하고, array 배열의 요소를 하나씩 차례대로 answer에 넣는 작업을 총 v의 size만큼 반복한다.

 

둘 중 더 효율적인 코드는?

1. 배열 vs vector
- 배열은 최대 크기가 고정되어 있으나, vector는 필요에 따라 유동적으로 확장되므로 두번째 코드가 좀 더 확장성이 좋다

2. 버블 정렬 방식 사용 vs STL의 sort() 함수 사용
- 버블 정렬의 시간 복잡도는 O(n²) 이고, STL의 sort() 함수는 퀵 정렬을 사용하기 때문에 시간 복잡도가 O(nlogn) 이다. 따라서 sort()를 사용하는 것이 더 효율적이다

→ 두번째 코드가 더 효율적인 코드이다.

 

 

 

역시 정답!

 

 

05. 개념 정리

5-1) vector

vector란? array 처럼 최대 크기가 정해져 있는 것이 아니라 필요에 따라 유동적으로 확장되는 배열

 

(1) 선언

vector<타입> 변수이름;

 

 

(2) 주요 멤버 함수

v[index];

v의 index번째 위치 요소

 

v.begin();

v의 첫번째 데이터

 

v.end();

v의 마지막 데이터

 

v.push_back(n);

v의 마지막 데이터 뒤에 데이터 n 삽입

 

v.pop_back();

v의 마지막 데이터 요소 삭제

 

v.clear();

v의 모든 데이터 요소 삭제

 

v.size();

v의 데이터 개수

 

 

5-2) sort() 함수

(1) 기본

sort(첫번째 데이터, 마지막 데이터);

세번째 인자를 입력하지 않으면 디폴트 설정인 오름차순으로 정렬된다.

 

(2) 오름차순

sort(첫번째 데이터, 마지막 데이터, less<데이터 타입>());

세번째 인자로 less<데이터 타입>()를 입력하면 오름차순으로 정렬된다.

 

 

 

(3) 내림차순

sort(첫번째 데이터, 마지막 데이터, greater<데이터 타입>());

세번째 인자로 greater<데이터 타입>()를 입력하면 내림차순으로 정렬된다.

 

 

06. 참고한 게시글

https://dense.tistory.com/entry/cpp-stl-vector

[C++ vector] 사용법

https://imjeongwoo.tistory.com/52

[C++] sort 이용한 오름차순, 내림차순 정렬, greater<>, less<>

 

 

---

 

 

끝!