[알고리즘] 주문 관리 시스템 문제 해결하기

주문 생성, 주문 제거, 주문 조회의 기능을 가진 주문 관리 시스템을 구현

입력예시

5
1 1 # 1번 주문 생성
1 2 # 2번 주문 생성
3 2 # 2번 주문이 몇 번째인지 조회
2 1 # 1번 주문 제거
3 2 # 2번 주문이 몇 번째인지 조회

 

출력 예시

2
1

 

주문 관리 시스템

 

주문 관리 시스템 - 성능 확인

연결 리스트로 구현하였을 때 처리 속도가 너무 느림

 

시간 복잡도

 

연결 리스트의 특정 노드를 삭제하기 위해서 그 특정 노드에 접근하는 과정이 필요하다

연결 리스트의 특성에 의해 특정 원소에 접근하기 위해서는 시작 원소부터 하나씩 따라가야 한다.

연결 리스트는 어떤 노드를 삭제하기 위해서 그 노드의 이전 노드와 다음 노드가 무엇인지 알고 있어야 하기 때문이다.

 

이 단점을 개선하기 위해 연결 리스트 내에 딕셔너리를 두고, 모든 노드들의 정보를 저장하고 있도록 한다.

 

딕셔너리는 내부적으로 해시 테이블이라는 자료구조로 동작하며 어떠한 key에 대한 value를 O(1)의 시간 복잡도로 접근할 수 있다

 

딕셔너리 활용

주문번호에 대해 각 노드를 대응시키는 딕셔너리를 하나 만들어두면 removeOrder 함수를 수행할 때 삭제할 노드를 O(1)만에 찾아낼 수 있다

 

삭제할 노드를 알아냈다고 해서 끝이 아니다. 삭제할 노드의 다음 노드와 이전 노드를 알아야 하는데, 현재로서는 이전 노드에 접근할 방법이 없다. 해결하기 위해 이중 연결 리스트를 활용한다.

노드에 포인터가 두 개가 있고 각각 이전 노드와 다음 노드를 가리키는 형태의 연결 리스트를 이중 연결 리스트라고 한다.

↓

 

↓

 

node 3의 바로 접근이 가능하고 포인터를 이용하여 2 와 4로 접근이 가능하며, 2에서도 4노드로 접근이 가능

이중 연결 리스트를 이용하여 노드를 간편하게 삭제할 수 있다

 

배열이든 연결 리스트든, 주문 번호가 주어졌을 때 해당 주문이 몇 번째인지 알기 위해서는 맨 첫 번째 주문부터 하나씩 확인해봐야 한다.

 

두 자료구조 모두 비슷한 방식으로 주문 조회를 수행하는데 왜 배열이 더 빠를까?

배열의 요소들은 컴퓨터에서 물리적으로 가깝기 때문이다.

연결 리스트는 각각 별도의 객체들을 임의로 연결하는 방식으로 구현되지만 배열의 경우, 각 요소들이 컴퓨터 내부에서 매우 가깝게 위치하고 있다.

 

메모리 구조

 

배열은 메모리 주소를 나타내게 되는데 0번째 인덱스에서 다음 인덱스까지 매우 빠르게 이동이 가능하다'

 

 

 

연결리스트

연결리스트는 포인터의 형태로 임의로 엮어준것에 불과함 배열에서 순회를 할때 이웃한 인자를 스캔하는게 아닌,

별도의 객체를 찾으러 나가기 때문에 배열보다 오래걸림

따라서 전체 요소를 순회하는 연산 또한 배열이 더 유리하다

 

 

알고리즘이 같더라도 데이터의 처리에 따라 성능이 다르다. 따라서 데이터의 입출력과 문제 상황을 잘 파악하여 적절한 자료구조를 선택해야 한다.

 

코드 구현

입력

첫째 줄에 주문관리 시스템이 처리할 명령의 개수를 의미하는 정수 n이 입력됩니다.

둘째 줄부터 n개의 줄에 걸쳐서 명령의 정보가 주어집니다.

명령은 공백으로 구분된 2개의 정수로 입력되며, 3가지 종류가 있습니다.

1. 1 x의 경우 주문번호 x를 추가
2. 2 x의 경우 주문번호 x를 삭제
3. 3 x의 경우 주문번호 x를 조회

입력 예시 1

10
1 1
1 2
1 4
2 2
3 1
3 4
1 2
2 1
1 1
3 2

출력 예시 1

1
2
2

 

배열로 구현

'''
orderManager 클래스를 완성
'''

class orderManager :
    '''
    주문을 처리하는 class를 작성
    '''

    def __init__(self) :
        
        self.data = []

    def addOrder(self, orderId) :
        '''
        주문번호 orderId를 추가
        '''
        self.data.append(orderId)

    def removeOrder(self, orderId) :
        '''
        주문번호 orderId를 제거
        '''
        self.data.remove(orderId)

    def getOrder(self, orderId) :
        '''
        주문번호 orderId가 몇 번째로 처리될지를 반환

        만약 주문번호 orderId가 존재하지 않으면 -1을 반환
        '''
        for i in range(len(self.data)):
            if self.data[i] == orderId:
                return (i + 1)
            
        return -1