프로그래머스 - 가장 큰 수

klean·2020년 10월 4일
0

문제 설명

0을 포함하는 양수 정수를 int 형으로 준다. 이 숫자들을 string처럼 이어붙였을 때 가장 큰 수가 나오는 경우를 찾아라.

내 아이디어(삽질)

숫자들을 맨 앞자리서부터 비교했을 때 큰 쪽이 앞으로 갈 자격이 있다.
고로 string 비교연산을 했다.
문제가 되는 경우는 98 , 9808과 같이 앞머리에 다른 후보를 포함하는 경우였다.

  1. 98, 9808의 경우 98 9808 순이다.
  2. 87, 8798의 경우 8798 97 순이다.

이 때 a. 더 긴쪽의 겹치지 않는 나머지부분b. 앞머리에 쏙들어갔던 후보 간 재귀 compare를 해주었다..^^....... 이거 땜에 한참을 segmentation fault와 싸워따.....^^^..
재귀 compare에서 ""가 생기는 게 원인이었던 거 같은데
사실 실험해보면 "" < "정상문자열"에서 operator<가 에러를 내는 건 없는데 원인을 모르겠다. 이걸 알아야 실력이 늘텐데...
아래 코드를 추가하니까 1-10번 테케가 맞고 11번 테케는 틀렸다 뜨더라..

    if(s1 == s2){
        return s1<s2;
    }

그리고 어떤 so sutteki 하신 분이 11번 테케 틀린 경우가 "00000"이 "0"이기 때문이라고^^^^^....하셔서 그 부분을 예외처리 하고 전체 테케를 맞게 되었다.

코드

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;
bool compare(string &s1, string &s2){
    
    if(s1 == s2){//이거 없으면 segmentation fault나는데 원인을 몰라요
        return s1<s2;
    }
    
    if(s1.size()>=s2.size()){
        if(s1.find(s2) ==0){
            string s11 = s1.substr(s2.size(),s1.size()-s2.size());
            
            //cout<<"i will compare "<<s11<<","<<s2<<endl;
            return compare(s11,s2);
        }
        else{
            return s1>s2;
        }
    }
    else{
        return !compare(s2,s1);
    }
}
string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> ns;
    for(int i =0;i<numbers.size();i++){
        ns.push_back(to_string(numbers[i]));
    }
    
    sort(ns.begin(),ns.end(),compare);
    for(int i =0;i<ns.size();i++){
        answer+=ns[i];
    }
    if(atoi(answer.c_str())==0){
        answer="0";
    }
    
    return answer;
}

여담

요즘 파이썬으로 문제를 조금씩 풀어보고있는데 str[시작인덱스:끝인덱스]같은 표현을 쓰다보니 c++ substr(시작인덱스, 몇개)를 끝인덱스로 바꿔 적었다^^^..... 그래도 테케는 다 맞았긴했다. 이유를 모르겟다.. (위 코드는 고침)

이 한 문제 때문에 너무 시간을 많이 써서 우울하다...

일반적, 간단하지만 확실한 아이디어

미니 결과물을 만들어보고 우위를 정한다

bool compare(const string &a, const string &b)
{
    if (b + a < a + b)
        return true;
    return false;
}

2021/05/05 2트

여전히 바로 정렬을 떠올리지는 못하고 ㅋㅋㅋㅋㅋ 처음에 완전탐색으로 모든 certificate를 만들어보는 것을 떠올렸다..
이번엔 미니 결과물을 만들어서 정렬하는 것을 적용할 수 있었고, "0000"만 나오는 경우에도 바로 "0"으로 만들어줄 수 있었다.

그리고 "0001000" 이렇게 나오는 것을 걱정했었는데 sort에 의해 저런 조합의 카드는 항상 "1000000"으로 나올 것이라는 확신이생겼따.

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

using namespace std;

bool comp(string a, string b){
    //임시 결과물을 만들어보고 결정
    return a+b>b+a;
}
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> s_nums;
    //어차피 정답도 string이기 때문에 숫자 shift를 할 생각을 배제한다.
    for(int i= 0;i<numbers.size();i++){
        s_nums.push_back(to_string(numbers[i]));
    }
    
    sort(s_nums.begin(), s_nums.end(), comp);
    bool is_zero = true;
    for(int i = 0;i<s_nums.size();i++){
        if(s_nums[i]!="0"){// 0으로 꽉채워진 벡터의 경우 "00"은 갖지 않는다.
            is_zero = false;
        }
        answer+= s_nums[i];
    }
    if(is_zero){
        answer = "0";
    }
    
    return answer;
}

1개의 댓글

comment-user-thumbnail
2020년 10월 8일

안녕하세요 오타발견해서 댓글 남깁니다

87, 8798의 경우 8798 97 순이다. 에서 97이 아니라 87인 것 같아요!
저랑 비슷하게 삽질하신분을 봐서 기뻐요..(?)
코드 잘 보고갑니다ㅎㅎ

답글 달기