배열, 연결리스트 실습

1. 최댓값 기계

• 문제 :
  machine.addNumber(x) : 정수 x를 최댓값 기계 machine에 추가합니다.
  machine.removeNumber(x) : 정수 x를 최댓값 기계 machine으로부터 제거합니다. 만약 정수 x가 최댓값 기계 내에 없다면 아무 일도 일어나지 않습니다.
  machine.getMax() : 최댓값 기계 machine이 갖고있는 숫자들 중 최댓값을 반환합니다.
• 첫 번째 줄에 최댓값 기계가 수행할 명령의 수를 나타내는 정수 n을 입력합니다. ( 500≤n≤55000 )
• 두 번째 줄부터 n개의 줄에 걸쳐 수행할 명령을 입력합니다. 명령의 종류는 다음과 같습니다.
• 0 x : 정수 x를 입력
  1 x : 정수 x를 제거
  2 : 최댓값 반환
• 코드

class maxMachine :
    def __init__(self) :
        self.num=[]

    def addNumber(self, n) :
        self.num.append(n)

    def removeNumber(self, n) :
        self.num.remove(n)

    def getMax(self) :
        return max(self.num)
        
main함수에서
n = int(input())		// n번 반복.
    for i in range(n) :
        line = [int(v) for v in input().split()]
        if line[0] == 0 :
            myMachine.addNumber(line[1])
        elif line[0] == 1 :
            myMachine.removeNumber(line[1])
        elif line[0] == 2 :
            print(myMachine.getMax())

2-1. 구슬 넣기(배열)

• 문제
  토끼는 n개의 구슬이 있으며, 각 구슬은 1부터 n까지의 번호를 하나씩 갖고 있습니다. 또한, 토끼는 양 쪽이 뚫려있고 투명하지 않은 관을 갖고 있습니다. 토끼는 n개의 구슬을 이 파이프에 무작위로 넣은 후에, 최종적으로 구슬이 파이프 속에서 어떻게 배치되어 있는지를 확인하고자 합니다.
• 입력
  입력의 첫 번째 줄에는 구슬의 개수 n이 주어집니다. (100≤n≤200000)
  두 번째 줄부터는 토끼가 구슬을 넣는 행위가 주어집니다.
  각 줄은 두 개의 정수 a, b로 이루어지며, 이 뜻은 구슬 a를 왼쪽 혹은 오른쪽으로 넣는다는 의미입니다. (1≤a≤1000000000)
  (b가 0이면 왼쪽, b가 1이면 오른쪽이며 그 외의 입력은 주어지지 않는다)
• 코드

class ListPipe:
    def __init__(self) :
        self.myPipe = []
    def addLeft(self, n) :
        self.myPipe.insert(0,n)
    def addRight(self, n) :
        self.myPipe.append(n)
    def getBeads(self) :
        return self.myPipe

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

2-2. 구슬 넣기(연결 리스트)

class LinkedListElement :
    def __init__(self, val, ptr) :
        self.value = val        # 정수
        self.myNext = ptr       # 또 다른 element

class LinkedListPipe:
    def __init__(self) :
        '''
        리스트 myPipe를 만듭니다. 이는 구슬의 배치를 저장합니다.
        '''
        # 연결 리스트의 시작 정점과 끝 정점을 가리키는 것이 각각
        # start, end인데 얘들을 none으로 초기화
        # 즉, 한마디로 초기화임...
        self.start = None
        self.end = None
        self.mypipe = []

    def addLeft(self, n) :
        '''
        파이프의 왼쪽으로 구슬 n을 삽입합니다.
        '''
        if self.start == None and self.end == None:
            # == 비어있다.
            elem = LinkedListElement(n,None)
            self.start = elem
            self.end = elem
        else:
            elem = LinkedListElement(n, self.start)
            # 새로 변경..
            self.start = elem

    def addRight(self, n) :
        '''
        파이프의 오른쪽으로 구슬 n을 삽입합니다.
        '''
        if self.start == None and self.end == None:
            # == 비어있다.
            elem = LinkedListElement(n,None)
            self.start = elem
            self.end = elem
        else:
            elem = LinkedListElement(n, None)
            # 새로 변경..
            self.end.myNext = elem
            self.end = elem

    def getBeads(self) :
        '''
        파이프의 배치를 list로 반환합니다.
        '''
        result = []
        # 현재 노드
        current = self.start
        while current != None:
            result.append(current.value)
            current = current.myNext
        return result

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

    myPipe = LinkedListPipe()

    result = []

    return result

3. 내림차순 정렬하기

• 수들이 주어질 때 내림차순으로 정렬하여 출력하는 프로그램을 만들되, 최댓값 기계의 자료구조를 이용하여 푸시오.
• 입력
  첫째줄에 n개의 정수들이 공백으로 구분되어 입력됩니다. (100≤n≤200000)

class maxMachine :
    def __init__(self) :
        self.num=[]

    def addNumber(self, n) :
        self.num.append(n)

    def removeNumber(self, n) :
        self.num.remove(n)

    def getMax(self) :
        return max(self.num)

