[Python] 배열 공부 및 순열 검사 알고리즘 문제 풀기

1. 배열 공부

1.1 배열이 왜 필요할까?

• 같은 종류의 데이터를 효율적으로 관리
• 순차적으로 관리
• 배열의 장점: 빠른 접근가능
• 배열의 단점: 추가/삭제가 쉽지 않음, 미리 최대 길이를 지정해야 함

1.2 파이썬과 배열

# 1차원 배열: 리스트로 구현시 data = [1,2,3,4,5]

# 2차원 배열 : 리스트로 구현시 data = [[1,2,3], [4,5,6],[7,8,9]]

2. 순열 알고리즘 문제

2.1 문제 설명

길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다. 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.
제한사항

• 배열의 길이는 10만 이하입니다.
• 배열의 원소는 0 이상 10만 이하인 정수입니다.

2.2 실패한 풀이

2.2.1 numpy를 사용한 분산 값으로 비교

import numpy as np

def solution(arr):
    arr = np.array(arr)
    lst = np.array([i for i in range(1,len(arr)+1)])
    if arr.var() == lst.var():
        return True
    else:
        return False

꼼수로 풀어보려고 길이가 1부터 순차적으로 늘어나는 길이가 n인 배열을 만들어서 분산을 구하고 이를 시스템 입력값으로 들어온 배열의 분산 값과 비교했다. 잘 통과했는데...효율성 부분에서 2개가 실패했다 ㅠㅠ

2.2.2 merge sort를 사용하여 배열비교

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

def solution(arr):
    merge_list = mergesort(arr)
    for i in range(0,len(merge_list)):
        if merge_list[i] != i+1:
            return False
        else:
            if i == len(merge_list):
                return True

mergesort 를 사용해서 시간복잡도를 줄이려고 했는데..... append를 써서 그런가 ㅠㅠ 이것도 효율성에서 2개의 테스트가 실패했다.

2.3 성공한 풀이

def solution(arr):
    arr = sorted(arr)
    for i in range(len(arr)):
        if arr[i] != i+1:
            return False
    return True

사실 왜 진작에 이렇게 안했을까 하는 바보같은 생각이.....아주 간단하게 sorted 함수를 사용하여 재배열을 한뒤에 값을 비교했다.