[Codility] Lesson4 MissingInteger 풀이 Python
OnlineJudge

[Codility] Lesson4 MissingInteger 풀이 Python

반응형

 

문제로이동

 

MissingInteger coding task - Learn to Code - Codility

Find the smallest positive integer that does not occur in a given sequence.

app.codility.com


목차

     


     


    문제 설명

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

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

     

    [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

    #
    반응형