처음엔 빈도값을 기준으로 멀티탭 아이템들을 뽑아내었으나, 정답이 맞지 않았다. 남은 전기 용품 리스트에서 가장 나중에 출현하는 아이템들을 뽑아내야만 한다. 그리디 방식이며, 자세한 풀이는 코드 주석으로 대체하겠다. 참고로 경우의 수를 잘 파악해야함을 유의해야한다. 다음은 경우의 수를 넘버링하여 나타낸 것이다.
- 이미 멀티탭에 꽂혀있는 경우
- 멀티탭에 꽂혀 있지 않은 경우
- 멀티탭 자리가 남아있는 경우
- 멀티탭 자리가 남아있지 않은 경우
- 멀티탭에 꽂힌 아이템 중 다시 등장하는 아이템이 존재하는 경우
- 멀티탭에 꽂힌 아이템 중 다시 등장하지 않는 아이템이 하나라도 존재하는 경우
- 멀티탭에 꽂힌 아이템이 모두 다시 등장하는 경우
- 멀티탭에 꽂힌 아이템 중 다시 등장하는 아이템이 아예 존재하지 않는 경우
현재 아이템을 기준으로 보았을 때 가장 나중에 등장하는 아이템을 찾기 위해서 dict.fromkeys()
를 사용하였다. 남아있는 아이템 배열이 arr=[2, 5, 3, 2] 라고 가정했을 때 단순히 arr[-1]을 하면 안되므로 (동일한 아이템이 여러번 등장할 수 있음을 고려해야하기 때문에) 중복은 제거하되, 이에 대한 순서 보장이 필요했다. 따라서 리스트의 중복 제거 및 순서 보장을 위해 set()이 아닌 dict.fromkeys()를 사용하였다.
n, k = map(int,input().strip().split())
items = list(map(int,input().split()))
# 멀티탭 수만큼 list 만들기
multiTap = [0]*n
cnt=0
for i in range(len(items)):
# 현재 item이 이미 멀티탭에 꽂혀있는 경우 continue
if items[i] in multiTap:
continue
else:
# 자리가 남아있는 경우 멀티탭 꽂음
if 0 in multiTap:
multiTap[multiTap.index(0)] = items[i]
# 자리가 안 남아있는 경우
else:
appear=[]
# 멀티탭에 꽂힌 아이템 중 다시 등장하는 아이템은 나중에 뽑아야하므로 appear 리스트로 check
for j in range(i+1,len(items)):
if items[j] in multiTap:
appear.append(items[j])
# 멀티탭에 꽂힌 아이템 중 다시 등장하는 아이템이 존재한다면
if(appear):
result_list = list(dict.fromkeys(appear))
for k in range(len(multiTap)):
# 멀티탭에 꽂힌 아이템 중 다시 등장하지 않는 아이템을 뽑음
if multiTap[k] not in result_list:
multiTap[k]=items[i]
cnt+=1
break
# 만약 멀티탭에 꽂힌 아이템 중 다시 등장하지 않는 아이템이 아예 없거나,
# 다시 등장하는 아이템이 여러개인 경우
# 가장 순서가 가까운 아이템을 가장 나중에 뽑아야하므로 맨 뒷순서의 아이템을 뽑음
else:
multiTap[multiTap.index(result_list[-1])]=items[i]
cnt+=1
# 만약 멀티탭에 꽂힌 아이템 중 다시 등장하는 아이템이 한 개도 없다면, 멀티탭에서 아무거나 뽑음
else:
multiTap[0]=items[i]
cnt+=1
# print(multiTap,'멀티탭', cnt, '카운트')
print(cnt)
파이썬에서 리스트를 중복 제거 할 때 순서를 보장하는 방식을 알게 되었다. 보통 리스트의 중복 제거를 구현할 경우 단순히 set() 자료형을 이용하는 경우가 많은데, 이는 알다시피 요소의 순서를 보장받지 못한다.
그러나 dict.fromkeys()
를 사용해서 이를 리스트화 할 경우 순서를 보장받을 수 있다 👍🏻 for문을 활용해서도 순서를 유지하며 중복 제거가 가능하지만 fromkeys() 메소드를 사용하면 코드를 간결하게 짤 수 있다.
arr = [6, 5, 6, 4, 4, 1, 1, 2, 3, 9, 8, 7, 9, 8, 7]
result = [] # 중복 제거된 값들이 들어갈 리스트
for value in arr:
if value not in result:
result.append(value)
print(result)
# [6, 5, 4, 1, 2, 3, 9, 8, 7]
arr = [6, 5, 6, 4, 4, 1, 1, 2, 3, 9, 8, 7, 9, 8, 7]
result1 = dict.fromkeys(arr) # 리스트 값들을 key 로 변경
print(list(result1))
# [6, 5, 4, 1, 2, 3, 9, 8, 7]