구현/완전탐색) Pro Lv1 실패율

Git: https://github.com/Tarte12/CodingTest_KUT/commit/d0e27be86ad32139ae74b2542fe394c30cccf43d

1. stay / reached

• stay[i]: 스테이지 i에 머무는 사람 수 (= i에서 실패한 사람)
• reached[i]: 스테이지 i에 도달한 사람 수 (= i 이상 스테이지에 있는 사람 전부)

2. 뒤에서 앞으로 누적 (suffix sum)

✅ 개념

• prefix sum (전방 누적): 앞에서부터 누적
  → sum[3] = arr[1] + arr[2] + arr[3]
• suffix sum (후방 누적): 뒤에서부터 누적
  → sum[3] = arr[3] + arr[4] + ... + arr[n]

즉,

• prefix = 과거까지의 누적
• suffix = 미래(뒤쪽)까지의 누적

✅ 왜 여기서 suffix?

• reached[i] = stay[i] + stay[i+1] + ... + stay[N] + stay[N+1]
• i보다 큰 값들이 필요 → 뒤에서 앞으로 계산해야 효율적

✅ 파이썬 range 예시

for i in range(N-1, 0, -1):
    ...

• i = N-1, N-2, ..., 1 (역순 반복)

3. 튜플 (tuple)

✅ 정의

• 여러 값을 묶어서 하나의 데이터로 저장하는 자료형
• 예: (3.5, 2) → 실패율 3.5, 스테이지 2

✅ 특징

• 수정 불가(immutable)
• 인덱스로 접근 가능 (t[0], t[1])
• 정렬 시: 첫 번째 원소 → 두 번째 원소 순서대로 비교

✅ 여기서 쓰는 이유

• (실패율, 스테이지번호)를 같이 들고 다니면
  → 정렬 후 스테이지 번호만 뽑으면 끝!

4. 정렬 키 (sort key)

✅ 기본

• list.sort(key=...) 또는 sorted(list, key=...)
• key 함수가 돌려준 값을 기준으로 정렬

✅ 음수 기법

• 내림차순은 reverse=True로도 가능하지만,
• 실패율 내림차순 + 번호 오름차순 같은 복합 조건은 이렇게:

answer.sort(key=lambda x: (-x[0], x[1]))

• x[0]: 실패율 (내림차순 → -붙임)
• x[1]: 스테이지 번호 (동률이면 작은 번호 먼저)

5. 분모 0 처리

• reached[i] == 0 → 도달한 사람이 없는 스테이지 → 실패율 0
• 그 외 → stay[i] / reached[i]

6. 전체 절차 요약

1. stay 배열 채움 (stage별 머무른 사람 수)
2. reached 배열 채움 (뒤에서 앞으로 누적)
3. 실패율 계산 → (실패율, 스테이지번호) 튜플로 저장
4. 정렬: 실패율 내림차순, 번호 오름차순
5. 정렬된 순서에서 스테이지 번호만 반환

7. 헷갈렸던 포인트 총정리

• range(N-1, 0, -1) → N-1 down to 1 (역순 루프)
• stay[N+1] = 전부 클리어 인원
  • 실패율 분자에는 불포함
  • reached에는 포함
• 정수 나눗셈(//) ❌ → 반드시 실수 나눗셈(/)
• list.sort()는 제자리 정렬, 반환값은 None
• 반환해야 하는 건 실패율이 아니라 스테이지 번호 리스트
• 튜플은 (실패율, 번호) 형태로 저장 → 정렬 시 자동으로 실패율 우선, 동률이면 번호 비교 가능