알고리즘 - stack

프로그래머스 lv.1 - stack "같은 숫자는 싫어"

효율성 부분에서 좋지 못한 점수를 얻어 통과하지 못했다.

효율성,,
중요하나보다.

기존 코드

def solution(arr):
    
    i = 0
    lens = len(arr)
    for _ in range(0,lens-1):
        if arr[i] != arr[i+1]:
            i+=1
        else:
            arr.pop(i)
        
        
    print('Hello Python')
    return arr

같은 숫자를 제외를 시켜야하는 문제

• list 로 입력값이 주어지기에 인덱스로 접근

• pop을 사용하여 중복 숫자 제거

• 중복숫자 없을 경우 i += 1 로 인덱스 순차적으로 증가 후 비교

크게 위 3가지 개념으로 문제에 접근했다.

정확도 - 100
효율성 - 불통
코드였다.

개선해야될 부분

1. pop () 을 잘쓰자

pop()을 어떻게 사용하느냐에 따라 , 효율성이 달라진다는 것을 알았다.

1.pop()
2.pop(n)

pop()

• 인덱스 마지막을 지우기 때문에
• 효율성 O(1)

pop(n)

• 지워야할 인덱스를 찾아야하기 떄문에
• 효율성 O(N)

으로 차이가 생긴다.

2. 효율성이 부족하다 싶다면, 과감히 다른 방식으로 접근

OUT OF INDEX 에러를 방지하고,
APPEND를 사용하여 풀기

바뀐 풀이

def solution(arr):
    
    result = []
    result.append(arr[0])
    
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            continue
        else:
            result.append(arr[i])
        
    print('Hello Python')
    return result

• 위 방식의 요점은

1. out of index 에러를 방지하고자 ,
i와 i+1 인덱스를 비교하는 것이 아닌,
i와 i-1 인덱스를 비교하고.

이렇게 해도 outofindexerror가 발생하기에,

먼저 첫번쨰 인덱스 0 값을 result 안에 append해주고,

for문을 할때,

range(0,len(arr)) -> range(1,len(arr))
로 변경해준다.