def sorting(myList) :
    myMachine = maxMachine()
    result = []
    for i in myList:
        myMachine.addNumber(i)
    for i in range(len(myList)):
        mymax = myMachine.getMax()
        result.append(mymax)
        myMachine.removeNumber(mymax)

    return result
    

4-1. 주문관리 시스템(배열)

• 문제
  addOrder(x) : 주문번호 x를 주문 관리 시스템에 추가합니다. return 값은 없습니다.
  removeOrder(x) : 주문번호 x를 주문 관리 시스템에서 제거합니다. 입력되는 x 값은 항상 주문 관리 시스템에 존재함이 보장됩니다. return 값은 없습니다.
  getOrder(x) : 입력한 주문번호 x가 주문 관리 시스템에서 몇 번째로 처리되는지를 return 합니다. 만약 입력한 주문번호 x가 주문 관리 시스템 내에 존재하지 않는 경우 -1을 return 합니다.
  예를들어 addOrder(1), addOrder(2), addOrder(4)를 차례로 실행하면 주문 관리 시스템에 1 - 2 - 4로 입력된 순서대로 저장됩니다. 이 상태에서 removeOrder(2)를 실행하면 주문 관리 시스템에서 주문번호 2를 찾아낸 다음 제거하여 1 - 4 로 주문 관리 시스템이 업데이트됩니다.
  이 상황에서 getOrder(1)를 실행한 결과는 주문번호 1이 처리될 순서인 1이 반환되며, getOrder(4)를 실행한 결과는 주문번호 4가 처리될 순서인 2가 반환될 것입니다.

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

    def addOrder(self, orderId) :
        self.data.append(orderId)

    def removeOrder(self, orderId) :
        self.data.remove(orderId)

    def getOrder(self, orderId) :
        for i in range(len(self.data)):
            if self.data[i] == orderId:
                return (i+1)
        return -1

4-2. 주문관리 시스템(연결 리스트)

class LinkedListElement :
    def __init__(self, data, myPrev, myNext) :
        self.data = data
        self.myPrev = myPrev
        self.myNext = myNext



class orderManager :
    def __init__(self) :
        self.start = None
        self.end = None

    def addOrder(self, orderId) :
        o = LinkedListElement(orderId, None, None)
        if self.start == None and self.end == None:
            self.start = o
            self.end = o
        else:
            self.end.myNext = o
            o.myPrev = self.end
            self.end = o

    def removeOrder(self, orderId) :
        if self.start == None and self.end == None:
            return
        current = self.start
        while current != None:
            if current.data == orderId:
                prevElem = current.myPrev
                nextElem = current.myNext

                if prevElem != None:
                    prevElem.myNext = nextElem
                if nextElem != None:
                    nextElem.myPrev = prevElem
                if current == self.end:
                    self.end = prevElem
                if current == self.start:
                    self.start = nextElem
            
            current = current.myNext

    def getOrder(self, orderId) :
        cnt=0
        if self.start == None and self.end == None:
            return -1
        current = self.start
        while current != None:
            if current.data == orderId:
                return cnt + 1

            current = current.myNext
            cnt += 1
        
        return -1

4-2. 주문관리 시스템(연결 리스트 개선ver.)

• 일반 연결 리스트는 수정은 빠르나 탐색은 매우 느리다. 이를 해쉬태이블을 이용하여 개선해보고자 한다.

class LinkedListElement :
    def __init__(self, data, myPrev, myNext) :
        self.data = data
        self.myPrev = myPrev
        self.myNext = myNext

class orderManager :
    def __init__(self) :
        self.start = None
        self.end = None
        self.elems = {}     #주문번호를 저장하는 딕셔너리.

    def addOrder(self, orderId) :
        elem = LinkedListElement(orderId, None, None)
        self.elems[orderId] = elem
        if self.start == None and self.end == None:
            self.start = elem
            self.end = elem
        else:
            self.end.myNext = elem
            elem.myPrev = self.end
            self.end = elem

    def removeOrder(self, orderId) :
        if self.start == None and self.end == None:
            return
# 전에는 while문을 돌려가며 찾았지만 지금은 cur에 바로 집어 넣음.       
        cur = self.elems[orderId]
        if self.start == cur and self.end == cur:
            self.start = None
            self.end = None
        elif self.start == cur:
            self.start = cur.myNext
            (cur.myNext).myPrev = None
        elif self.end == cur:
            self.end = cur.myPrev
            (cur.myPrev).myNext = None
        else:
            cur.myPrev.myNext = cur.myNext
            cur.myNext.myPrev = cur.myPrev


    def getOrder(self, orderId) :
        cnt = 1
        cur = self.start

        while cur != None:
            if cur.data == orderId:
                return cnt
            cur = cur.myNext
            cnt = cnt + 1
        return -1

에러

list object cannot be interpreted as an integer

주로 for문의 range함수를 쓸 때 나오는데 range함수 안에 배열만 짚어넣고 안된다고 한다. len을 넣어야만 해결 가능.