[코테공부 5/24] 배열 - 교재문제01

제약조건 설명이 이해가 안됐던 문제

def solution(arr):
  arr.sort()
  return arr
  

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution([1,-5,2,4,3])) # 반환값 : [-5, 1, 2, 3, 4]
print(solution([2,1,1,3,2,5,4])) # 반환값 : [1, 1, 2, 2, 3, 4, 5]
print(solution([1,6,7])) # 반환값 : [1, 6, 7]

배열 정렬하는 문제를 푸는데,
제약조건은
- 정수 배열의 길이는 2 이상 100000 이하이고
- 정수 배열의 각 데이터 값은 -100000 이상 100000 이하래

문제분석란에
제약조건을 보면 데이터 개수는 최대 100000이다. 즉, 제한 시간이 3초라면 O(N제곱) 알고리즘은 사용할 수 없다. 라는 말이 있는데, 무슨말이야?

chatgpt 답변

💡 문제 조건 요약
배열의 길이: 최대 100,000개

제한 시간: 3초 (일반적으로 코딩테스트 기준 시간)

🧠 시간 복잡도란?
알고리즘이 입력 크기(N)에 따라 얼마나 많은 연산을 하는지를 나타내는 것.

대표적인 시간 복잡도:

O(N): 입력 크기만큼

O(N log N): 정렬 알고리즘 대부분

O(N²): 이중 for문 → N이 커지면 매우 느려짐

🔥 왜 O(N²) 안 되는지 예시로 보기
예를 들어 N = 100,000인 경우:

O(N²) 알고리즘:
→ 100,000 × 100,000 = **10,000,000,000 (100억)**번 연산
→ 컴퓨터는 1초에 약 1억 번 연산한다고 가정하면,
100억 ÷ 1억 = 약 100초 걸림 (💣 시간 초과)

O(N log N) 알고리즘 (정렬 알고리즘이 보통 이 수준)
→ 대략 100,000 × log₂(100,000) ≈ 100,000 × 17 ≈ 170만 연산
→ 1초 이내 처리 가능! ✅

📌 결론
제약 조건에 따라 시간 복잡도가 O(N²)인 알고리즘은 쓰면 안 된다.
대신 O(N log N) 또는 그 이하인 알고리즘을 사용해야 한다.

따라서 정렬 문제에서는 sort()처럼 빠른 정렬 (Timsort 기반, O(N log N))을 쓰는 게 맞고, 이 문제의 solution() 함수는 효율적으로 잘 짜인 거예요. 😊

최대 100000 값을 갖는데,
O(N제곱)을 쓰게 되면 100억번 연산, (1초에 1억번 연산)이면 100초 걸리고
O(NlogN)을 쓰면 170만 연산이면, 1초에 1억번 연산이면, 1초 안걸림

출처 : 코딩테스트 합격자되기 - 파이썬편