프로그래머스 정렬 가장 큰 수

문제 설명

programmers.co.kr/learn/courses/30/lessons/42746?language=cpp

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

 

문제 보자마자 1. 일단 자릿수를 다 같게 만들고 2. 정렬해서 3. 이어붙이자! 였다.

일년간 자바스크립트만 존나해서 자스로 로직이 머릿속에서 얼기설기 짜짐... 근데 누가 코테를 자스로 보냐구요 흑흑

 

1. 암튼 일단 자릿수를 다 같게 만들기 위한 로직을 짜봤다.

numbers의 원소들을 조사해서 가장 큰 수를 찾고 그 수의 자릿수대로 나머지 수들을 통일해주면 된다.

한창 하는데... 문득 문제를 다시 읽다가 생각해보니 원소는 1000 이하란다...^^ 오... 

최대 네 자리수니까 그냥 다 네 자리로 통일 해주면 된다. 그건 쉽지~

 

물론 씨플플 쌉초보인 나에게는 아니었다.

    for (int i : numbers)
    {
        while (i < 100)
        {
            i = i * 10;
        }
        cout << i << endl;
    }
    for (int i : numbers)
    {
        cout << i << endl;
    }
   

이렇게 했더니... 포문 안에서만 값이 바뀌고 밖에서 다시 찍으면 값이 안변한다.

어렴풋이 박상일 교수님께 배운 수업이 기억난다... 어어... 맞아 그랬던 것 같아...

그래서 바꿨다.

    for (int i = 0; i < numbers.size(); i++)
        while (numbers[i] < 100)
            numbers[i] = numbers[i] * 10;

    for (int i : numbers)
        cout << i << endl;
       

이제 잘 됨.

 

2. 정렬

라이브러리를 적극 이용합시다~

sort(numbers.begin(), numbers.end(), greater<int>());

sort는 기본 오름차순 정렬이라서, 내가 원하는대로 정렬을 하려면 세번째 인자에 정렬 기준 함수를 주면 된다.

물론 함수를 새로 만들 수도 있지만 라이브러리에 greater라는 함수가 있어서 그걸 씀.

 

3. 이어 붙이기

자스나 파이썬이라면 개껌이었을 텐데 씨플플... 후^^

물론 구글링으로 안되는 건 없다.

stackoverflow.com/questions/2518979/how-to-transform-a-vectorint-into-a-string/2519011

How to transform a vector into a string?

이 글을 참고해서 이어 붙였다.

테스트 케이스는 통과하는데 정답이 아니라 함.

질문 게시판을 보니 나 같이 생각해서 틀린 사람이 있었는데, 다음 케이스가 문제라고 한다.

테스트 케이스: [121, 12] 
정답: 12121 
나: 12112

그냥 애초에 전제 자체가 틀렸다. 자릿수 통일해서 크다고 붙였을 때 더 큰 수가 아닌 거임...

이럴 땐 파고드는 것보다 그냥 처음부터 다시 시작하는게 보통 낫다. (말은 이렇게 하지만 미련이 남아서 한 시간 동안 질척거렸음)

 

 

어차피 정렬은 이용해야하고, 정렬 함수를 바꿔보는 건 어떨까?

문제는 정렬 함수를 어떻게 해야 예외 없이 모든 경우를 커버하냐는 것이다.

자릿수 맞춰서 정렬하기 같은 꽤를 부리기 보단 문제의 본질을 생각해서, 두 수를 일단 붙여보고 더 큰 경우대로 정렬하면 될 것 같았다.

두 개를 붙이는건 string이 더 쉽고, 어차피 리턴할 때도 붙여서 string으로 리턴해야 하니까 string 배열에 하나하나 넣어준다.

그리고 정렬 함수를 짠다.

간단하다. string은 기본적으로 + 연산을 지원하므로 적극 이용한다.

compare 함수는 기본적으로 bool 값을 리턴하는 함수이다. 처음게 먼저 와야하면 true, 아니면 false를 리턴하면 된다.

bool compare(string a, string b)
{
    return a + b > b + a;
}

이제 배열을 이어 붙이고 리턴한다.

근데 테스트 케이스 하나를 통과를 못한다... 아 또 뭔데...

아.. 가장 큰 수가 0일 때 예외처리를 해줘야 한다.

그건 정렬한 배열의 첫 번 째 원소가 0일 때이다. 예외 처리를 해주고 제출함.

통과

 

개선 아이디어

개선 아이디어는 딱히 없지만... 내 처음 아이디어대로 네 자릿수로 문제를 풀 수 있을지 궁금하다.

그래서 찾아봤더니 파이썬으로 한 사람이 있다.

dailyheumsi.tistory.com/102

[프로그래머스] 가장 큰 수

나랑 아예 똑같은 시행착오를 겪은 사람이다 ㅋㅋ

마지막에 같은 아이디어를 파이썬으로 깔쌈하게 푼 사람 코드가 있는데 진짜 짧아서 자괴감...

 

다른 사람 코드 분석

이번엔 진짜 다 나랑 똑같다. 리뷰할 게 없음.

 

 

 

 

문제 풀이라기 보단 일기를 쓰고 있는 느낌이긴 한데 그래도 내 사고 흐름을 낱낱이 적어두면 개선에 도움이 되지 않을까 한다!

아님 말고