[파이썬] 프로그래머스 커뮤러닝 1주차 가장 큰 수

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

코딩테스트 연습 - 가장 큰 수

 

정렬 알고리즘을 활용하여 접근하는 문제

 

풀이계획

 - [6,10,2]가있으면 이를 조합하여 장 큰 수를 문자열로 출력해야 함

  1) 빈 문자열로 수를 초기화 -> 가장 크게 만들 수 있는 수를 고름 -> 그 수를 현재 수에 이어 붙임 -> 모든 수를 다 사용할때까지 반복함

 - 목록에서 가장큰 수를 만드는건 길이에 비례하게 됨 주어진 수의 갯수가 n에 비례한 시간을 가지게 됨

 - 이는 정렬을 활용하여 시간을 줄일 수 있음

 - 작은것으로부터 큰것, 큰것부터 작은것을 정렬하는 일이 많아지는데, 문자열의 크기가 커지는 기준을 숫자의 크기가 아닌 문자열의 크기를 크게 만드는 것을 우선해야 한다.

 - 크게 만드는 기준을 볼때, 3과 32가 있으면 332가 323보다 크므로 3이 먼저 와야된다.

 - 3과 33일때는 아무거나 와도 크게 문제가 되지 않는다.

  - 3과 34중에는 34를 먼저 넣는게 더 크기 때문에 34를 올 수 있도록 만들어야 한다.

   - 정렬을 함에 어느 기준을 가지고 수를 뽑을건지 만들고 이를 뽑으면 될 것임

  - 정렬이 된 숫자에서  숫자를 가장크게 만드는것은 해당숫자가 지속적으로 반복될때 가장 큰 값이 될것임 ->그렇다면 어느시점을 가지고 비교 해야 되는가? 

  - 문제에서는 숫자의크기는 1000이하의 수로 정해져 있음 즉 가장커도 4자리 안에서 이를 비교하면 된다는 뜻이라고 봐도 됨

 

 - 알고리즘 설계 => 구현

   1) 대소 관계 비교를 위한 기준을 마련

   2) 이것을 이용해 주어진 배열을 정렬

   3) 정렬된 배열을 이용하여 문자열 표현을 완성함

 

 

직접푼 풀이

from itertools import permutations

def solution(numbers):
    answer = list(permutations(numbers,len(numbers)))
    result = []
    for trans in answer:
        a = ""
        for num in trans:
            a += str(num)
            result.append(a)
    return max(result)

 - itertools 의 permations 즉, 조합을 사용해서 리스트에 있는 숫자들을 모두 조합하여 튜플을 만들고 이를 리스트로 만들었다. 그래서 문자열에 추가하고 이를 다 더하는 방식으로 진행을 하였는데, 모든 경우의 수를 다 계산하다보니 당연히 시간초과가 뜨게 되었다.

 

해결풀이(1)

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x: (x*4)[:4], reverse=True)
    answer = "".join(numbers)
    return answer

 

 - numbers라는 변수에 문자열로 변경해 준다.

 - numbers를 정렬하는데, lambda함수를 활용하여 x를 4번 반복하여 앞에서부터 4개까지를 슬라이스한 값을 끊어낸다

 - 기본값은 오름차순으로 되어있으므로 reverse를 통해 내림차순으로 만들어 준다.

 - 빈 문자열에 join을 활용하여 붙여주면 됨

 - 문제의 제한사항에 원소는 0이상 1000이하 라는 제약조건 시, 0이 2개 이상 있는 이런 배열이 된다면, 이를 붙인 값을 표현하기 때문에 틀리게 될 것이다. 즉 이에 대한 처리를 한번 더 해줘야 한다.

 

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x: (x*4)[:4], reverse=True)
    if numbers[0] == "0":
        answer = "0"
    else:
        answer = "".join(numbers)
    return answer

   -  if 문을 통해서 0이 들어있다면 0을 출력할 수 있도록 처리해주었다. 첫번째 원소가 0이라는 것은 크기 비교를 하였을때, 0보다 큰값이 없다는 것이므로 첫번째 값이 0일 것이다.