[코딜리티(Codility)/Lesson4/파이썬3(python3)] MissingInteger

[코딜리티(Codility)/Lesson4/파이썬3(python3)] MissingInteger

문제

This is a demo task.

Write a function:

def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].

풀이

def solution(A):
    temp_list = {*list(range(1, max(A) + 2))}
    for i in A:
        if i in temp_list:
            temp_list.remove(i)
    return min(temp_list) if temp_list and min(temp_list) > 0 else 1

설명

딜리버리히어로코리아에 서류합격을 하게 되어 처음으로 codility에서 온라인 코딩테스트를 보게 됐는데 그 데모테스트에 있는 문제였다. 원랜 프로그래머스 코딩챌린지때처럼 그냥 테스트로 자주 나오는 문제인줄만 알았는데 Lesson4에 있는 문제였다.
 아무튼 설명을 보자. 특정 수열이 주워졌을 때 수열이 차례대로 꽉 차있으면, 그러니까 공차 1인 등차수열이 주워지면(예: [1,2,3]) 그 다음 숫자인 4를 반환하면 되는 것이고, 만약에 중간에 빈 숫자가 있다면 그곳에 들어가야 할 숫자를 리턴해주고(예: [1, 3, 6, 4, 1, 2]면 5) 마지막 숫자가 음수라면 위 설명에 있는 smallest positive integer, 곧 1을 리턴하라는 의미이다.

 나는 주워지는 배열 A의 최대 수 + 1만큼의 등차수열을 튜플로 만든다음에 튜플에서 A의 요소들을 하나하나 빼고 그 튜플에서 제일 작은 수를 반환하는 방법으로 해결하였다. 그리고 만약 끝나는 수가 음수라면 튜플이 만들어지지 않기 때문에 튜플이 없으면 1을 리턴하는 식으로 음수에 대한 케이스도 적용하였다.

아 그리고 코딜리티는 재미있게도

이런식으로 성적표 비슷하게 결과가 나온다. 자신이 어느부분에 약한지 제대로 파악할 수 있는 방법이 되겠지 싶다.

딜리버리 히어로 코리아 코딩테스트 후기

딜리버리히어로코리아의 코딩테스트문제는 조금 '독특'했다. 일단 지문이 영어라서 해석하는 데 시간을 꽤 소모하기도 했는데 이해하고 나니 별로 어렵진 않았다. 하지만 음... 분위기 파악이 조금 늦었달까.

 여러가지 알고리즘 풀이 사이트를 예로 들자면 hackerank와 programmer는 비슷하게 '함수의 반환값'으로 답을 제공해야 하고, 백준은 출력되는 형태 그대로를 정답으로 인식하는 등 각각 사이트 저마다의 인식방식이 있지만 이번에 봤던 테스트의 형태와 돌아가는 구조가 완전 처음보는 모습이어가지고 "이걸 어떻게 풀어야 하냐"로 시간을 소모한 것이 아니라 "이걸 어떻게 써야되나"로 시간을 소모했다. 굳이 비교하자면 hackerank에서 가끔 봐왔던 형태들과 비슷했다. 물론 자세한 건 저작권 침해요소가 있어 쓰진 못하지만 음... 이런 식으로도 문제가 나오는구나 하는 밑천으로 삼아야겠더라. 첫번째 문제는 풀었지만 다음문제를 들어갈 때 이미 타임아웃이 확정되겠구나 싶어서 깔끔하게 포기하고 밥먹으러 갔다. 다음에 이런식의 문제를 만난다면 가볍게 풀 수 있을 것 같다.