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

Konseo·2023년 8월 6일
0

코테풀이

목록 보기
5/59

문제

링크

풀이

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

  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]
  1. 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]
profile
둔한 붓이 총명함을 이긴다

0개의 댓글