[알고리즘/정렬] 프로그래머스-가장 큰 수

✍🏻 해당 문제를 풀면서 알아야될 개념 

숫자 문자열 대소 비교 

숫자 문자열의 대소관계는 문자열의 첫 글자부터 비교하여 결정된다. 숫자 문자열을 비교할 때는 다음과 같은 규칙이 적용된다. 

• 첫 번째 글자부터 비교한다. 
• 두 문자열의 첫 번째 글자가 다를 경우, 해당 글자의 아스키코드 값에 따라 비교한다. 
  • 아스키코드 값이 낮을수록 작은 값으로 간주된다. 
  • 예를 들어 "652"는 "3434" 보다 크다.  
• 만일 두 문자열의 첫번째 글자가 동일한 경우, 두번째 글자를 비교하고 동일한 글자일 경우에도 그 다음 문자를 비교한다. 
• 이렇게 문자열의 모든 글자를 비교하여 두 문자열 중 하나가 먼저 끝나면, 길이가 짧은 문자열이 작은 값으로 간주된다. 
  • "123"은 "1234"보다 작다. 

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

프로그래머스

 

📌문제

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

 

📌 풀이방법 

 

1. 가장 처음 시도했던 풀이 > permutations(순열)을 이용하여 가장 큰 수 출력 

 

처음에는 순열을 이용하여 나올 수 있는 숫자의 모든 조합을 구한 후, 

sort 함수를 통해 큰 수대로 정렬하고 , 가장 큰 숫자를 출력하는 코드 작성 

⇒ "시간초과로 인해 실패" 

#순열 이용 => 시간초과.. 
from itertools import permutations
def solution(numbers):
     answer_list = []
    
     res_list  = list(permutations(numbers , len(numbers)))
    
     for res in res_list :
         answer_list.append(''.join(map(str,res))) 
     answer_list = sorted(set(answer_list) , reverse = True)
     answer = answer_list[0]
     return answer

 

2 . 다른 방법으로 시도 > 도저히 생각이 안나서 블로그 유랑을 하며 힌트를 찾으러 떠났다..🎒

• 숫자의 앞자리 수를 비교하여 대소 관계 파악한다. 
• 만일 앞자리수가 같을 경우 자릿수를 똑같이 해서 처리한다.
• ex) 3 , 30 , 34 이 있을 때는 333, 3030,3434로 처리하여 대소비교를 하면 되겠다고 생각했다. 

이 문제에서 제한 조건은 0이상 1000이하라고 했기에, 모든 원소가 3자리 이상이 될 수 있도록 문자열인 각 원소에 3을 곱하여 대소비교를 해준다. 

⭐ sorted(['3','30']) 은 ['30' , '3'] 이 되지만, sorted(['333','303030']) 은 [ '333' , '303030'] 이 된다.

 

999 와 343434 를 비교할 수 있는 이유는 "999" 와 "343" 까지만 비교되고 나머지는 무시되기 때문에 1000이상이 넘어가는 거는 신경을 안써도 된다. 

 

해당 문제로 풀었을 때, 1문제에서 실패가 나서찾아나섰다.. 게시판을 통해 살펴보니 예를 들어 [0,0,0,0] 일 경우에는 정답이 '0000'으로 나오므로 int 형으로 바꾼다음 str로 바꿔주는 코드 추가했다.  

def solution(numbers) :
	numbers = list(map(str , numbers)) 
    
    #각 숫자의 3을 곱한 기준대로 정렬수행 
    numbers.sort(key = lambda x : x*3 , reverse = True) 
    
    #문자열하나로 합쳐주기 
    answer = ''.join(numbers) 
    #예를 들어 [0,0,0,0] 등등 0으로만 이루어진 경우를 고려해 int 변환 후 다시 str 변환 
    answer = str(int(answer))  
    
    return answer

 

 

정말 파이썬스러운 코드이지 않나.. 

 

📌느낀점 

당연히 정렬 문제라고 해서 생각보다 쉽게 풀 것이라 예상했지만, Lv1 이외 문제들은 난항을 겪었다.. ㅎㅎ.. 시간복잡도를 고려하지 않은 적이 많았는데 이번 문제에서 완전탐색적인 방법으로 풀다가 오류를 맞이했다. 다음주 특강에서 시간복잡도에 대한 강의를 할 예정이니 주의깊게 들어야겠다. 

---

✍🏻 Reference 

https://dev-astra.tistory.com/455

[Programmers-42746][Python] 가장 큰 수