백준 1700번 멀티탭 스케줄링 | python | 그리디

문제

링크

풀이

처음엔 빈도값을 기준으로 멀티탭 아이템들을 뽑아내었으나, 정답이 맞지 않았다. 남은 전기 용품 리스트에서 가장 나중에 출현하는 아이템들을 뽑아내야만 한다. 그리디 방식이며, 자세한 풀이는 코드 주석으로 대체하겠다. 참고로 경우의 수를 잘 파악해야함을 유의해야한다. 다음은 경우의 수를 넘버링하여 나타낸 것이다.

1. 이미 멀티탭에 꽂혀있는 경우
2. 멀티탭에 꽂혀 있지 않은 경우
   • 멀티탭 자리가 남아있는 경우
   • 멀티탭 자리가 남아있지 않은 경우
     • 멀티탭에 꽂힌 아이템 중 다시 등장하는 아이템이 존재하는 경우
       • 멀티탭에 꽂힌 아이템 중 다시 등장하지 않는 아이템이 하나라도 존재하는 경우
       • 멀티탭에 꽂힌 아이템이 모두 다시 등장하는 경우
     • 멀티탭에 꽂힌 아이템 중 다시 등장하는 아이템이 아예 존재하지 않는 경우

현재 아이템을 기준으로 보았을 때 가장 나중에 등장하는 아이템을 찾기 위해서 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() 메소드를 사용하면 코드를 간결하게 짤 수 있다.

1. 일반 for문 이용

  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]

2. dict.fromkeys() 이용

    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]