경력 직원 고용하기
경력 직원 고용하기
구현하는데는 성공했지만, for문을 3개나 들여써서 time limited가 떴다.
for문을 3개나 들여써서 어떻게 하면 줄일 수 있을지 많이 고민한 문제이다.
문제
어느 IT 회사에서 경력 직원을 고용하려고 한다. 이 회사에는 모바일 앱 개발, 3D 그래픽스, C/C++, 데이터 베이스, 서버 보안 등 M개의 기술을 필요로 하며, 지원자 N명 중 M개의 기술을 모두 커버할 수 있는 최소한의 인원을 채용하려고 한다. 이때 최소한에 가까운 인원에 대한 값을 Greedy한 방법으로 출력해보자.
입력
첫번째 줄에는 지원자의 수 N과 회사에서 요구하는 기술의 종류 M개가 공백으로 구분되어 입력된다. (1≤N≤ 1000,1≤ M ≤ 1000) 두번째 줄부터 N개의 줄에는 지원자별로 가진 기술 경력을 공백으로 구분하여 입력하며 최대 M개 입력 가능하다. (기술 경력 사항은 정수로 입력된다.) 두번째 줄에 입력되는 지원자 경력 사항부터 차례대로 지원 번호가 매겨지며, 1번부터 시작한다.
출력
요구된 기술 경력을 모두 커버하는 최소 인원에 근사한 인원들의 지원 번호를 공백으로 구분하여, 오름차순으로 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Sample Input 1
3 5
1 2 3 4
3 4 5
2 3 4 5
Sample Output 1
1 2
Sample Input 2
5 10
1 2 3 4
2 4 5 7 8
3 5 6
1 2
6 8 9 10
Sample Output 2
1 2 5
Sample Input 3
7 16
1 2 3 10 15
4 5 8
6 9 7 16
12 13 14 15
4 8 11
5 6 7
4 3 8 10 14 16
Sample Output 3
1 2 3 4 5 7
잘못 짠 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
N, M = map(int, input().split())
emp = []
output= []
for i in range(N): # 각 직원들의 기술들을 입력받아 0-setting 해주고 emp에 배열을 넣어주기
arr = list(map(int, input().split()))
for j in range(len(arr)):
arr[j] -= 1
emp.append(arr)
# U = list(range(M))로 대체 가능
U = []
for i in range(M): # 회사에서 필요한 기술들을 U에 넣어주기
U.append(int(i))
while U:
max_emp = -1 # 기술이 가장 많은 직원의 인덱스
count_result = 0 # 회사에서 필요한 기술들과 고용할 직원의 기술들의 교집합의 개수
for i in range(N):
count = 0
for j in emp[i]:
for k in U:
if j == k:
count += 1 # 시간복잡도가 너무 안좋음 : O(N*U^2)
if count > count_result:
count_result = count
max_emp = i
for i in range(len(emp[max_emp])): # 기술이 가장 많은 직원의 기술을 U에서 빼기
for skill in emp[max_emp]:
if skill in U:
U.remove(skill)
emp[max_emp] = []
output.append(max_emp)
for i in range(len(output)):
output[i] += 1
output.sort()
print(' '.join(str(x) for x in output))
이 문제를 효율적으로 풀기 위해 set() 자료형을 알아야했다.
set() 자료형의 특징
- 요소 중복 안됨
- 요소 순서 없음
- 변경 가능
- 집합 연산 지원(중요)
set 관련 메소드
clear(): 집합의 모든 요소를 제거하여 빈 집합을 만듭니다.copy(): 집합의 복사본을 반환합니다.union(other_set): 두 집합의 합집합을 반환합니다.intersection(other_set): 두 집합의 교집합을 반환합니다.difference(other_set): 다른 집합과의 차집합을 반환합니다.- 등등
여기서 intersection과 difference를 이용하면 아주 효율적으로 코드를 짤 수 있다.
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
N, M = map(int, input().split())
emp = []
output = []
# 0부터인 것들 감안해서 setting
for i in range(N):
arr = set(map(lambda x: int(x) - 1, input().split()))
emp.append(arr)
# U setting
U = set(range(M))
while U:
max_skill_count = 0
max_emp = -1 # 기술이 가장 많은 직원의 인덱스
for i in range(N):
count = len(emp[i].intersection(U)) # 교집합의 개수를 count에 넣어준다
if count > max_skill_count:
max_skill_count = count
max_emp = i
U.difference_update(emp[max_emp]) # difference_update로 해당 원소들을 U에서 제거
output.append(max_emp + 1) # 다시 1부터 setting해서 append
def bubble_sort(arr): # 버블 정렬로 오름차순 정렬
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
bubble_sort(output)
print(' '.join(str(x) for x in output))
굳이 for문 3개를 들여써서 회사의 기술과 직원의 기술의 교집합을 구하지 않아도, 저렇게 intersection() 메소드를 이용하면 교집합을 효율적으로 구할 수 있고, difference_update() 메소드를 이용하여 교집합에 해당하는 요소들을 U에서 빼준다.
하지만, 이런 메소드를 몰라도 풀 수 있었으면 좋을 것 같아서 다른 코드를 찾아봤다.
set() 자료형을 사용하지 않은 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
N, M = map(int, input().split()) # N은 직원의 수, M은 기술의 수
emp = [] # 각 직원이 보유한 기술을 담는 리스트
output = [] # 결과를 담을 리스트
# 각 직원이 보유한 기술을 리스트로 변환하고 1을 빼기
for i in range(N):
arr = list(map(lambda x: int(x) - 1, input().split())) # 리스트로 변환하고 1을 빼기
emp.append(arr)
U = [True] * M # True는 해당 기술을 사용 가능함을 나타냄, False는 사용 불가능을 나타냄
while any(U): # 반대는 all(U)
max_skill_count = 0 # 가장 많은 기술을 가진 직원의 기술 수
max_emp = -1 # 가장 많은 기술을 가진 직원의 인덱스
# 각 직원에 대해 가진 기술 중 사용 가능한 기술 수 구하기
for i in range(N):
count = sum(U[skill] for skill in emp[i]) # 해당 직원이 가진 사용 가능한 기술 수 구하기
if count > max_skill_count:
max_skill_count = count
max_emp = i
# 선택된 직원의 기술을 사용 불가능으로 표시
for skill in emp[max_emp]:
U[skill] = False
output.append(max_emp + 1) # 선택된 직원의 인덱스를 결과 리스트에 추가
output.sort()
print(' '.join(str(x) for x in output))
일단 U를 True로 전부 배열하는 것이 시작이다.
count = sum(U[skill] for skill in emp[i])
이 부분을 생각해내는 것이 정말 어려운 것 같다. 교집합을 구하는 중요한 구조인 것 같다.
이를 이용하여, 사용 가능한 기술이 많은 직원을 뽑은 뒤,
1
2
for skill in emp[max_emp]:
U[skill] = False
이렇게 U에서 해당 기술들을 False 해준다.
알게된 것 정리
set() 자료형
- 요소 중복 안됨
- 요소 순서 없음
- 변경 가능
- 집합 연산 지원(중요)
set 관련 메소드
clear(): 집합의 모든 요소를 제거하여 빈 집합을 만듭니다.copy(): 집합의 복사본을 반환합니다.union(other_set): 두 집합의 합집합을 반환합니다.intersection(other_set): 두 집합의 교집합을 반환합니다.difference(other_set): 다른 집합과의 차집합을 반환합니다.- 등등
1-setting에서 0-setting으로 바꾸기(참고)
arr = set(map(lambda x: int(x) - 1, input().split()))
교집합 구하는 법
1
U = [True] * M
이렇게 U를 설정해놓고,
1
count = sum(U[skill] for skill in emp[i])
emp[i]안에 들어있는 요소들을 U의 인덱스로 사용하여 True이면 +1을 나타냄