BOJ 16496 큰 수 만들기 Python

BOJ 그리디,정렬
문제 링크 : https://www.acmicpc.net/problem/16496

양의 정수로 입력받아서 리스트 안에 요소들을 하나씩 확인하여 이어붙였을 때 가장 큰 수를 만드는 문제.

접근 1

1. 정수를 크게 만들어 주기 위해 가능한 많은 자릿수를 채워주고
   각 자릿수마다 제일 높은 수를 골라준다 (9 < 10, 10 < 99)
   근데 해당 문제에서는 리스트의 요소들로 정수를 만들어야 되므로 자릿수는 고정이기에
   만들어진 정수 중에서 각 자릿수마다 제일 높은 정수가 오게 정렬을 시켜준다

코드1

import sys
input = sys.stdin.readline
n = int(input())
lst = input().split()
q = max(map(lambda x : len(x),lst))
lst.sort(key= lambda x : -int(x.ljust(q,'0')))
a = int(''.join(lst))
if a > 0:
    print(a)
else:
    print(0)

접근2

1. 리스트 요소의 정수끼리 단순 비교로는 풀 수 없음
   케이스 1
   3
   1,110,10

위와 같은 경우 110 10 1 순으로 정렬이 되어 110101이 출력이 될 텐데
3개의 수로 만들 수 있는 제일 큰 수는 1 110 10으로 정렬하여 111010을 만드는 것이다

그래서 자릿수를 맞춰서 비교해 줬지만 1과 10이 100으로 동일한 값이 와 우선순위가 같아지기 때문에 해당 조건으로는 이 문제를 해결하기엔 수정이 필요하다

그래서 정렬 조건을 찾아보려 했지만 입력 개수가 그렇게 많지 않고 정수 범위도 평범해 보이기 때문에 위의 정렬 조건에서 우선순위가 같은 수들은 서로 인접해 있을 거고 만들어지는 과정에서 누적된 정수에 앞이나 뒤에 붙으면 되니까 리스트를 순회하며 정수를 만들 때 앞에 붙였을 때와 뒤에 붙였을 때를 비교해 더 큰값 이를 붙여주는 방식으로 보안해 봤다

코드2

import sys
input = sys.stdin.readline

n = int(input())

lst = input().split()
q = max(map(lambda x : len(x),lst))
lst.sort(key= lambda x : int(x.ljust(q,'0')) ,reverse=True    )
ans = ""
for x in lst:
    ans = max(x+ans,ans+x)
if int(ans) == 0:
    print(0)
else:
    print(ans)  

여러 문제 구경하다가 플레 문제인데 할 수 있을 거 같아서 해봤는데 의외로 빨리 푼 것 같다 그리고

다른 사람의 코드를 보려고 파이썬으로 필터 걸어서 구경하다가 내 제출이 파이썬 코드 중 9등으로 나왔다 첫 플레 문제로 1페이지에 내 아이디가 보이니 기분이 새롭다