Programmers) Lv2 가장 큰 수

출처: https://programmers.co.kr/learn/courses/30/lessons/42746

분류: Lv2, 정렬

---

접근방식

주어진 수로 만들 수 있는 가장 큰 수를 구하는 문제입니다.

처음엔 첫 자리부터 비교하려고 했었는데요, 이렇게 하면 매우 복잡해집니다.
우선 앞 자리부터 비교하기가 어렵습니다.
길이를 알면 자리수로 나눠볼텐데 그것도 안되고
뒤집자니 뒤가 0이라면 날라갈테고
문자열로 바꿔서 한 자리씩 비교하더라도 각각의 길이가 다르기 때문에 어렵습니다.

무작정 길이가 짧다고 앞에 둘 수가 없습니다.
가령, [5, 559] 가 있다면 5559 < 5595 가 되어버립니다.
중간에 0이 껴있는 경우는 어떻게 처리 할 것이며... 
네 첫 단추를 잘못 끼웠습니다...

결국 다른 분들의 풀이를 참고하여 해결했습니다.

 

해결방법

 

제가 찾은 해결방법은 두 가지가 있습니다.

1. 앞 뒤로 붙여보기

앞에서 예를 든, [5, 559] 두 수를 비교할 때 저희는 두 수를 앞 뒤로 붙여서 만든 5559와 5595를 비교했습니다. 마찬가지로 다른 수들도 이렇게 비교하면 됩니다. 두 수를 앞, 뒤로 붙여보고 더 큰 수를 우선순위로 두는 것입니다.

let num = numbers.sorted { (a, b) -> Bool in
	return Int("\(a)\(b)")! >= Int("\(b)\(a)")!
}

 

아직 한 가지 주의사항이 남아있습니다. "모든 수가 0일 경우는  "0000..."이 아니라 "0"이 출력되어야 합니다. 
가장 손쉽게 첫 자리가 0인지 확인하는 방법이 있고, 0을 필터링해서 비어있는지 확인할 수도 있을 것 같습니다.

필터링으로 처리한 완성된 코드입니다.

func solution(_ numbers:[Int]) -> String {
    let num = numbers.sorted { (a, b) -> Bool in
        return Int("\(a)\(b)")! >= Int("\(b)\(a)")!
    }

    var result = ""
    num.forEach({ result += String($0) })
    if result.filter({ $0 != "0" }) == "" {
        return "0"
    }
    return result
}

 

2. 수를 반복해 4자리로 만들어서 비교하기

이 문제의 제한사항을 보면 0~1000 의 제한사항을 가지고 있습니다. 이에따라 4자리 수로 만들면 모든 수를 비교해볼 수 있습니다. 
5, 559 -> 5555, 5595 로 만들어서 비교합니다. 

var duplicateTuple = numbers.map ({ number -> (String, Int) in
  var n = "\(number)"
  while n.count < 4 {
  	n += "\(number)"
  }
  let range = n.startIndex...n.index(n.startIndex, offsetBy: 3)
  return ("\(n[range])", number)
}).sorted { (a, b) -> Bool in
	return Int(a.0)! > Int(b.0)!
}

 

첫번째가 0인지 확인해서 처리한 코드입니다.

func solution(_ numbers:[Int]) -> String {
    var duplicateTuple = numbers.map ({ number -> (String, Int) in
        var n = "\(number)"
        while n.count < 4 {
            n += "\(number)"
        }

        let range = n.startIndex...n.index(n.startIndex, offsetBy: 3)
        return ("\(n[range])", number)
    }).sorted { (a, b) -> Bool in
        return Int(a.0)! > Int(b.0)!
    }

    var result = ""
    duplicateTuple.forEach { result += "\($0.1)" }

    if result.first! == "0" {
        return "0"
    }

    return result
}

 

 

배운점

레벨2였지만.. 생각보다 어려웠고 풀이도 다양해 많이 얻어갈 수 있었던 문제였습니다. 

 

+ 코드 리펙토링

비어있는 let result = "" 변수를 만들고 더해가는 방식만 사용할 줄 알았었는데, 다른 분들의 코드를 참고해 reduce라는 문법을 새로 익혔습니다. 

func solution(_ numbers:[Int]) -> String {
    let num = numbers.sorted { (a, b) -> Bool in
        return Int("\(a)\(b)")! >= Int("\(b)\(a)")!
    }

    var result = num.reduce("") { "\($0)\($1)" }
    if result.filter({ $0 != "0" }) == "" {
        return "0"
    }
    return result
}

첫번째 요소를 체크하는게 더 효율적이고 간편한 방법이겠죠? 이것도 더 간편하게 사용해봅시다.

func solution(_ numbers:[Int]) -> String {
    let num = numbers.sorted { (a, b) -> Bool in
        return Int("\(a)\(b)")! >= Int("\(b)\(a)")!
    }
    
    var result = num.reduce("") { "\($0)\($1)" }
    return result.first! == "0" ? "0" : result
}

굳이 num에서 result를 거칠 필요도 없을 것 같아요

func solution(_ numbers:[Int]) -> String {
    let num = numbers.sorted { (a, b) -> Bool in
        return Int("\(a)\(b)")! >= Int("\(b)\(a)")!
    }.reduce("") { 
    	"\($0)\($1)" 
    }

    return num.first! == "0" ? "0" : num
}

 

 

회고

갈 길은 멀고도 멀고 또 멀다.