[BOF/Python] 4673번, 셀프 넘버

📜 문제

BOF 4673번, 셀프 넘버

🔥난이도🔥

1차 풀이 ⭕

1 ~ 10000까지 정수와 각 정수의 자릿수를 더했을 때 나오지 않는 수(셀프 넘버)를 구하는 문제다.

1 ~ 10000까지 각 정수의 계산값을 1 ~ 10000까지의 수를 저장한 리스트에서 제외하는 방식으로 문제를 풀었다.

단순하게 이중 for 문을 사용하고, 조건문이 들어가 시간이 길게 나온 거 같다…😭

def seq(max: int):
    '''n과 n의 각 자릿수를 더하는 함수'''
    
    # 셀프 넘버를 찾기 위한 리스트
    self_no = list(range(1, max))
    
    for i in range(1, max):
        seq_no = i  # 더한 결과값

        # 각 자릿수를 더한다.
        for j in str(i):
            seq_no += int(j)

        # 더한 결과값이 있으면 리스트에서 제거
        if seq_no in self_no:
            self_no.remove(seq_no)
    
    # 셀프 넘버 출력
    for no in self_no:
        print(no)

seq(10000)

2차 풀이(개선) ⭕

시간을 줄이기 위해 더 효율적인 방법을 찾았다.

차집합을 이용해 한 번에 셀프 넘버를 찾아내는 방법이다.

코드도 간단해지고, 시간이 232 ms -> 76 ms 로 약 1/3 줄었다!

다양한 사고방식으로 문제에 접근할 수 있도록 노력해야겠다!

def seq(max: int):
    '''셀프 넘버를 찾는 함수'''

    # 1 ~ max - 1 까지의 range
    max_rang = range(1, max)

    # n과 n의 각 자릿수를 더한 결과 리스트 (리스트 내포 사용)
    seq_no = [i + sum(map(int, str(i))) for i in max_rang]
    
    # 집합 자료형으로 변환 후 차집합 계산
    # 1 ~ max 리스트에서 n과 n의 각 자릿수를 더한 결과를 제외
    self_no = sorted(set(max_rang) - set(seq_no))

    # 셀프 넘버 출력
    for i in self_no:
        print(i)

seq(10000)

보충 🤓

리스트 내포란?

for 문의 결과를 리스트로 반환해주는 기능으로 사용법은 아래와 같으며 if 문은 선택이다.

if 문을 사용하면 특정 조건을 만족하는 값만 리스트로 반환할 수 있다!

[표현식 for 항목 in iterable if 조건]

# 리스트의 각 항목에 곱한 결과를 다른 리스트에 담기
a = [1, 2, 3, 4, 5]
result = [num * 3 for num in a]
print(result)
# 결과
[3, 6, 9, 12, 15]

# 짝수만 3을 곱하여 담고 싶을 경우
a = [1, 2, 3, 4, 5]
result = [num * 3 for num in a if num % 2 == 0]
print(result)
#결과
[6, 12]

현재 티어 🥉