[백준 10610번] 그리디 알고리즘

 

 

[백준 알고리즘 - 10610번 30]

 

 

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

10610번: 30

 

(오답)

문제: 시간초과

*그래도 문제는 잘 풀었다! 시간 초과는 차차 해결해 나가면 된다.

import itertools
n=list(str(int(input())))
nums=list(map(int, map(''.join, itertools.permutations(n))))
nums.sort(reverse=True) #가장 큰 수를 찾아야 하므로 내림차순 정렬을 해준다.

for i in range(len(nums)):
    if nums[i]%30==0:
        print(nums[i])
        break
    if i==len(nums)-1:
        print(-1)

 

 

 

 

(정답1 - 시간 128 ms)

해결방법: 30의 배수 조건 (1의 자리에 들어갈 '0'을 포함 + 모든 수의 합이 3으로 나눠짐)

n=list(input())
n.sort(reverse=True)

if '0' not in n:
    print(-1)

else:
    if sum(map(int,n))%3==0:
        for i in range(len(n)):
            print(n[i],end='')

    else:
        print(-1)   

 

 

 

(정답2 - 시간 88ms)

정답1을 조금 더 간단하게 구현해서 시간을 단축시킬 수 있었다.

n=list(input())
n.sort(reverse=True)
if '0' not in n or sum(map(int,n))%3!=0:
    print(-1)
else:
    print(''.join(n)) 

 

 

 

 

<공부>

◾ 숫자를 각각 하나씩 쪼갤 때는 str로 바꿔주면 된다.

ex. (문자형) 30 → ['3', '0']

n=list(str(int(input()))) #30
print(n) #['3','0']

 

◾ for문 사용하지 않고 순열을 구하기 위해서는 itertools.permutation()을 사용하면 된다.

ex. 30 → ['30', '03']

import itertools
n=list(str(int(input())))
nums=list(map(''.join, itertools.permutations(n))) #30
print(nums) #['30','03']

 

 

◾ str 문자형에서도 sort를 하면 숫자가 정렬된다.

ex. (문자형) 2196 → ['9', '6', '2', '1']

n=list(input()) #2196
n.sort(reverse=True) #['9','6','2','1']

 

 

◾ list의 모든 원소가 숫자일 경우 sum()을 통해서 원소의 합을 구할 수 있다.

test=[1,2,3]
print(sum(test)) #6

 

◾ list의 모든 문자형 원소를 이어서 하나의 문자열로 반환하기 위해서는 ''.join()을 사용하면 된다.

test=['1','2','3']
print(''.join(test)) #123

 

 

위의 함수를 구현하다 보면

리스트의 원소가 문자형인지 숫자형인지에 따라서 결과가 달라짐을 알 수 있다.

 

 

리스트 원소를 사용할 때는 이부분을 잘 유의하자!