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
나도 간결하고, 직관적인 코드를 작성하기 위해.
누가 봐도 이해하기 쉬운 코드를 작성하기 위해 노력해야겠다.
