[백준 / 27172 / Python] 수 나누기 게임

문제 요약

여러 명의 플레이어가 각각 1~1,000,000 사이의 서로 다른 수가 적힌 카드를 한 장씩 받습니다.
각 플레이어는 본인을 제외한 모든 플레이어와 한 번씩 결투를 하며,

• 내 카드의 수로 상대의 수를 나누어 떨어지면 승리(+1점),
• 반대로 상대가 내 수를 나누어 떨어뜨리면 패배(-1점),
• 둘 다 아니면 무승부(점수 변화 없음)
  이렇게 모든 결투가 끝난 뒤, 각 플레이어의 최종 점수를 구하는 문제입니다.

---

접근 방식

처음에는 모든 플레이어 쌍을 비교하는 완전탐색을 떠올릴 수 있습니다.
하지만 플레이어 수 N이 최대 100,000명, 카드 숫자 범위도 1,000,000까지라서
O(N²) 방식은 시간 초과가 발생합니다.

여기서 "나누어 떨어진다"는 조건에 주목하면,
각 카드의 배수(2배, 3배, ...)가 다른 플레이어의 카드에 있다면
그 배수 카드를 가진 플레이어에게 승리할 수 있습니다.

즉,

• 내 카드의 배수에 해당하는 카드가 있다면 나는 +1점, 그 상대는 -1점
• 이 과정을 모든 카드에 대해 반복
  이렇게 하면 불필요한 비교 없이 효율적으로 점수를 계산할 수 있습니다.

실생활 비유로 설명하면,
"내가 가진 숫자의 배수만 찾아서 그 사람만 이긴다"는 식으로
불필요한 결투(비교)를 피하는 셈입니다.

---

코드 구현

아래는 Python으로 구현한 코드입니다.
핵심 부분마다 주석을 달아 이해를 돕습니다.

import sys
input = sys.stdin.readline

N = int(input())
cards = list(map(int, input().split()))
max_card = max(cards)
card_set = set(cards)  # 카드가 실제로 존재하는지 빠르게 확인

# 각 카드별 점수 기록용 딕셔너리
value_score = {card: 0 for card in cards}

for card in cards:
  multiple = card * 2
  # 내 카드의 배수들만 탐색
  while multiple <= max_card:
    if multiple in card_set:
      value_score[card] += 1      # 나는 이긴다
      value_score[multiple] -= 1  # 상대는 진다
    multiple += card

# 결과 출력 (입력 순서대로)
print(' '.join(str(value_score[card]) for card in cards))

---

시간복잡도 & 최적화

• 시간복잡도:
  • 각 카드마다 자신의 배수(최대 1,000,000까지)를 탐색하므로
    전체적으로 약 O(N log M) 수준 (M: 카드 숫자 최대값)
• 최적화 포인트:
  • 카드가 실제로 존재하는지 빠르게 확인하기 위해 set 자료구조 사용
  • 불필요한 모든 쌍 비교를 배수 관계로만 한정하여 연산량 대폭 감소

---

느낀 점 / 팁

• "모든 쌍을 비교"하는 문제는 반드시 효율적인 조건(여기선 배수 관계)을 찾아내야 합니다.
• set을 활용하면 "존재 여부"를 O(1)로 빠르게 확인할 수 있어,
  대량의 데이터 처리에 매우 유용합니다.
• 배수 관계 문제는 종종 "에라토스테네스의 체"와 비슷한 아이디어로 접근하면
  시간복잡도를 크게 줄일 수 있습니다.

---

참고

• 백준 27172번 문제 링크
• 파이썬 set 공식 문서
• 에라토스테네스의 체 위키백과

---