[Python] 연결 리스트 문제 해결

 

구슬 넣기 문제

양쪽이 열려있는 파이프에 구슬을 넣고 결과를 출력해보자. 왼쪽 또는 오른쪽으로 구슬을 넣을 수 있다.

 

입력예시

3
1 0 # 왼쪽으로 1 삽입
2 1 # 오른쪽으로 2 삽입
3 0 # 왼쪽으로 3 삽입

출력 예시

3 1 2

파이프를 갖는 클래스를 구현하여 자료구조 구현

추상적 자료형은 구현 방법을 지정하지 않으므로 파이프를 어떻게 구현하든 상관이 없다.

 

 

 

이 문제를 가장 잘 해결할 수 있는 '덱' 이라는 자료구조가 있음(참고)

 

명령 왼쪽으로 1 삽입 오른쪽으로 2 삽입 왼쪽으로 3 삽입

 

 

배열의 특성에 의해 왼쪽으로 구슬을 삽입하는 경우 파이프 내의 모든 구슬을 한 칸씩 옮겨야 하는 연산이 필요하다.

 

좋은 해법인지 생각해보기

수행하는 명령의 수가 적을수록 시간이 덜 걸린다. (똑같은 연산을 해도 수행하는 명령에 따라서 걸리는 시간이 적은게 좋은코드)

sum = 0
for i in range(30) :
sum = sum + 1

sum = 0
for i in range(300000) :
sum = sum + 1

 

시간 복잡도

알고리즘이 문제를 해결하는 데 걸리는 시간을 정량화하여 나타낼 수 있는 방법 일반적으로,

문제에서 주어지는 최악의 경우에 대한 소요 시간을 나타내는 데 사용한다

(최악을 세는 이유는 특정 일부케이스에서만 빠르게 동작하고 다른코드에서는 그렇지 않다면 빠르게 동작하지 않는다고 볼 수 있기 때문이다.)

 

대략 몇 개의 명령이 수행되는가? - 배열

1. 숫자 하나를 왼쪽으로 삽입

2. 숫자 하나를 오른쪽으로 삽입

 

시간 복잡도는 일반적으로 최악의 경우를 고려해야 한다.

구슬을 왼쪽으로 삽입하면, 배열 내에서 한 칸씩 이동해야 하므로 느리다.

그렇다면, 최악의 경우의 연산 횟수는?

 

구슬 n개를 모두 왼쪽으로만 삽입

구슬이 3개라면? 1 + 2 + 3 = 6

구슬이 5개라면? 1 + 2 + 3 + 4 + 5 = 15

구슬이 n개라면? n(n+1)/2

 

즉, 이 문제를 배열로 해결하였을 때의 시간 복잡도는

O()는 최악 조건의 시간 복잡도를 의미하는 기호로, Big-O Notation이라고 합니다.

 

왼쪽으로 1 삽입

오른쪽으로 2 삽입

왼쪽으로 3 삽입

연결 리스트는 구슬을 어디로 넣든 한 번의 연산으로 수행한다.

 

구슬 n개를 모두 왼쪽으로만 삽입

구슬이 3개라면? 1 + 1 + 1 = 3

구슬이 5개라면? 1 + 1 + 1 + 1 + 1 = 5

구슬이 n개라면? n

 

즉, 이 문제를 연결 리스트로 해결하였을 때의 시간 복잡도는

연결 리스트로 구현한 것이 배열로 구현한 것보다 빠르다.

이 문제에서는 연결 리스트가 더 좋다.

 

먼저 배열을 이용하여 문제를 해결해 보자

 

입력

입력의 첫 번째 줄에는 구슬의 개수 nnn이 주어집니다. (100≤n≤200000100 \le n \le 200000100≤n≤200000)

두 번째 줄부터는 토끼가 구슬을 넣는 행위가 주어집니다.

각 줄은 두 개의 정수 aaa, bbb로 이루어지며, 이 뜻은 구슬 aaa를 왼쪽 혹은 오른쪽으로 넣는다는 의미입니다. (1≤a≤10000000001 \le a \le 10000000001≤a≤1000000000)

(bbb가 0이면 왼쪽, bbb가 1이면 오른쪽이며 그 외의 입력은 주어지지 않는다)

출력

최종적으로 구슬이 파이프 속에서 어떻게 배치되어 있는지를 출력한다.

입력예시

3
1 0
2 1
3 0

출력

3 1 2

 

풀이

'''
1. ListPipe 클래스를 완성하세요. 
2. processBeads 함수를 완성하세요.
'''

class ListPipe:
    '''
    List를 이용하여 다음의 method들을 작성하세요.
    '''
    def __init__(self) :
        '''
        리스트 myPipe를 만듭니다. 이는 구슬의 배치를 저장합니다.
        '''
        self.myPipe = []
        pass

    def addLeft(self, n) :
        '''
        파이프의 왼쪽으로 구슬 n을 삽입합니다.
        '''
    
        self.myPipe.insert(0, n)

    def addRight(self, n) :
        
        self.myPipe.append(n)

    def getBeads(self) :
        '''
        파이프의 배치를 list로 반환합니다.
        '''
        return self.myPipe


def processBeads(myInput) :
    '''
    구슬을 파이프에 넣는 행위가 myInput으로 주어질 때, 구슬의 최종 배치를 리스트로 반환하는 함수를 작성

    myInput[i][0] : i번째에 넣는 구슬의 번호
    myInput[i][1] : i번째에 넣는 방향

    예를 들어, 예제의 경우 

    myInput[0][0] = 1, myInput[0][1] = 0,
    myInput[1][0] = 2, myInput[1][1] = 1,
    myInput[2][0] = 3, myInput[2][1] = 0


    '''

    myPipe = ListPipe()

    for bead, direction in myInput:
        if direction ==0 :
            myPipe.addLeft(bead)
        elif direction == 1:
            myPipe.addRight(bead)
    result = myPipe.getBeads()

    return result