[코드트리] 완전탐색 - 운행 되고 있는 시간

코드트리 네이버 커리큘럼 - 완전탐색

• 운행 되고 있는 시간 (Python)
  https://www.codetree.ai/cote/14/problems/hours-in-service/description

Code

N = int(input())
work_hour = [list(map(int, input().split())) for _ in range(N)]

# ex) [1 4) [3 7) [5 9)
# 1 2 3 4 5 6 7 8 9
# [     ]
#     [       ]
#         [        ]

# 범위를 설정하기 위해 직원들 중 가장 마지막 시간의 길이 찾기
length = 0
for i in range(len(work_hour)):
    if(length < work_hour[i][0]):
        length = work_hour[i][0]
    if(length < work_hour[i][1]):
        length = work_hour[i][1]

max_cnt = 0
for i in range(N):
    to_fire = work_hour[i]      # 해고할 직원 하나 선정
    check = []
    for j in range(N):
        if (work_hour[j] != to_fire):       # 해고할 직원을 제외하고 시간 계산을 하기 위해 check 리스트에 담기
            check.append(work_hour[j])

    # 남은 직원들의 일하는 시간 표시
    check_time = [False for _ in range(length)]
    for i in range(len(check)):
        for j in range(check[i][0]-1, check[i][1]-1):   # 각 직원의 일하는 시간들 True로 칠하기
            check_time[j] = True

        # print(check_time)

    cnt = check_time.count(True)    # True면 직원이 일하고 있는 시간이므로 True들을 count
    if(max_cnt < cnt):      # 최대 운행 되고 있는 시간 찾기
        max_cnt = cnt

print(max_cnt)

풀이 및 해설

• 해고할 직원을 하나씩 뽑아서 → 해당 직원을 제외하고 시간 칠해보기 → 가장 최대의 시간이 칠해지는 값이 정답
• 여기서 입력되는 일하는 시간의 의미

  # ex) [1 4) [3 7) [5 9)
  
  # 만약 [1 4) 라면 아래에서 첫번째와 같이 일한다는 뜻
  # 1 2 3 4 5 6 7 8 9
  # [     )
  #     [       )
  #         [        )

• 해설 코드

  MAX_NUM = 1000
  
  # 변수 선언 및 입력
  n = int(input())
  segments = [
      tuple(map(int, input().split()))
      for _ in range(n)
  ]
  
  ans = 0
  
  # 빼야하는 직원을 정합니다.
  for i in range(n):
  	# i번 직원의 구간을 제외한 나머지 구간에서
  	# 운행 되고 있는 시간을 구합니다.
  	
  	count = [0] * MAX_NUM
  	
  	for j, (l, r) in enumerate(segments):
  		# i번째 구간은 제외합니다.
  		if j == i:
  			continue
  		
  		# 모든 구간을 카운팅합니다.
  		for k in range(l, r):
  			count[k] += 1
  	
  	time = 0
  	
  	for j in range(1, MAX_NUM):
  		if count[j] > 0:
  			time += 1
  
  	# 운행 되고 있는 시간 중 최댓값을 구합니다.
  	ans = max(ans, time)
  
  print(ans)