22.10.14 / 구현, 그리디

4673 셀프 넘버 .

나의 풀이

# 셀프 넘버를 반환하는 함수
def selfNumber(number):
    sn = number
    i = 1
    while(number//i != 0):
        sn += (number//i)%10
        i *= 10
    return sn

# number를 10000까지 세면서, 그 숫자가 set에 포함되는지 확인    
snSet = set()
number = 1
for number in range(10000):
    snSet.add(selfNumber(number))
    if(number not in snSet):
        print(number)

 

더 나은 풀이

백준 알고리즘 | 4673 : 셀프 넘버 (Python / 파이썬) (tistory.com)

netural_num = set(range(1, 10001))
generated_num = set()

for i in range(1, 10001):
	for j in str(i):
    	i += int(j)
    generated_num.add(i)
    
self_num = sorted(natural_num - generated_num)
for i in self_num:
	print(i)​

str(숫자) 방식으로 자리 수를 더 쉽게 구했다.

1~10000까지 모인 숫자 집합과

셀프 넘버가 모인 숫자 집합의 여집합을 구했다.

리뷰

셀프 넘버의 집합은 순서가 중요하지 않기 때문에, 탐색 속도가 빠른(O(1)) set형으로 정리를 한다.
숫자를 str(숫자) 로 분리하면, 자리 수 마다 각 음절로 나누어 리스트화 된다.
ex) str(123) → [ '1', '2', '3' ]

 

2839 설탕 배달

나의 풀이

틀린 풀이

def greedyKg(nKg):
    kg5 = 0
    kg3 = 0
    # 그리디하게 5kg부터 정산
    while(nKg >= 5):
        nKg -= 5
        kg5 += 1
    # 나머지에 따라 3kg를 그리디하게 정산하거나 반환
    if nKg == 1 or nKg == 4:
        if kg5 != 0:
            nKg += 5
            kg5 -= 1
            while(nKg >= 3):
                nKg -= 3
                kg3 += 1
        else:
            return -1
    elif nKg == 3 :
        nKg -= 3
        kg3 += 1
    elif nKg == 2 :
        return -1
    
    return kg5 + kg3

nKg = int(input())
print(greedyKg(nKg))

그리디 방식으로 5kg짜리를 우선 배분해봤음.

나머지에 따라 3kg을 배분하거나 5kg하나를 되돌리거나 하는 방식으로 작성하려했음.

비효율적이라 판단되며, 최종적으로 틀린 풀이로 나타남.

 

더 나은 풀이

[Algorithm] 백준 2839번 설탕 배달(파이썬) (velog.io)

def greedy_kg(n_kg):
    n = 0
    while n_kg > 0:
        if n_kg % 5 == 0:
            n = n_kg//5
            return n
        # 5로 나누어지지 않고, 3으로 빼다보면 5로 나누어질때가 존재할 것이다.
        else:
            n_kg -= 3
            n += 1
    
    # 5kg과 3kg으로 뺐을시에 정확히 0이 되지 않으면, 결국 나누어 떨어지지 않는 것이다
    return -1

n_kg = int(input())
print(greedy_kg(n_kg))

리뷰

큰 숫자부터 계산하는 그리디(greedy) 문제의 특성에 너무 매달리면 안된다.
이 문제의 경우 더 작은 3kg을 어떻게 배분할 지가 더 중요했다. 
또한 나누어 떨어지지 않는 경우는, 뺀 결과가 정확히 0이 아닐때 임을 알아두자.