7/6 코테 일지 (중요! set 자료형과 원소 검색, 배열 안 배열 sorting, sort key)

set 자료형과 원소 검색

10815 숫자 카드 

 

해당 문제를 풀기 위해 binary search를 사용하였으며 통과하였다. 하지만 시간이 꽤나 오래 걸렸고 다른 코드들을 보아하니 나보다 훨씬 적게 걸린 제출들이 많이 보였다. 

import sys
n = int(sys.stdin.readline().rstrip())
n_array = list(map(int,sys.stdin.readline().rstrip().split(' ')))
m = int(sys.stdin.readline().rstrip())
m_array = list(map(int,sys.stdin.readline().rstrip().split(' ')))

n_array.sort()
ans = [0 for _ in range(len(m_array))]
for i,m in enumerate(m_array):
    l,r = 0,len(n_array)-1
    while (l<=r) :
        mid = (l+r) // 2
        if n_array[mid] > m : 
            r = mid - 1
        elif n_array[mid] < m :
            l = mid + 1
        else :
            ans[i] = 1 
            break

print(*ans)

 

다음은 그 코드의 예시다. 보다시피 binary search를 구현하지 않고 단순히 if문을 사용하였는데 나보다 시간은 훨씬 적게 걸렸다.

import sys

n=int(input())
n1=set(map(int,sys.stdin.readline().split()))

m=int(input())
m1=list(map(int,sys.stdin.readline().split()))


for i in m1:
    if i in n1:
        print(1,end=' ')
    else:
        print(0,end=' ')

 

어떻게 그게 가능한가 싶어서 코드를 보다 보니 바로 search하는 수의 리스트를 배열로 받지 않고 set로 받았다. 어차피 문제에서 중복되는 수가 없다 하여서 과연 다른점이 뭐가 있을까에 대해 공부를 해보니 set를 사용하면 search에서 굉장한 이점이 있다. 바로 원소 검색을 O(1)으로 할 수 있다는 것이다. 그것이 어떻게 가능할까?

n1=set(map(int,sys.stdin.readline().split()))

 

그것은 바로 set가 원소를 저장할 때 기존의 리스트처럼 앞, 뒤에 원소를 넣어주는 것이 아닌 해시함수를 거친 해시로 변경 후 저장소에 넣어준다는 것이다. 즉 해당값이 존재하는지에 대해서는 단순히 해시테이블을 사용해서 O(1)으로 가능해지는 것이다.

 

 

 

배열 안 배열 sorting, sort 메서드의 key 매개변수 

1946 신입사원

array = []
    for _ in range(n) : 
        array.append(list(map(int,sys.stdin.readline().rstrip().split(' '))))
array.sort()

다음 과 같은 배열 안 배열이 있고 sorting을 하면 첫 번째 element를 기준으로 sorting 한다. 

그렇다면 두 번째 element를 기준으로 sorting 하고 싶으면?

import sys

array = []
n = int(sys.stdin.readline().rstrip())  # n 값을 입력 받음
for _ in range(n):
    array.append(list(map(int, sys.stdin.readline().rstrip().split(' '))))
array.sort(key=lambda x: x[1])

다음 과 같이 sort 메서드의 key 매개변수를 사용해야 한다. key 매개변수는 함수를 받아 리스트의 각 요소를 인자로 받아 정렬 기준이 되는 값을 반환한다.

람다 함수를 사용하지 않으면 다음과 같다.

def sort_key(x):
    return x[1]

array.sort(key=sort_key)

 

 

그 외 

10817 세 수 

브론즈 3 문제 가볍게 해결

import sys
a = list(map(int,sys.stdin.readline().rstrip().split(' ')))
a.sort()
print(a[1])