[Codility] Lesson4 MissingInteger 풀이 Python

 

문제로이동

MissingInteger coding task - Learn to Code - Codility

---

목차

 

---

 

---

문제 설명

양수인 정수 중에서 배열에 없는 가장 작은 값을 출력하는 문제입니다.

너무 간단한 문제라 바로 예제부터 보겠습니다.

 

[1,2,3]의 경우 배열에 없는 가장 작은 정수인 4가 나옵니다.

[-1,-3]의 경우 배열에 없는 가장 작은 정수인 1이 나옵니다.

[1,3,6,4,1,2]의 경우 배열에 없는 가장 작은 정수인 5가 나옵니다.

접근 방법

어쨌든 모든 배열을 탐색해야 하므로 O(N)의 시간 복잡도를 갖습니다.

입력 범위를 보면 음수까지도 들어오지만, 출력하는 것은 양수이므로 음수는 신경 쓰지 않습니다.(필요 없습니다)

양수인 입력값만 visited로 체크해준 뒤 1부터 N까지 순차적인 탐색을 해줍니다.

---

소스 코드

Python

def solution(A):
    visited = [0]*1000001
    for i in A:
        if i>0:#음수는 생각하지 않는다
            visited[i]=1
    for i in range(1,len(visited)):
        if not visited[i]:
            return i

print(solution([1,2,3]))
print(solution([-1,-3]))
print(solution([1,3,6,4,1,2]))
print(solution([1000000,2,1]))

---

Java8

#