AlgorithmProgrammers

프로그래머스 가장 큰 수

, ,

1. 프로그래머스 가장 큰 수 문제

2. 컴퓨팅적 스킬

  • 0 또는 양의 정수 1 <= numbers_length <= 100,000, 0 <= numbers <= 1000 를 보고 O(N^2) 복잡도 불가할 것이라 예측하였습니다. 왜냐하면 (100,000)^ = 약 100억
  • String to int 변환 함수 atoi(str.c_str()), int to String 변환함수 to_string(number)
    • “String" - ‘0’ => 숫자로 변경이 가능합니다. 단, 범위는 0~9까지
    • Number + ‘0’ => 문자로 변경이 가능합니다. 단, 범위는 0~9까지
    • 숫자가 10이 나왔을 경우에는 dec = dec * 10 + str[i] - '0'의 형식으로 해주어야합니다. 유사문제로는 카카오 셔틀버스 문제가 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
bool compare(const string &s1, const string &s2){
    return s1 + s2 > s2 + s1 ? true : false;
}
bool compare(const string &s1, const string &s2){
    
    if(s1 > s2){
        return true;
    }else {
        return false;
    }
}

3. 컴퓨팅적 사고

  • string기준으로 문제를 해결해야한다.
  • 맨 처음 순열과 같이 DFS로 완전탐색을 하였지만 시간초과 가 나서 sort()함수 사용해봤지만 테스트케이스는 맞지만 시간초과는 그대로여서 시간복잡도에 고민을 한번 더 하였습니다.
  • Sort Compare로 비교 후 정렬값들을 가지고 문자열끼리 append시켜주었으면 쉽게 해결하였을 문제였습니다.
  • compare 함수 기본 형식(기본적으로 오름차순을 적용시킵니다.) 굳이 if문을 쓰지 않고 바로 return s1 > s2형식으로 해주어도 됩니다.

4. 풀이

4.1. 1. DFS풀이(시간초과)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//  가장큰수.cpp
//  algorithm-level-up
//
//  Created by kgh on 14/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;
bool check[100001];
int ans = 0;
int arr[100001];
vector<int> value_v;

bool compare(const string &a, const string b){
    
    if(b.size() > a.size()){
        return b > a;
    }else {
        return b < a;
    }
    
}
void dfs(int idx,vector<int> v,int len){
    
    //len개를 모두 선택하였을 경우
    if(idx == len){
        string str = "";
        for(int i=0; i<len; i++){
            str += to_string(value_v[i]);

        }
        int comp = atoi(str.c_str());
        
        if(comp > ans){
            ans = comp;
        }
        return;
        
    }
    
    for(int i=0; i<len; i++){
        if(check[i]){
            continue;
        }
        check[i] = true;
        value_v.push_back(v[i]);
        dfs(idx+1, v, len);
        value_v.pop_back();
        check[i] = false;
        
    }
}
int main(void){
    
    vector<string> s;
    s.push_back("3"); s.push_back("30"); s.push_back("34");s.push_back("5");s.push_back("9");
    int len = s.size();
    vector<int> v(len);
    sort(s.begin(), s.end(), compare);
    
    for(int i=0; i<s.size(); i++){
        v[i] = atoi(s[i].c_str());
    }
    dfs(0,v,len);
    cout << to_string(ans);
    return 0;
    
}

4.2. String 정렬 비교(시간초과 X 정답)

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
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool compare(const string &s1, const string &s2){

    cout << s1 + s2;
    cout << s2 + s1 << '\n';


    return s1 + s2 > s2 + s1 ? true : false;

}

int main(void){
    string ans = "";
    vector<int> numbers;
    vector<string> s;
    numbers.push_back(3); numbers.push_back(30); numbers.push_back(34);numbers.push_back(5);numbers.push_back(9);
    
    int numbers_len = numbers.size();
    for(int i=0; i<numbers_len; i++){
        s.push_back(to_string(numbers[i]));
    }
    
    sort(s.begin(), s.end(), compare);
    int s_len = s.size();
  
   
    for(int i=0; i<s_len; i++){
          ans += s[i];
    }
    if(ans[0] == '0')
        return "0";
    cout<< ans;

    return 0;
    
}

유사문제: 백준 1422 숫자의 신

Share