[BOJ] 백준 15719번 Python

백준 15719번 Python

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

 

문제

---

1부터 N - 1까지의 정수가 하나씩 정렬되지 않은 채로 저장되어 있는 어떤 수열 A가 있다.

수열 A에 임의의 정수 M(1 ≤ M ≤ N – 1)을 넣어 크기가 N인 수열로 만들었을 때,

임의의 정수 M을 찾는 프로그램을 작성하라.

 

 

입력

---

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 10,000,000)이 주어진다.

둘째 줄에 수열 A의 원소인 N개의 정수가 주어진다. 입력으로 주어지는 정수는 모두 1보다 크거나 같고,

N-1보다 작거나 같은 정수이며 문제의 답인 M을 제외하고는 모두 서로 다른 정수이다.

 

 

출력

---

M을 출력하라.

 

반응형

풀이

---

""" 정답 """

import sys
input = sys.stdin.readline

N = int(input().rstrip())
N_sum = N * (N-1) // 2

nums = input().rstrip()
nums_sum = 0
tmp = ""
for n in nums:
    if n == " ":
        nums_sum += int(tmp)
        tmp = ""
    else:
        tmp += n

nums_sum += int(tmp)

print(nums_sum - N_sum)

 

728x90

해당문제의 메모리제한과 시간제한이 Python은로 풀기에는 적합하지 않은 것 같다.

 

""" 시간 초과 """

import sys
input = sys.stdin.readline

N = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
ans = set()

for n in nums:
    if n in ans:
        print(n)
        break
    ans.add(n)

 

처음에는 다음과 같이 집합을 이용한 방식으로 접근했지만 메모리초과에 걸렸다.

 

메모리와 시간 조건을 만족하기 위해 점점 코드가 지저분해지는데...

 

""" 틀린 풀이 """

import sys
input = sys.stdin.readline

N = int(input().rstrip())
N_sum = N * (N-1) // 2

nums = input().rstrip()
nums_sum = 0
for n in nums:
    if n == " ": continue
    nums_sum += int(n)

print(nums_sum - N_sum)

 

python에서 int형은 28 bytes으로 메모리를 상당히 많이 잡아먹는다.

 

N(2 ≤ N ≤ 10,000,000) 최대 1억개의 int형을 리스트에 넣어버리면, 대략 2800MB를 사용해 버린다.

 

(문제의 메모리 제한은 256MB)

 

그래서 생각해 낸 방법이 list(map(int, input().split())) 으로 배열에 int형으로 다 넣어버리는 대신 하나씩 int형으로 변환해서 계산하는 방법이다.

 

다만, 위의 코드대로라면 두 자릿수 숫자를 계산하는 과정에서 문제가 발생한다.

 

예를 들어 12를 1과 2로 계산해 버린다.

 

이걸 해결하기 위해 tmp변수를 사용해서 " "

 

즉, 공백이 나올 때까지 문자열을 더해 공백을 만났을 때 자료형을 변환하여 nums_num에 넘기는 방식을 선택했다.

 

코드가 지저분해져서 정말 하기 싫은 방식이었지만 도저히 다른 방법이 생각이 안 난다.

 

""" 정답 """

import sys
input = sys.stdin.readline

N = int(input().rstrip())
N_sum = N * (N-1) // 2

nums = input().rstrip()
nums_sum = 0
tmp = ""
for n in nums:
    if n == " ":
        nums_sum += int(tmp)
        tmp = ""
    else:
        tmp += n

nums_sum += int(tmp)

print(nums_sum - N_sum)

 

그렇게 해서 나온 코드

 

이렇게 해도 python으로 돌리면 시간초과가 뜬다 ㅠㅠ

 

 

뭐 어쩔 수 없지 마지막 방법

 

 

PyPy3로 돌려서 solved 받아내고 덮어버렸다.

 

이후에 다른 분들 풀이 살펴보면 sys.stdin.readline 대신 sys.stdin.read 활용해서 푸는 방법도 있었다.