파이썬) 선형 배열 실습

1번 문제) 정렬된 리스트에 원소 삽입

문제 설명

 

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

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

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

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

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

 

정답

def solution(L, x):
    answer = L
    for i in range(0,len(L)):
        if x > L[i] and x<L[i+1]:
            answer.insert(i+1,x)
            break
        elif  x> L[-1]:
            answer.append(x)
            break
        elif x< L[0]:
            answer.insert(0,x)   
            break
    return answer

• x가 L의 원소들의 중간에 있어야 할 때

for문을 이용해 임의의 원소 L[i]보다 크고 그 다음 원소 L[i+1]보다 작은 경우가 나온다면 insert를 이용해 i+1번째 index에 x를 삽입한다.

 

• x가 L의 원소들보다 클 때

L은 오름차순으로 정렬된 리스트이기 때문에 L의 마지막 원소보다 크면 자동으로 L의 모든 원소들 보다 크게 된다. 따라서 

x가 L의 마지막 원소 L[-1]보다 크면 append로 추가하는 것으로 코드를 구성했다. 이 때, insert 대신 append를 사용한 이유는 append가 insert보다 실행속도가 빠르기 때문이다. insert를 이용하는 것도 정답이 될 수 있지만 자료구조의 취지에 맞게 코드를 구성했다.

 

• x가 L의 원소들보다 작을 때

위와 마찬가지로 x가 첫 원소 L[0]보다 작다면 insert를 이용해 첫번째 자리에 삽입하는 것으로 코드를 구성했다.

 

 

 

 

 

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" 과 같은 조건문으로 특정 원소가 리스트 내에 존재하는지를 판단해도 됩니다.

 

정답 

def solution(L, x):
    answer = []
    for i in range(len(L)):
        if L[i] == x:
            answer.append(i)
    if x not in L:
        answer.append(-1)
    return answer

우선 빈 리스트 answer를 만들고 for문을 이용해 L의 원소들이 x와 같다면 append를 이용해 answer 리스트에 추가하는 코드이다. 처음에 문제 제목을 읽고 index()를 이용하는 문제라 생각했으나, index의 실행 속도는 리스트의 길이에 비례해 길어진다. 그러나 append는 리스트의 길이와 상관없이 실행 속도는 index보다 빠르며 위 문제는 append만으로도 해결할 수 있는 문제이다. 

x가 L의 원소내에 없는 경우는 x not in L이라는 조건문을 이용해 -1을 return하도록 힌트2를 참고하였다.

 

 

* 위 두 문제의 정답은 필자가 개인적으로 구성한 코드이며, 최적의 알고리즘으로 구성된 코드는 아님을 참고하길 바란다.