📌 큰 수의 법칙 - 코드 비교 분석

1️⃣ 내가 작성한 코드

n, m, k = map(int, input().split())
arr = list(map(int, input().split()))

sum = 0
cnt = k

while m > 0:
  if cnt > 0:
    sum += max(arr)  # 매번 max() 호출 → O(N) 연산 반복
    m -= 1
    cnt -= 1
  else:
    tmp = max(arr)
    arr.remove(tmp)  # 리스트에서 요소 삭제 → O(N) 연산
    sum += max(arr)  
    m -= 1
    cnt = k
    arr.append(tmp)  # 삭제한 요소 다시 추가

🔹 문제점

• max(arr)를 반복적으로 호출 → O(N) 연산이 반복됨
• arr.remove()와 arr.append()를 사용 → 불필요한 리스트 조작
• 시간 복잡도: O(NM) (느림) 🚫

---

2️⃣ 개선된 코드 (정렬 활용)

n, m, k = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
first = arr[-1]   # 가장 큰 수
second = arr[-2]  # 두 번째로 큰 수

sum = 0
cnt = k

while m > 0:
  if cnt > 0:
    sum += first
    m -= 1
    cnt -= 1
  else:
    sum += second
    m -= 1
    cnt = k

🔹 개선점

• max(arr) 대신 정렬(sort())을 사용하여 가장 큰 수를 미리 구함 → O(N log N)
• 불필요한 리스트 조작 제거
• 하지만 while m > 0 반복문이 여전히 존재 → 시간 복잡도 O(M)으로 비효율적 🚫

---

3️⃣ 최적화된 코드 (반복문 없이 O(1) 연산)

n, m, k = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
first = arr[-1]   # 가장 큰 수
second = arr[-2]  # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = (m // (k + 1)) * k + (m % (k + 1))

# 최종 결과 계산
result = (count * first) + ((m - count) * second)

print(result)

🔹 최적화된 이유

• 반복문 없이 한 번의 계산만 수행 (O(1)) 🚀
• (m // (k + 1)) * k + (m % (k + 1)) 를 이용해 가장 큰 수가 몇 번 더해질지 미리 계산
• 두 번째로 큰 수도 한 번의 연산으로 계산 가능
• 시간 복잡도: O(N log N) (정렬) → O(1) (빠름) ✅

---

📌 1이 될 때까지 - 코드 비교 분석

1️⃣ 내가 작성한 코드

n, k = map(int, input().split())

cnt = 0

while True:
  if n % k == 0:
    n = n / k
    cnt += 1
  else:
    n = n - 1
    cnt += 1
  
  if n == 1:
    break

print(cnt)

🔹 문제점

• n % k == 0 체크 후 n - 1을 반복적으로 수행하여 비효율적
• 시간 복잡도: O(N) (최악의 경우) 🚫

---

2️⃣ 최적화된 코드 (한 번에 처리)

n, k = map(int, input().split())

cnt = 0

while n >= k:
    # n이 k로 나누어 떨어질 수 있도록 한 번에 감소
    target = (n // k) * k
    cnt += (n - target)
    n = target
    
    # 더 이상 나눌 수 없으면 반복 종료
    if n < k:
        break
    
    # 나누기 연산 수행
    n //= k
    cnt += 1

# 마지막으로 남은 숫자 처리
cnt += (n - 1)

print(cnt)

🔹 최적화된 이유

• target = (n // k) * k를 이용해 한 번에 나누어 떨어지는 수로 조정 🚀
• cnt += (n - target)으로 한 번에 감소 연산 수행 → 반복 횟수 줄임
• n //= k 수행 후, 남은 n이 k보다 작아지면 한 번에 n-1까지 감소
• 시간 복잡도: O(log N) (더 효율적) ✅

---

📌 볼링공 고르기 - 코드 비교 분석

1️⃣ 내가 작성한 코드 (브루트포스 방식)

n, m = map(int, input().split())
a = list(map(int, input().split()))

l = []

for i in range(len(a)-1):
  for j in range(i+1, len(a)):
    if a[i] != a[j]:
      l.append((i+1, j+1))

print(len(l))

🔹 문제점

• 이중 for문을 사용하여 O(N²) 시간 복잡도 발생 🚫
• 불필요한 리스트 l 사용 → 공간 낭비 💾
• 큰 입력값(N = 100,000)에서 비효율적 → 시간 초과 가능 ⚠️

---

2️⃣ 최적화된 코드 (무게별 개수 카운팅 방식)

n, m = map(int, input().split())
a = list(map(int, input().split()))

# 각 무게별 개수 저장
weight_count = [0] * (m + 1)

for w in a:
    weight_count[w] += 1

# 가능한 조합 개수 구하기
result = 0
for i in range(1, m + 1):
    n -= weight_count[i]  # 현재 무게를 선택한 공 제외
    result += weight_count[i] * n  # 남은 공과 조합

print(result)

🔹 최적화된 이유

• 무게별 개수를 배열에 저장하여 O(N)에 해결 가능 🚀
• 불필요한 리스트(l) 제거 → 공간 절약
• 이중 for문 없이 한 번의 반복으로 해결 (O(N))
• 큰 입력값(N = 100,000)에서도 빠르게 동작 ✅

---

📌 "만들 수 없는 금액" - 코드 비교 분석

1️⃣ 내가 작성한 코드

import copy

n = int(input())

unit = list(map(int, input().split()))
unit.sort()

s = set()
res = sum(unit) + 1

for i in unit:
  if res < i:
    break
  if len(s) == 0: 
    s.add(i)
    res = i + 1
    continue
  else:
    tmp = copy.deepcopy(s)
    for j in s:
      tmp.add(i + j)
    s = tmp
    res = max(s) + 1

print(res)

🔹 문제점

• set을 사용하여 가능한 모든 조합의 합을 저장 → 불필요한 연산 ⏳
• copy.deepcopy(s)를 매번 수행 → 비효율적 ❌
• max(s) + 1을 통해 최댓값을 계속 찾음 → 굳이 set을 쓰지 않아도 해결 가능

✅ 시간 복잡도: O(2^N) (최악의 경우) 🚫 비효율적!

---

2️⃣ 최적화된 코드 (그리디 알고리즘 적용)

n = int(input())  
unit = list(map(int, input().split()))  
unit.sort()  

res = 1  # 만들 수 없는 최소 금액

for i in unit:
    if res < i:
        break
    res += i

print(res)

🔹 최적화된 이유

• 가능한 범위의 최댓값 res를 유지하며 진행 🚀
• res < i가 되면 그 순간 res를 만들 수 없으므로 정답!
• 불필요한 조합 계산 없이 O(n log n)에 해결 (정렬 후 한 번만 순회)
• 시간 복잡도: O(n log n) (훨씬 효율적!) ✅