백준 4673 : 집합(set) 활용

문제

https://www.acmicpc.net/problem/4673
33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51,
다음 수는 51 + 5 + 1 = 57이다.
생성자가 없는 숫자를 셀프 넘버라고 한다.

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

해결 방안 1 : 단순 반복문

1. 이중 반복문을 돌며 j의 셀프 넘버를 구한다.
2. 구한 셀프 넘버가 i와 일치할 경우 flag를 1로 만들고 break 한다.
3. flag가 0일 경우에만 i를 출력한다.

해결방안 1 코드

for i in range(1,10001):
    flag = 0
    total = 0

    for j in range(1,i+1):
        if j < 10:
            total = j * 2
        elif j < 100:
            total = j + j // 10 + j % 10
        elif j < 1000:
            total = j + j // 100 + (j % 100 // 10) + j % 10
        else:
            total = j + j // 1000 + (j % 1000 // 100) + (j % 100 // 10) + j % 10

        if total == i:
            flag = 1
            break

    if flag == 0:
        print(i)

이렇게 열심히 했는데 내가 제일 싫어하는 시간초과 오류가 났다..ㅜㅠㅠ

결국 구글링을 통해 집합을 사용한다는 것을 확인하고 집합에 대해 간단히 공부한 후에 다시 해결했다.

해결 방안 2 : 집합 활용

1. 전체 수를 넣는 집합과 삭제할 집합을 만든다.
2. 1부터 10000까지 돌면서 각 수들의 셀프 넘버를 삭제할 집합에 추가한다.
3. 전체 집합에서 삭제할 집합을 뺀다.
4. 정렬해서 출력

해결방안 2 코드

arr = set(range(1,10001))   # 1 ~ 10000 전체 집합
remove = set()              # 삭제할 집합 

for i in range (1,10001):   # i = 234
    for j in str(i):        # j : 2, 3, 4
        i = i + int(j)      # i = 234 + 2 + 3 + 4 = 244
    remove.add(i)           # 삭제할 집합에 추가
    
arr = arr - remove          # 전체에서 삭제할 집합 빼기

for i in sorted(arr):       # 정렬해서 출력
    print(i)

---

파이썬 집합!

특징 정리 & 연산

1. 내부 원소는 다양한 값을 가질 수 있지만, 중복되는 값은 가질수 없다.
2. s = set() 과 같이 선언한다.
   
   
3. 합집합 : s1 | s2
4. 교집합 : s1 & s2
5. 차집합 : s1 - s2
   
   
6. 원소 추가 : s.add(50) - add 메소드를 사용
7. 원소 제거 :
   s.remove(20) - remove 메소드 : 없으면 KeyError 발생
   s.discard(20) - discard 메소드 : 없어도 에러발생하지 않음

보다 자세한 설명은 아래 링크에서 확인할 수 있다 :D
https://wikidocs.net/16044

---

예전에 c언어로 풀어봤던 문제라 쉽게 봤다가 세게 맞은 문제다;;
파이썬을 좀 더 잘 다루고 싶다:D 👍👍