[BaekJoon] 15719번 : 중복된 숫자 (Python)

코딩 1일 1문제! 오늘의 문제는 백준 15719번 중복된 숫자입니다.

2달 전 부터 시도하였다가 메모리초과, 시간초과, 런타임에러에 시달리다 오늘 드디어 풀게 된 문제입니다.

 

15719번: 중복된 숫자

👨🏻‍💻 문제 풀이

처음에는 엄청 쉽다고 생각한 문제여서 시도한 문제인데

첫째 줄에 주어지는 수열의 크기 N(2 ≤ N ≤ 10,000,000)의 최대 크기인 천만은 생각보다 큰 숫자였습니다.

split을 하여 리스트로 만들면 메모리 초과

그냥 반복문을 돌면서 값에 접근하려하면 시간초과가 발생했습니다.

시간초과는 언어를 Python3 -> PyPy3 로 변경하는 방법으로 해결하였고메모리초과는 split을 하지않고 반복문을 돌면서 합을 구하고 가우스의 덧셈 공식을 활용하여 N까지의 합을 구해 문제를 풀었습니다.

def get_range_sum(final_number):
    return final_number * (final_number - 1) // 2

먼저 가우스의 덧셈 공식을 함수로 만들어 주었습니다.

import sys

N = int(input())
numbers = sys.stdin.read()

예제 입력은 sys의 stdin.read()를 활용했습니다.

sum_numbers = 0
temp = ""
for num in numbers:
    if num.isdigit():
        temp += num
    elif num == " ":
        sum_numbers += int(temp)
        temp = ""
            
sum_numbers += int(temp)

반복문을 돌면서 입력받은 숫자에서 공백이 아닐때 temp에 이어붙여 숫자를 만들어주고 

공백일 경우 지금까지 이어붙인 숫자들을 int형으로 변경한 뒤 sum_numbers에 더해주어

입력받은 모든 숫자들의 합을 만들어 줍니다.

sum_numbers - get_range_sum(N)

이렇게 모든 숫자를 더한 합의 결과와 1부터 N까지의 숫자의 합을 빼주면!

중복된 숫자를 알 수 있습니다.

 

전체 코드는 아래를 참고해주세요.

👨🏻‍💻 코드 ( Solution )

import sys

def get_range_sum(final_number):
    return final_number * (final_number - 1) // 2
    

def duplicate_number(N, numbers): 
    sum_numbers = 0
    temp = ""
    for num in numbers:
        if num.isdigit():
            temp += num
        elif num == " ":
            sum_numbers += int(temp)
            temp = ""
            
    sum_numbers += int(temp)
    
    return sum_numbers - get_range_sum(N)

if __name__ == "__main__":
    N = int(input())
    numbers = sys.stdin.read()
    print(duplicate_number(N, numbers))

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07