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;
}
'알고리즘 공부' 카테고리의 다른 글
프로그래머스 코딩 연습 level 2-타켓 넘버 (0) | 2020.02.20 |
---|---|
프로그래머스 level 2 코딩 연습 -더 맵게 (0) | 2020.02.19 |
프로그래머스 level2 연습 문제-전화번호 목록 (0) | 2020.02.17 |
프로그래머스 level2 연습 문제-기능개발 (0) | 2020.02.17 |
프로그래머스 -level 2 코딩 연습 문제-탑 (0) | 2020.02.16 |