[그리디] 탑승구

[ericagong]

⭐ 성찰

1. 문제 요구사항 빼먹지 말고 상세히 읽기 i번째 비행기가 1번부터 g_i 번째 탑승구 중 하나에 도킹할 수 있음
2. 가능한 한 큰 번호의 탑승구 먼저 비행기 도킹할 때 그리디 알고리즘의 정당성이 부합되는지 확인
3. 2중 for문에서 한 번에 뛰쳐 나오기 위해 별도의 변수 stop 선언

❓ 문제 상황

[탑승구](이코테 p.395)

👨‍💻 문제 해결: 그리디

⏳ 시간복잡도: O(PG)

• P = 100,000
• G = 100,000
• 따라서 최악의 경우 10^12의 연산이 필요해 주어진 시간 안에 그리디로 풀이 불가

✅ 1차 풀이: 그리디 (시간 초과)

그리디 정당성: 주어진 비행기가 도킹 가능한 탑승구 중 가장 큰 탑승구를 우선 선택하는 것이 최적해를 보장하는지 파악 앞선 비행기가 최대 탑승구를 선택했을 때, 그 이후 비행기가 더 작거나 동일한 최대탑승구를 가져도 이전 선택에 영향을 끼치지 않음.

1. 비행기 순서대로 선택하므로, 어떤 탑승구에도 도킹 불가한 비행기가 나오는 경우, 중지 가능하도록 stop 변수를 별도로 설정
2. 뒤에서부터 가능한 탑승구를 찾되, 탑승구 0에 도달하는 경우, 더이상 탑승 불가하다 판정함.

# code
g = int(input())
p = int(input())
occupied = [False] * (g+1)
cnt = 0
stop = False
data = []
for _ in range(p):
  data.append(int(input()))

for i, d in enumerate(data):
  for i in range(d, -1, -1):
    if stop:
      break
    if i == 0:
      stop = True
      print(cnt)
      break
    if not occupied[i]:
      occupied[i] = True
      cnt += 1
      break

✅ 2차 풀이: union 합집합

[ericagong]

✏️ TODO

탑승구 문제 서로소 집합 알고리즘으로 시간 복잡도 계산 + 풀이하기