프로그래머스 가장 큰 수 (C#)

프로그래머스

숫자를 입력 배열로 입력 받을 때, 숫자들을 조합해서 만들 수 있는 가장 큰 수를 구해주세요.

ex) [3, 30, 34, 5, 9] => "9534330"

 

 

풀이방법

해당 문제는 정렬 알고리즘 문제입니다.

일반적인 정렬과는 다르게 두 원소를 이어붙였을 때, 어떤게 더 큰지에 따라 우선순위를 결정합니다.

public bool Comp(int a, int b)
{        
    int A = int.Parse(a.ToString() + b.ToString());
    int B = int.Parse(b.ToString() + a.ToString());

    return A > B;
}

 

위의 함수를 통해 정렬을 마친 후

순회하여 이어붙여주면 됩니다. 

 

이때, numbers의 원소가 0만 있는 경우가 있습니다.

ex) [0, 0, 0, 0, 0, 0, 0, 0];

이런 경우에는 0을 반환해야하지만 이어붙이게 되면 0이 아니게 되버립니다.

 

예외 처리를 추가하여 정답을 완성해주면 됩니다.

 

정답 코드 -  Array.Sort 사용

public string solution(int[] numbers) 
{
    StringBuilder sb = new StringBuilder();

    string answer = "";
    Array.Sort(numbers, (x, y) => string.Compare(y.ToString()+x.ToString(),x.ToString()+y.ToString()));

    foreach (int n in numbers)
        sb.Append(n.ToString());

    answer = sb.ToString();

    foreach (var item in answer)
        if (item != '0')
            return answer;

    return "0";
}

 

 

Prioriy Queue 사용

using System;
using System.Collections.Generic;
using System.Text;

public class PriorityQueue
{
    public void Add(int num)
    {
        arr[size++] = num;
        int cur = size-1;
        
        while (cur > 0)
        {
            int parent = (cur -1) / 2;
            if (Comp(arr[cur], arr[parent]))
            {
                int temp = arr[cur];
                arr[cur] = arr[parent];
                arr[parent] = temp;
                cur = parent;
            }
            else
                break;
        }
    }
    
    public int Pop()
    {
        int ret = arr[0];
        arr[0] = arr[--size];
        
        int cur = 0;
        while (cur < size)
        {
            int left = cur * 2 + 1;
            int right = left+1;
            
            if (left >= size)
                break;
            
            if (right < size && Comp(arr[right], arr[left]))
                left = right;
                
            if (Comp(arr[left], arr[cur]))
            {
                int temp = arr[cur];
                arr[cur] = arr[left];
                arr[left] = temp;
                cur = left;
            }
            else
                break;
        }
        return ret;
    }
    
    private bool Comp(int a, int b)
    {        
        int A = int.Parse(a.ToString() + b.ToString());
        int B = int.Parse(b.ToString() + a.ToString());
        
        return A > B;
    }
    
    public bool isEmpty => size == 0;
    
    int size = 0;
    int[] arr = new int[200001];
}

public class Solution 
{
    public string solution(int[] numbers) 
    {
        StringBuilder sb = new StringBuilder();
        PriorityQueue pq = new PriorityQueue();
        string answer = "";
        
        foreach (int n in numbers)
            pq.Add(n); 
        
        while (!pq.isEmpty)
            sb.Append(pq.Pop().ToString());
        
        answer = sb.ToString();

        foreach (var item in answer)
            if (item != '0')
                return answer;

        return "0";
    }
}

 

 

 

 

PQ

 

 

Array.Sort