https://programmers.co.kr/learn/courses/30/lessons/42746

 

코딩테스트 연습 - 가장 큰 수 | 프로그래머스

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

programmers.co.kr

정답 : 

#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
struct stackStruct{
 
    int delta;
   
    
 
};
struct int_compare {
  bool operator()(const int& a, const int& b) const { return a < b; }
};

struct stackStruct_compare {
  bool operator()(const int& a, const int& b) const { 
      
      int arry[2]={0,0};
      string tmpstr1="";
      string tmpstr2="";
          arry[0]=a;
          arry[1]=b;
          int cnt=0;
          for(int i:arry){
              
              tmpstr1+=to_string(i);
             
          }
          arry[0]=b;
          arry[1]=a;
          for(int i:arry){
              tmpstr2+=to_string(i);
          }
          return stoi(tmpstr1)>stoi(tmpstr2);
          
      }
      
};
string solution(vector<int> numbers) {
    string answer="";
    stackStruct tmp;
    vector<int> stack;
    vector<int> pivot;
    
   int ccn=0;
    
  sort(numbers.begin(),numbers.end(),int_compare());
  sort(numbers.begin(),numbers.end(), stackStruct_compare());
  
    int arr[numbers.size()];
    int count =0;
    for(int i=0;i<numbers.size();i++){
        
        if(numbers[i]==0){
        count++;    
        }
       arr[i]=numbers[i];
    }
    for(int i:arr){
        
        answer+=to_string(i);
    if(count==numbers.size()){
          answer=to_string(0);
        }
    }
  
    
    return answer;
}

200811

#include <string>
#include <vector>
#include <algorithm>
#include<iostream>
using namespace std;
bool cmp(const int &p1, const int &p2){
    if(p1 > p2){
        return true;
    }else {
        return false;
    }
    
}
struct Save{
  int number;
  int flag;//flag
  int data;//비교값
    
};
bool cmpSTR(const Save &p1, const Save &p2){
    if(p1.number > p2.number){
        return true;
    }else if(p1.number < p2.number){
        return false;
    }else if(p1.number == p2.number){
         int firstNum= p1.data;
         int secondNum= p2.data;
        string str1="";
        string str2="";
        str1=to_string(firstNum)+to_string(secondNum);
        str2=to_string(secondNum)+to_string(firstNum);
        int comFirst=stoi(str1);
        int comSecond=stoi(str2);
        if(comFirst>comSecond){
            
            return true;
       }else if(comFirst<comSecond){
           return false;
       }
            return false;
       
        
        
        
       
    }
    
}

string solution(vector<int> numbers) {
    string answer = "";
    int test=0;
    vector<Save>collects;
   
     sort(numbers.begin(),numbers.end(),cmp);
    
 
 
    
    for(int i=0;i<numbers.size();i++){
          Save tmpSave;
        if(numbers[i]==0){
          test++;
         }
        if(numbers[i]/1000>=1){
            tmpSave.number=numbers[i]/1000;
            tmpSave.flag=i;
            tmpSave.data=numbers[i];
            
        }else if (numbers[i]/100>=1){
              tmpSave.number=numbers[i]/100;
              tmpSave.flag=i;
              tmpSave.data=numbers[i];
            
        }else if (numbers[i]/10>=1){
              tmpSave.number=numbers[i]/10;
             tmpSave.flag=i;
             tmpSave.data=numbers[i];
            
        }else{
              tmpSave.number=numbers[i];
              tmpSave.flag=i;
              tmpSave.data=numbers[i];
        }
        collects.push_back(tmpSave);
    }
     if( test==numbers.size()){
      return "0";
   }   
    sort(collects.begin(),collects.end(),cmpSTR);
    
    string ak;
    for(int i=0;i<collects.size();i++){
       ak+=to_string(collects[i].data);
    }
    //int test =stoi(ak);
    for(int i=0;i<collects.size();i++){
        
    answer+=to_string(collects[i].data);
      
    }
  
   
     // return "0";
   
    
    return answer;
      
}

