[프로그래머스] 종이접기

https://programmers.co.kr/learn/courses/30/lessons/62049

프로그래머스

---

[코드]

def solution(n):
    answer=[0]
    for i in range(n-1):
        answer=answer+[0]+[bit^1 for bit in answer[::-1]]
    return answer

---

[실패코드] 테스트케이스 17개중 15개 맞음 (2문제는 시간초과)

def solution(n):
    answer=[0]
    if n==1:
        return answer
    
    for i in range(2,n+1):
        cnt=2**(i-2) #0,1숫자쌍 개수
        for j in range(cnt):
            answer.insert(j*4,0)
            answer.insert(j*4+2,1)
    
    return answer

코드 세운 근거

(n=1) arr=[0]

(n=2) arr=[0] -> arr=[0, 0, 1] (2개 숫자끼워넣기)

(n=3) arr[0, 0, 1] -> arr=[0, 0, 1, 0, 0, 1, 1] (4개 숫자 끼워넣기)

 

아래의 코드도 위의 코드와 동일한 결과를 가졌다.

아래의 코드의 경우에는 0과 1로 구성된 tmp리스트에

n-1일때의 answer원소들을 홀수번째 인덱스에 끼워넣는 방식이다.

def solution(n):
    answer=[0]
    if n==1:
        return answer
    
    for i in range(2,n+1):
        cnt=2**(i-2) #0,1숫자쌍 개수
        tmp=([0]+[1])*cnt
        for idx,e in enumerate(answer):
            tmp.insert(idx*2+1, e)
        answer=tmp
    
    return answer

 

풀어보면서 느낀것은 insert()를 이용하지 않고 풀어내면

시간초과를 벗어 날 수 있을 것같다.

그리고 시간복잡도는 O(n^2)이다.