정렬 - 가장 큰 수

아래 문제는 프로그래머스에서 제공하는 코딩테스트 > 정렬 > 가장 큰 수 (고득점 Kit)의 문제입니다🧑🏻‍💻

 

문제 제시

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

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

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

제한 사항

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

입출력 예

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

문제 해결

import Foundation

func solution(_ numbers:[Int]) -> String {
    let result = numbers.map{ String($0) }.sorted{ $0 + $1 > $1 + $0 }
    
    if result[0] == "0" {
        return "0"
    }
    return result.joined()
}

사용된 개념

 - 배열

 - 정렬

 - map / sorted / joined

 

문제 뒷담화

이번 문제는 생각하자면 쉽고 생각이 안나면 한도 끝도 없는 문제였습니다. (모든 코테 문제가 그렇겠지만...?!)

우선 각 수를 문자열로 매핑해줍니다.

그 후 각 문자열을 연결하여 큰 수를 비교하여 탐색하고 큰 인덱스부터 정렬해줍니다.

또한 첫 인덱스가 0 이라면 모든 수가 0이 들어온 경우이니 이럴때는 0을 반환 할 수 있도록 해줍니다. (그렇지 않다면 문자열이 00000 이런식으로 들어올 수 있습니다.)

그 후 마지막으로 문자열이 담긴 결과 배열을 조인을 통해 합쳐줍니다.

여기서 배웠던 점은 정렬을 할때 저렇게 조건을 세워주면 알아서 전체를 탐색하고 비교해줍니다.

그리고, sort와 sorted의 차이는 sort는 기존 배열을 정렬되게 변경시키고 sorted는 기존을 변경시키지 않음으로 변수 생성이 필요합니다.

joined은 인덱스들을 합쳐줍니다. 만약 어떤 기준으로 합쳐주는 중간 문자를 넣고 싶으면 seperator 옵션을 사용합니다.

마지막으로, 위 경우 전 아래와 같이 정렬을 먼저하고 매핑을 해줬는데, 그럴경우 각 비교할때 문자로 바꾸고 다시 정수로 변환해서 비교함으로 탐색 시간이 더 오래걸립니다.

추가로, 강제추출을 함으로 더 안전하지 않은 코드였습니다.

import Foundation

func solution(_ numbers:[Int]) -> String {
    let result = numbers.sorted{ Int("\($0)\($1)")! > Int("\($1)\($0)")! }.map{String($0)}
    
    if result[0] == "0" {
        return "0"
    }
    
    return result.joined()
}

 

 

[참고자료]

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