FirstDuplicate

1984·2021년 12월 4일
0

Algorithm

목록 보기
2/8

CodeSignal의 Interview Practice - Array 부문 문제입니다.


Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.


Example

For a = [2, 1, 3, 5, 3, 2], the output should be solution(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

For a = [2, 2], the output should be solution(a) = 2;

For a = [2, 4, 3, 5, 1], the output should be solution(a) = -1.


Input/Output

[execution time limit] 4 seconds (py3)

[input] array.integer a

Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.

[output] integer

The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.


요약하자면, 중복된 숫자 중 두 번째 숫자의 index가 가장 작은 것을 return 해주면 되는 문제이다.

# 없다면 return -1

처음으로 짠 코드 :

def solution(a):
    min_value = 10000000
    result =0
    
    for num in range (len(a)) :
        
        if num >= min_value :	# 가지치기를 위해
            break
            
        for compare in range (num + 1, min(min_value, len(a))) : # 가지치기를 위해

            if a[num] == a[compare] :
                
                if (compare) < min_value :
                    min_value = compare
                    result = a[num]

    if min_value == 10000000 :
        return -1
        
    else :
        return result

-> 반복문이 2개가 있다 보니 시간 초과가 발생했다.

  • 최대한 시간을 줄여주기 위해 break 문과 반복문에 min(min_value, len(a))를 넣어주었는데 유의미한 시간 변화는 일어나지 않은 것 같다.

  • 근본적인 해결책은 반복문의 개수를 2개에서 1개로 줄이는 것이라고 생각했다.

몇 시간을 투자해도 풀리지 않아 결국 solution을 찾아봤다.


Solution

1. 배열의 index와 내용을 이용했다

def solution(a):
    for i in a:
        a[abs(i)-1] *= -1
        if a[abs(i)-1] > 0:
            return abs(i)
    return -1

한눈에 이해하기 어려워서 예를 들어 보았다.

예) :
a = [2, 1, 3, 5, 3, 1] 이라면

1 : a = [2, -1, 3, 5, 3, 1]
2 : a = [-2, -1, 3, 5, 3, 1]
3 : a = [-2, -1, -3, 5, 3, 1]
4 : a = [-2, -1, -3, 5, -3, 1]
5 : a[2] *= -1 > 0 보다 크므로 return 3 이다.


단순히 겹치는 숫자의 index를 -로 기록한다.
해당 숫자가 두 번 나와 +값이 된다면 그 값을 return

2. set() 자료구조를 이용했다.

def solution(a):
    mySet=set()
    for el in a:
        if el in mySet:
            return el
        mySet.add(el)
    return -1

굉장히 직관적이다.
중복되지 않는 집합 set()에 원소를 넣고, 이미 있다면 그 숫자를 return
아니라면 return -1


나도 간결하고, 직관적인 코드를 작성하기 위해.
누가 봐도 이해하기 쉬운 코드를 작성하기 위해 노력해야겠다.

profile
42seoul hyojeong / 더하기보다 곱하기로 성장하고 싶습니다.

0개의 댓글