[코드 리뷰] 자료구조&알고리즘 - 2강 실습(2) 리스트에서 원소 찾아내기

*프로그래머스 - 어서와! 자료구조와 알고리즘은 처음이지? 강의를 공부한 내용을 바탕으로 작성했습니다.*

 

 

리스트에서 원소 찾아내기

 

 

1. 문제

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

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

---

2. 입력예제

예를 들어, 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] 입니다.

---

3. 힌트

힌트 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 = []
    if x in L:
        while True:
            if x in L:
                find_index = L.index(x)
                answer.append(find_index)
                L[0:find_index+1] = [0]* (find_index+1)
            else:
                break
 
    else:
        answer.append(-1)
    return answer
 

 

처음에는 위에 힌트를 참고하고 우선 리스트에 특정 원소가 존재하는 지 판단한 뒤, 만약에 있다면 L에 x가 몇 번째 인덱스에 있는지 찾고, 새로운 리스트에 이 값을 추가했다. 그리고 나서 L리스트에 0부터 찾은 인덱스까지의 값을 모두 지웠다.(-> L에 x값이 여러 개 있을 때 또 찾기 쉽도록 하려고)

 

이 코드 제출했을 때, 테스트 케이스는 통과했다. 코드가 좀 비효율적이게 보여서 질문하기에 올라온 강사님이 코드리뷰 해준 답글들을 봤는데 내 코드에서 찾은 비효율적인 부분을 파악했다.

우선 문제점은 크게 세 가지로 꼽아봤다.

① if x in L은 리스트 L의 길이에 비례하는 시간을 소요한다. 리스트 원소를 하나하나씩 뒤져서 찾기 때문에 -> 비효율적

② if x in L안에 무한 반복문과 if X in L, L.index()가 등장한다. 엄청 비효율적,,

③ if, else절 코드가 너무 중복해서 나타난다. 

 

이를 바탕으로, index() 를 사용해서 코드를 간추려 보았다.

 

 

 

 

 

- 간추린 코드

 

def solution(L, x):
    answer = []
    for _ in range(len(L)):
        try:
            find_index = L.index(x)
            answer.append(find_index)
            L[0:find_index+1] = [0]* (find_index+1)
        except:
            break
 
    if len(answer)==0:
        answer.append(-1)
    return answer
 

아예 if x in L을 사용하지 않고 try except문을 통해서 L에 x값이 있는지 파악했다. 그리고 L에 x값이 아예 없는 경우는 len(answer)이 0일 테니까 이와 같이 코드를 작성했다.

 

 

 

이 문제에서 가장 중요한 부분은 "리스트를 단 한 번만  탐색 " 하도록 하는 것이 가장 중요한 것 같다.

 

 

다른 사람의 풀이를 참고했더니 효율적이게 리스트를 한 번 탐색한 코드를 확인할 수 있었다.

 

 

 

 

- 최종 코드

 

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

for문을 통해서 한 번만 리스트를 탐색하고 리스트에 값이 없을 때까지도 잘 고려한 효율적인 코드라고 생각한다.

 

 

 

 

 

*참고사항

 

아래 코드가 아닌 위쪽의 최종 코드처럼 작성하는 것이 좋다.

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

 

 

이유는 많은 coding style guideline 에서 (반드시 엄격하게 지키지는 않지만) 하나의 함수 내에 복수 개의 return statement 를 두는 것을 (코드의 가독성과 유지보수성을 떨어뜨린다는 이유로) 피하고 있다고 한다!!