이 문제는 입력값에 범위도 매우 적어서 단순 구현을 하면 쉽게 푸는 문제라고 생각해 얕봤었지만 좀 더 구체적으로 생각해보니 엄청나게 많은 for문 사용이 예상되어 그리디적인 방법에 대해 고민하다가 결국 시간초과로 인해 문제를 다 풀지 못하였다.
그리고 여러 사람의 해답을 보고 모든 조합의 경우의 수에서 유일성을 만족하는지 판단한 다음 거기서 추려진 항목들중 희소성을 만족한다면 해당 문제의 답이 되는 식으로 문제를 풀었다.
1. 모든 조합의 경우의 수를 구한다.
address = [i for i in range(0,col)]
comb = []
#후보키의 모든 조합을 comb리스트에 저장
for i in range(1,col+1):
comb.extend(map(tuple,combinations(address,i))).extend의 메서드를 사용하여 튜플로 묶어진 모든 조합의 경우를 하나의 리스트에 담게 했다.
2. 위에서 구한 주소값들의 모든 조합을 make_table함수를 통해 실제 값의 조합들을 구성하였다.
# relation의 주소값 combination 조합들을
# 원래의 값들의 조합으로 바꾸는 함수
def make_table(lst,row,col,relation):
ans = []
for i in range(row):
option = []
for j in lst:
option.append(relation[i][j])
ans.append(option)
return ans 3. 실제 값 조합들이 유일성을 만족하는지 알아본다.
유일성은 임의의 두 값을 가져와 두 값이 같은 지 비교하는 방식으로 풀었다.
## 유일성 만족
for com in comb:
flag = False
lst = make_table(com,row,col,relation)
# 각 항목에 똑같은 값들이 있는지 확인한다.
for i in range(len(lst)):
for j in range(len(lst)):
if i == j:
continue
else:
if lst[i] == lst[j]:
flag = True
break
if flag == True:
break
# 없다면 유일성의 속성을 가지고 있기 때문에 unique리스트에 넣어준다.
if flag == False:
unique.append(com)실제 값들의 임의의 두 값들을 모두 비교하여 두 값이 같을 경우 flag변수를 True, 그렇지 않을 경우 False로 두어 유일성을 판단하였다.
이때 포문을 끝까지 돌렸음에도 불구하고 flag값이 False일 경우 unique라는 리스트에 해당 주소값 조합을 넣습니다.
4. 유일성을 만족한 값들 중 최소성을 만족하는 지 확인합니다.
최소성을 만족하는지 확인하여 임의의 두 값을 가져와 두 값이 서로 부분집합일 경우를 확인하는 방식으로 접근하였습니다.
# set으로 자료형을 묶기 위해서는 각 리스트의 원소들이 해쉬가 있는 값(set, 숫자)이어야 한다.
answer = set(unique)
### 최소성 만족
for i in range(len(unique)):
for j in range(len(unique)):
if i == j:
continue
else:
#만약 unique에 있는 임의의 두 원소를 비교하여 부분집합일 경우 그 원소를 제거한다.
if len(unique[i]) == len(set(unique[i]) & set(unique[j])):
# set 자료형에서만 쓸 수 있는 discard함수를 통해 해당값이 있으면 지울 수 있고 없어도 오류가 발생하지 않을 수 있다.
answer.discard(unique[j])
return len(answer)set(unique)값을 answer로 복사하여 만약 부분집합이 있을 경우 상위집합을 제거하는 식으로 구현하였다.
.discard 메서드의 경우 set자료형에만 쓸 수 있는 메서드로서 만약 지우고자 하는 값이 있을 때 그 값을 제거, 없을 때도 그냥 에러가 나지 않고 넘어가는 메서드이기에
set(unique)를 answer로 복사하고 .discard를 사용하였습니다. remove를 사용할 경우 에러가 난다.
실제 코드
# 프로그래머스
# 카카오 2019 블라인드 채용 출제 문제
# 후보키
# 입력값
relation = [["100","ryan","music","2"],
["200","apeach","math","2"],
["300","tube","computer","3"],
["400","con","computer","4"],
["500","muzi","music","3"],
["600","apeach","music","2"]]
from itertools import combinations
# relation의 주소값 combination 조합들을
# 원래의 값들의 조합으로 바꾸는 함수
def make_table(lst,row,col,relation):
ans = []
for i in range(row):
option = []
for j in lst:
option.append(relation[i][j])
ans.append(option)
return ans
def solution(relation):
row = len(relation) #세로 축
col = len(relation[0]) #가로 축
address = [i for i in range(0,col)]
comb = []
#후보키의 모든 조합을 comb리스트에 저장
for i in range(1,col+1):
comb.extend(map(tuple,combinations(address,i)))
unique = []
## 유일성 만족
for com in comb:
flag = False
lst = make_table(com,row,col,relation)
# 각 항목에 똑같은 값들이 있는지 확인한다.
for i in range(len(lst)):
for j in range(len(lst)):
if i == j:
continue
else:
if lst[i] == lst[j]:
flag = True
break
if flag == True:
break
# 없다면 유일성의 속성을 가지고 있기 때문에 unique리스트에 넣어준다.
if flag == False:
unique.append(com)
# set으로 자료형을 묶기 위해서는 각 리스트의 원소들이 해쉬가 있는 값(set, 숫자)이어야 한다.
answer = set(unique)
### 최소성 만족
for i in range(len(unique)):
for j in range(len(unique)):
if i == j:
continue
else:
#만약 unique에 있는 임의의 두 원소를 비교하여 부분집합일 경우 그 원소를 제거한다.
if len(unique[i]) == len(set(unique[i]) & set(unique[j])):
# set 자료형에서만 쓸 수 있는 discard함수를 통해 해당값이 있으면 지울 수 있고 없어도 오류가 발생하지 않을 수 있다.
answer.discard(unique[j])
return len(answer)2019 카카오 공개 채용 때 출제되었던 문제로 실제 시험에서 접했더라면 아마 풀지 못했을 거 같다. 이 문제를 통해서 내가 2차원 배열을 통한 단순 구현문제에 약하다는 사실을 알았다.
