배열 개념에 대해 이해하고 활용하는 방법을 알 수 있습니다. 코딩 테스트 난이도별로 배열 관련 문제를 풀며 여러 함정을 확인하고 이를 해결하는 방법에 익숙해집니다.
배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있습니다. 총 3편으로 정리했습니다. 3편은 배열 몸풀기 문제입니다.
1. 배열의 개념
2. 배열의 효율성과 자주 활용하는 리스트 기법
3. 배열 몸풀기 문제
문제 01 배열 정렬하기 ⭐️
- 저자 권장 시간: 10분
- 권장 시간 복잡조: O(NlogN)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/01.py
정수 배열을 정렬해서 반환하는 solution( ) 함수를 완성하세요.
제약 조건
- 정수 배열의 길이는 2 이상 105 이하입니다.
- 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하입니다.
입출력의 예
문제 분석하고 풀기
문제만 놓고 보면 간단해 보이지만 제약 조건은 주의 깊게 봐야 합니다. 제약 조건을 보면 데이터 개수는 최대 105입니다. 즉, 제한 시간이 3초라면 O(N2) 알고리즘은 사용할 수 없습니다. 만약 정수 배열의 최대 길이가 10이라면 O(N2) 알고리즘을 사용해도 되죠. 제가 이 문제를 제시한 이유는 제약 조건에 따른 알고리즘의 선택을 보여주기 위함입니다. 이렇게 제약 조건에 따라 같은 문제도 난이도가 달라질 수 있습니다. 그리고 이런 때에 초보자가 하기 쉬운 실수는 너무 문제가 쉽다고 생각해서 제약 조건을 고려하지 않는다는 겁니다. 단순히 내림차순 또는 오름차순으로 정렬하면 이 문제는 통과할 수 없습니다. 정답 코드는 다음과 같이 아주 짧습니다.
def solution(arr):
arr.sort()
return arr
sort( ) 메서드는 리스트를 역순으로 반환합니다. 주목할 점은 sort( ) 메서드가 리스트 원본 자체의 값을 바꾼다는 겁니다. 만약 원본 리스트를 그대로 두고 싶다면 다음과 같이 구현하면 됩니다.
def solution(arr):
sorted_list = list(sort(arr))
return sorted_list
합격 조언
sort( ) 메서드를 사용하지 않고 O(N2) 정렬 알고리즘을 사용하면?
sort( ) 메서드를 사용하지 않고 O(N2) 정렬 알고리즘으로 배열 원소를 정렬하는 연산을 구현하면 시간 차이는 얼마나 벌어질까요? 다음 코드를 봅시다.
import time
def bubble_sort(arr): # 버블 정렬로 정렬하기
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def do_sort(arr): # sort( ) 함수로 배열 정렬하기
arr.sort( )
return arr
def measure_time(func, arr): # 시간을 측정하고 뒤집힌 배열 반환
start_time = time.time( )
result = func(arr)
end_time = time.time( )
return end_time - start_time, result
arr = list(range(10000))
# 첫 번째 코드 시간 측정
# 첫 번째 코드 실행 시간 : 3.9616279602
bubble_time, bubble_result = measure_time(bubble_sort, arr)
print("첫 번째 코드 실행 시간:", format(bubble_time, ".10f"))
# 두 번째 코드 시간 측정
# 두 번째 코드 실행 시간 : 0.0000560284
arr = list(range(10000))
reverse_time, reverse_result = measure_time(do_sort, arr)
print("두 번째 코드 실행 시간:", format(sort_time, ".10f"))
# 두 개의 코드의 결과가 동일한지 확인
print("두 개의 코드의 결과가 동일한지 확인:", bubble_result == sort_result) # True
첫 번째 방법은 O(N2) 정렬 알고리즘인 버블 정렬을 활용한 방법이고, 두 번째 방법은 O(NlogN) 시간 복잡도의 sort() 함수를 활용한 방법입니다. 결과를 보면 시간 차가 상당합니다. 데이터 10,000개를 역순으로 정렬하는 데 버블 정렬은 4초가 걸렸지만 sort( ) 함수를 활용한 두 번째 방법은 1초도 걸리지 않았습니다. 실행 환경마다 시간의 차이는 조금 생길 수 있겠지만 압도적으로 sort( ) 함수가 성능이 좋다는 것을 알 수 있습니다. 이것으로 알고리즘의 시간 복잡도가 얼마나 중요한지 알아두기 바랍니다.
시간 복잡도 분석하기
N은 arr의 길이이므로 시간 복잡도는 O(NlogN)입니다.
문제 02 배열 제어하기 ⭐️⭐️
- 저자 권장 시간: 10분
- 권장 시간 복잡조: O(NlogN)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/02.py
정수 배열을 하나 받습니다. 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution( ) 함수를 구현하세요.
제약 조건
- 배열 길이는 2 이상 1,000 이하입니다.
- 각 배열의 데이터 값은 -100,000 이상 100,000 이하입니다.
입출력의 예
문제 분석하고 풀기
이런 문제를 보면 직접 코드를 구현하고 싶은 마음이 들 수도 있지만 파이썬에는 미리 구현한 좋은 함수들이 많으므로 그런 함수들도 활용해보면 좋습니다. 이 문제가 딱 그렇게 풀었을 때 좋은 문제입니다. 코드를 살펴봅시다.
def solution(lst):
unique_lst = list(set(lst)) # ➊ 중복값 제거
unique_lst.sort(reverse=True) # ➋ 내림차순 정렬
return unique_lst
➊에서 set( ) 함수를 사용해 배열의 중복값을 제거했습니다. set( )은 집합을 생성하는 내장 함수입니다. 집합은 중복값을 허용하지 않으므로 문제에서 요구하는 중복 문제를 한 번에 해결할 수 있습니다. 가끔 파이썬 함수를 통해 해결할 수 있는 문제를 굳이 직접 코드를 작성해서 해결하려는 경우가 있습니다. 하지만 그럴 필요가 없습니다. 이를테면 반복문을 통해 일일이 데이터를 확인해서 중복값을 확인해 제거하는 알고리즘은 시간 복잡도가 O(N2)으로 성능이 좋지 않습니다. 제가 이렇게 간단해 보이는 문제를 굳이 언급한 이유는 ‘파이썬에는 코딩 테스트에 유용한 함수가 많다. 굳이 직접 작성하려 하지 마라’를 강조하기 위함이었습니다. 심지어 set( ) 함수는 해시 알고리즘으로 데이터를 저장하므로 시간 복잡도 O(N)을 보장합니다. ➋의 sort( ) 함수 활용 부분에서 reverse 매개변수에 넣은 조건을 확인할 수 있습니다. reverse가 True이면 내림차순, False이면 오름차순(기본값)입니다.
※ 해시 알고리즘 자체는 시간 복잡도가 O(1)입니다만 리스트의 원소 개수가 N인 경우 중복값을 제거하기 위해 리스트를 한 번 순회하고 삽입해야 하므로 시간 복잡도는 O(N)입니다.
시간 복잡도 분석하기
N은 lst의 길이입니다. lst의 중복 원소를 제거하는 데 걸리는 시간 복잡도는 O(N)이고, 이를 다시 정렬하는 데 걸리는 시간 복잡도는 O(NlogN)이므로 최종 시간 복잡도는 O(NlogN)입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
