2021년 1학기 알고리즘응용 8주차

• 8주차 과제 - 가장 큰 수(정렬)

• 사용 언어 : python

• 해결 날짜 : 2021-04-30

• 느낀점 및 해결 과정 :

  • 리스트에서 가장 큰 값의 길이를 저장한다
  • sorted 함수와 lambda 함수를 활용하여 리스트의 원소들을 str로 형변환하여 가장 큰 수의 자리 수 만큼 맞춰주어 비교를 통해 내림차순으로 정렬한다.

  • 크기 순으로 정렬된 리스트의 원소들을 join 함수를 사용해 붙여준다.

  • 시간 복잡도 :

    • max : 전체를 한 번씩 탐색하므로 O(N), len : O(1)
    • sorted : sort 함수와 같으므로 O(NlogN)
    • 따라서 O(N*1 + NlogN) = O(NlogN) 의 시간 복잡도를 갖는다.
  • 코드

  N = int(input()) # 수의 개수 입력
  # N개의 수를 입력 받아 리스트에 넣음
  numList = list(map(int, input().split()))
  
  # 리스트에서 가장 큰 값의 길이를 저장, 숫자의 길이가 주어지지 않았기 때문에 쓰임
  maxNumLen = len(str(max(numList)))
  
  # numList를 내림차순으로 정렬하되, str로 형변환하여 아까 저장한 큰 값의 길이만큼 곱한 것을 비교하여 정렬
  # 이유는 가장 큰 값이 991로 자리 수가 3, 가장 작은 값이 9로 자리수가 1이라고 하면
  # 자리 수 만큼 곱해주었기 때문에 str형인 991991991과 999를 비교하면 999가 더 크게 됨을 알 수 있음
  numList = sorted(numList, key=lambda x: str(x)*maxNumLen, reverse=True)
  
  # 정렬된 값을 join을 사용해 붙여줌
  answer = int("".join(map(str, numList)))
  
  print(answer)