이번엔 struct를 이용해서 좀더 시각적으로 이해가 잘되도록 만들었다 

이번 방법엔 두가지의 sorting 방법을 사용했다

첫번째는 맨 앞자리수 비교 

sort(numbers.begin(),numbers.end(),cmp);

그다음 정렬이 되었다면 

앞자리가 같은 숫자들이 존재할것이다

이 같은 숫자들을 비교한다. string으로 합쳐서 int로 변환하여 다시 비교한다. 

그리고 그걸 비교해서 정렬한다.

 sort(collects.begin(),collects.end(),cmpSTR);

여기서 주의점이 있다 

데이터가 0000 인경우 return 0을 해줘야 한다.

미리 for문이 돌때 0체크를 해주고 현재 갯수와 0체크 갯수가 같으면 return "0"을 해준다

 

 

 

2011005 정렬문제 주의점중 string 반환시 

0값 , int형 값 03 ->3 으로 계산됨 잊지말것  앞자리가 같아서 비교가 불가능하면 나머지를 구하지말고 앞자리가 같은 숫자를 원본값으로 비교하는게 포인트

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
#include<cstdlib>
using namespace std;

struct NumberData{
    int num;
    int index;
    int nor;
    int counting;
};


int Divdie(int a,int *alpa){
    if(a/1000>0){
        *alpa=1000;
        return a/1000;
    }else if(a/100>0){
        *alpa=100;
        return a/100;
    }else if(a/10>0){
        *alpa=10;
        return a/10;
    }else {
        *alpa=1;
        return a;
    }
    
    
}
int Nors(int a){
    if(a/1000>0){
        return a%1000;
    }else if(a/100>0){
        return a%100;
    }else if(a/10>0){
        return a%10;
    }else {
        return a;
    }
    
    
}
bool cmp(const NumberData &p1, const NumberData &p2){

    if(p1.num>p2.num){
        return true;
    }
    else if(p1.num== p2.num){
       
       return  p1.num>p2.num;
        
        
    }
    else{
        return false;
    }
}
bool cmpSRT(const NumberData &p1, const NumberData &p2){

    if(p1.num>p2.num){
        return true;
    }
    else if(p1.num== p2.num){
       string str1;
       string str2;
        str1=to_string(p1.nor)+to_string(p2.nor);
        str2=to_string(p2.nor)+to_string(p1.nor);
        int comFirst=stoi(str1);
        int comSecond=stoi(str2);
        if(comFirst>comSecond){
            return true;
        }else{
            return false;
        }
        
        
        
    }
    else{
        return false;
    }
}
string solution(vector<int> numbers) {
    string answer = "";
    vector<int> zip;
    vector<NumberData>data;
   vector<NumberData>dataSort;
    int sum=0;
      for(int i=0;i<numbers.size();i++){
          sum+=numbers[i];
      }
    if(sum==0){
        answer="0";
        return answer;
    }
    
    
    for(int i=0;i<numbers.size();i++){
        NumberData tmp;
        tmp.num=numbers[i];
        tmp.index=i;
        tmp.nor=0;
        tmp.counting=0;
        data.push_back(tmp);
     
        
    }
    
    sort(data.begin(),data.end(), cmp);
    
    for(int i=0;i<numbers.size();i++){
        NumberData tmp;
        int alpa=0;
        tmp.num=Divdie(data[i].num,&alpa);
        tmp.index=data[i].index;
        tmp.nor=data[i].num;
        tmp.counting=alpa;
        dataSort.push_back(tmp);
        
    }
    
    
    
    
    
    sort(dataSort.begin(),dataSort.end(),cmpSRT);
    
     
    string str="";
    for(int i=0;i<numbers.size();i++){
      
       //cout<<dataSort[i].nor;
        str+=to_string(numbers[dataSort[i].index]);
   
       
        
    }
    
    answer=str;
    
    
    
    
    return answer;
}

+ Recent posts