배열 - 몸풀기 문제

문제 01 배열 정렬하기

정수 배열을 정렬해서 반환
시간복잡도 : O(NlonN)

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

# 원본 바꾸지 않으려면
def solution(arr):
	sorted_list=list(sort(arr))
    return sorted_list

이 문제에서는 시간복잡도를 한 번쯤 확인하고 고려해보는 것이 핵심 !
파이썬은 1초에 1000만번 (10^7) 연산
-> 제한 시간이 1초면 1000만번 연산 이상인 알고리즘을 선택해야함

n! 최대 10번
2^n 최대 20번
n^3 최대 200번
n^2 최대 3000번
nlogn 최대 100만번
n 최대 1000만번
logn 최대 10억

# 버블 정렬 O(N^2)
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

cf ) arr[j],arr[j+1]=arr[j+1],arr[j] 이렇게 자리 바꾸기 가능

문제 02 배열 제어하기

정수 배열을 하나 받고, 배열의 중복값을 제거하고 내림차순으로 정렬해서 반환

def solution(arr):
	result=list(set(arr))
    result.sort(reverse=True)
    return result

배열의 중복값은 set() 함수를 사용해서 제거 !
set 함수는 해시 알고리즘으로 데이터를 저장해서 O(N) 보장