[2강] 선형 배열(Linear Array)

황인용·2020년 7월 8일
0
post-thumbnail

배열(Arrays)

  • 원소들을 순서대로 늘어놓은 것
  • 순서(index) : 0부터 시작

리스트(List)

  • Python에서의 리스트(list)
  • 대괄호로 요소들을 묶어서 표현

Example

>>> L = ['Bob', 'Cat', 'Spam', 'Programmers']
>>> L[0]
Bob

>>> L[-1]
Programmers

// 리스트에 마지막 요소 추가
>>> L.append('New')
>>> L
['Bob', 'Cat', 'Spam', 'Programmers', 'New']

// 리스트에서 마지막 요소 꺼내기
>>> L.pop()
'New'
>>> L
['Bob', 'Cat', 'Spam', 'Programmers']

리스트(배열)연산

원소 덧붙이기와 끝에서 꺼내기

  • 원소 덧붙이기 : append()
  • 끝에서 꺼내기 : pop()
  • 순식간에 빠르게 할 수 있는 일 : O(1)
  • 리스트의 길이와 무관(상수 시간)

Example

// 리스트에 마지막 요소 추가
>>> L.append('New')
>>> L
['Bob', 'Cat', 'Spam', 'Programmers', 'New']

// 리스트에서 마지막 요소 꺼내기
>>> L.pop()
'New'
>>> L
['Bob', 'Cat', 'Spam', 'Programmers']

원소 삽입하기와 원소 삭제하기

  • 특정 원소 삽입 : insert(index, element)
  • 특정 원소 삭제 : del(list[index])
  • 리스트의 길이가 길면 오래 걸리는 일 : O(n)
  • 리스트의 길이에 비례(선형 시간)

Example

>>> L = [20, 37, 58, 72, 91]
>>> L
[20, 37, 58, 72, 91]

// 원소 삽입 하기
>>> L.insert(3, 65)
>>> L
[20, 37, 58, 65, 72, 91]

// 원소 삭제 하기
>>> del(L[2])
>>> L
[20, 37, 65, 72, 91]

원소 꺼내기와 원소 삭제하기와 비교

원소 탐색하기

  • index(element)

[실습_1] 정렬된 리스트에 원소 삽입

문제

어서와! 자료구조와 알고리즘은 처음이지? - 2강 실습: (1) 리스트에 새로운 요소 삽입하기

문제 설명

리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요.

인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다.

예를 들어, L = [20, 37, 58, 72, 91] 이고 x = 65 인 경우, 올바른 리턴 값은 [20, 37, 58, 65, 72, 91] 입니다.

힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다.

주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처리해야 합니다.


나의 풀이_1

  • 리스트 'l'을 sort()로 정렬
  • for문을 돌려서 answer 리스트에 넣음
    • 요소를 넣을때 answer의 기존 요소와 비교하여 넣음

solutuon.py

def solution(L, x):
    L.sort()
    # answer = []
    for idx in range(len(L)):
        if L[idx] > x and x > L[idx-1]:
            L.insert(idx, x)
            break
    answer = L
                
    return answer

실행결과 : 실패

정확성  테스트
테스트 1 〉	실패 (0.31ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.8MB)
테스트 3 〉	실패 (0.32ms, 10.8MB)
채점 결과
정확성: 33.3
합계: 33.3 / 100.0
  • index가 0일때랑 index 최대값을 생각못해서????=_=

나의 풀이_2

  • index가 0일때
    • L.insert(0, x)
  • x가 L의 모든 요소들보다 큰 정수 인 경우
    • L.append(x)

solution.py

def solution(L, x):
    L.sort()
    # answer = []
    for idx in range(len(L)):
        if idx == 0:
            if L[idx] > x:
                L.insert(0, x)
                break
        if L[idx] > x and L[idx-1] < x:
                L.insert(idx, x)
                break
    if max(L) < x:
        L.append(x)

    answer = L
    return answer

실행결과

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.8MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

다른 사람의 풀이

  • enumerate() 메소드 사용
    • 리스트를 for문 할때, index와 value를 한번에 같이 확인 가능

solution.py

def solution(L, x):

    for idx, num in enumerate(L):
        if num > x:
            L.insert(idx,x)
            break

        if L[-1] < x:
            L.append(x)
        else:
            pass

    return L

[실습_2] 리스트에서 원소 찾아내기

문제

어서와! 자료구조와 알고리즘은 처음이지? - 2강 실습: (2) 리스트에서 원소 찾아내기

문제 설명

인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 이 인덱스들로 이루어진 리스트를 반환하는 함수 solution 을 완성하세요.

리스트 L 은 정수들로 이루어져 있고 그 순서는 임의로 부여되어 있다고 가정하며, 동일한 원소가 반복하여 들어 있을 수 있습니다. 이 안에 정수 x 가 존재하면 그것들을 모두 발견하여 해당 인덱스들을 리스트로 만들어 반환하고, 만약 존재하지 않으면 하나의 원소로 이루어진 리스트 [-1] 를 반환하는 함수를 완성하세요.

예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 72 인 경우의 올바른 리턴 값은 [1, 3] 입니다.또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 83 인 경우의 올바른 리턴 값은 [2] 입니다.마지막으로 또 다른 예를 들어, L = [64, 72, 83, 72, 54] 이고 x = 49 인 경우의 올바른 리턴 값은 [-1] 입니다.

힌트 1: 리스트의 index() 메서드와 리스트 슬라이싱을 활용하는 것이 한 가지 방법이 됩니다. 리스트 슬라이싱은 아래와 같이 동작합니다.

L = [6, 2, 8, 7, 3] 인 경우L[1:3] = [2, 8]L[2:] = [8, 7, 3]L[:3] = [6, 2, 8]

힌트 2: 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 를 일으킵니다. 이것을 try ... except 로 처리해도 되고, if x in L 과 같은 조건문으로 특정 원소가 리스트 내에 존재하는지를 판단해도 됩니다


나의 풀이

  • 리스트 L에 x값이 있다면,
    • 리스트 L에서 enumerate()로 for 문을 돌려서 index와 element를 확인
      • element와 x값이 같으면,
        • answer.append(index)
  • 리스트 L에 x값이 없다면,
    • answer.append(-1)

solution.py

def solution(L, x):
    answer = []
    if x in L:
        for idx, el in enumerate(L):
            if el == x:
                answer.append(idx)
    if x not in L:
        answer.append(-1)
    return answer

실행결과

정확성  테스트
테스트 1 〉	통과 (0.08ms, 10.6MB)
테스트 2 〉	통과 (0.05ms, 10.6MB)
테스트 3 〉	통과 (0.05ms, 10.8MB)
테스트 4 〉	통과 (0.03ms, 10.7MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

다른 사람의 풀이

  • return 한줄에 lambda 식을?! ㅇㅅㅇ

solution.py

def solution(L, x):
    if x in L:
        return [i for i, y in enumerate(L) if y == x]
    else:
        return [-1]
profile
dev_pang의 pang.log

0개의 댓글