[백준] 19496 큰 수 만들기(그리디) - Python

https://www.acmicpc.net/problem/16496

16496번: 큰 수 만들기

 

n = int(input())
lst = input().split()
cnt = 0
for i in range(n-1, 0, -1): # 문자열로 붙여본다음 버블정렬 !
    for j in range(i):
        if int(lst[j] + lst[j+1]) > int(lst[j+1] + lst[j]):
            pass
        else:
            lst[j], lst[j+1] = lst[j+1], lst[j]

for l in lst: # 다 0일 경우 0 하나만 출력
    if l == "0":
        cnt += 1

if cnt == n:
    print(0)
else:
    print(''.join(lst))

 

- 접근방식: 각 숫자들을 문자열로 받은 다음 첫 번째 원소에 두 번째 원소를 앞에 붙였을 경우, 뒤에 붙였을 경우 이 두 가지를 비교한 후 두 번째 원소를 앞에 붙이는게 더 큰 경우에는 두 개의 원소 자리 바꾸기. 만약 뒤에 붙였을 경우 더 크면 그대루 두기. 이런식으로 끝 원소까지 버블정렬 후 출력 !

- 느낀점: 문제 꼼꼼히 잘 읽기. 0이 여러 개면 0 하나만 출력 해야하는 것을 처음에 못봐서 한 번 틀렸다.. 또한 그리디 문제는 계속 발상전환 해보기, 버블정렬 까먹지 않기 !