programmers(6)_같은_숫자는_싫어

작성일 | In

문제: 같은 숫자는 싫어

level1

배열 arr가 주어진다. 배열 arr의 원소는 숫자 0부터 9까지 이루어져 있다. 이때 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 한다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 한다.

생각한 방법

  • 집합을 쓰면 어떨까?
  • 집합 생성: s1 = set([1,2,3]) s1 = set('Hello')
  • 예제에서 보듯 연속된 수들이 나올 경우에만 중복을 제거하는 거라 사용 불가 [1,1,3,3,0,1,1]이라면
  • [1,3,0,1]을 출력해야 하므로

  • 집합을 쓴다면, 중복된 리스트가 나올 경우 해당 리스트를 분해한뒤 중복 제거한 뒤, 다시 결합해줘야 하는 방법을 사용해야함

  • 원소를 하나씩 검사하면서 (인덱스 1부터 시작.) -> 원소가 왼쪽과 같으면 -> 해당원소 x를 제거해주는 것도 방법

주의할 사항

  • for i in range(len(arr)) 이러한 for문 안에서, del[arr[i]를 적어버리면, 리스트의 갯수가 변하는데 for문은 해당 갯수만큼 리스트를 돌게 되므로 IndexError: list index out of range가 발생한다.

  • 또한 원소를 지움으로써 인덱스가 달라지므로 이를 고려해야한다.

  • 새로운 리스트에 입력을 받고, 해당 리스트가 있다면 리스트에서 제거해주는 방식으로 해보자. -> 이 방식은 연속적으로 있는 리스트를 지울 수 없다. -> 인덱스를 우선 입력 받자 -> 인덱스를 입력 받아서 어떻게 지워주지 ? -> 거꾸로 지워주면 된다. 그렇다면, 애초에 거꾸로 한다면 ?

  • 거꾸로 인덱스를 고려하면 제거 할 때, 숫자가 바뀌지 않을까? -> 거꾸로 하면 된다.

  • 만약, 앞에서부터 나아간다면, 어떠한 특정 값을 채워주면 되지 않을까? -> 그리고 그 특정값을 제거해서 리스트를 만들 수도 있다.

시간초과

def solution(arr):
    for i in range(len(arr)-2, -1, -1):
        if(arr[i] == arr[i+1]):
            arr.pop(i+1)
    return arr
  • 실행결과는 모두 통과했지만, 시간초과에 걸렸다. - 선형 방식으로 탐색하면 시간초과에 걸린다는 뜻이다.
  • Q) 병합정렬처럼 divide and conquer방식을 사용해야 할까?
  • Q) 이진 탐색을 이용해서 중복을 찾아야 할까? -> 값이 정렬되어 있어야 하므로 이건 아니다.
  • pop method를 써서 리스트를 없앨 때, 해당 리스트를 선형적으로 조사해가면서 찾는 것 같다.

해결

  1. 위에서 분석을 잘못했다. del.arr[i+1]처럼 원본 배열을 지우는 함수를 쓰기에 문제가 발생했던 거다.
  2. arr.pop(i+1)과 같은 method를 쓰면, 해당 인덱스를 순차적으로 찾아가므로, 시간이 초과된다.
  3. 따라서, 새로운 리스트를 만들고, 굳이 반대로 찾아줄 필요 없이 조건을 !=로만 바꿔주면 문제가 해결 된다.
def solution(arr):
    idxList = [arr[0]]
    for i in range(1, len(arr)):
        if(arr[i-1] != arr[i]):
            idxList.append(arr[i])
    return idxList

다른 사람 풀이

def no_continuous(s):
    a = []
    for i in s:
        if a[-1:] == [i]: continue
        a.append(i)
    return a

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print( no_continuous( "133303" ))
  • 배열 array가 주어진다고 문제에서 명시 되어있는데, 입력에 문자열이 들어간다
  • 아마 문제가 개편된 것 같아
  • 위 코드는 문자열을 입력 받아서, a[-1:]이 리스트를 리턴하므로 [i]와 같은지 비교한다
  • 같으면 계속 진행하고, 같지 않다면, a의 배열에 append 해주는 방식이다.

다른 사람 풀이2

def no_continuous(s):
    # 함수를 완성하세요
    return [s[i] for i in range(len(s)) if s[i] != s[i+1:i+2]]

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print( no_continuous( "133303" ))
  • 리스트 함축을 이용한 방법이다.
  • 리스트 갯수만큼 for문을 돌면서, 리스트의 [i]와 리스트[i+1:i+2]가 같지 않을때, s[i]를 리턴하는 것이다.
  • 이 답안 매개변수가 문자열일 때만 동작한다. 왜냐하면 : 리스트를 슬라이스하면, 리스트가 반환되기 때문이다.
  • 문자열을 슬라이드 하면 해당 문자열만 슬라이스 되기에 상관이 없지만, 리스트의 경우 리스트의 값과 리스트를 비교하는 것이 되기 때문에 문제가 발생한다.
  • 명심하자. 리스트 슬라이스를 하면 나오는 값은 리스트다
  • 따라서 문제가 개편된 이후 답을 내기 위해선,
  • return [s[i] for i in range(len(s)) if [s[i]] != s[i+1:i+2]] 이렇게 바꿔줘야 한다.
  • 리스트 슬라이스는 index 범위가 초과되어도 오류가 발생하지 않는다.

참고자료 [프로그래머스]https://programmers.co.kr/learn/challenges

0%