[자료구조][파이썬으로 쉽게 풀어쓴 자료구조] 03 리스트 문제풀기

728x90

 

 

 

🙆‍♂️리스트

---

"""
리스트
"""

class ArrayList:
    def __init__(self):
        self.items=[]
    def insert(self,pos,elem):
        self.items.insert(pos,elem)
    def delete(self,pos):
        return self.items.pop(pos)
    def isEmpty(self):
        return self.size()==0
    def getEntry(self,pos):
        return self.items[pos]
    def size(self):
        return len(self.items)
    def clear(self):
        self.items=[]
    def find(self,item):
        return self.items.index(item)
    def replace(self,pos,elem):
        self.items[pos]=elem
    def sort(self):
        self.items.sort()
    def merge(self,lst):
        self.items.extend(lst)
    def display(self, msg='ArrayList:'):
        print(msg,"항목수=",self.size(),self.items)

위의 리스트 class를 사용

 

🙋‍♂️리스트 문제

---

3.1-1. 구현한 리스트 중 insert() 연산을 사용하지 않고 append()를 사용해서 다시 구현해보라.

    def insert(self,pos,elem):
        self.itemsTemp = self.items[:pos]
        self.itemsTemp.append(elem)
        self.itemsTemp.extend(self.items[pos:]) 
        self.items = self.itemsTemp

슬라이싱을 사용해서 해당 pos에 입력된 elem이 들어가도록 할 수 있었습니다.

 

3.1-2. delete() 연산을 파이썬 리스트의 pop(-1)을 사용하여 다시 구현하라, 즉 리스트의 후단 항목만을 삭제하는 것이다. 이제 삭제할 위치 이후의 모든 항목을 앞으로 이동하는 코드를 작성해야 한다.

    def delete(self, pos):
        self.itemsTemp = self.items[:pos+1]
        self.itemsTemp.pop(-1)
        self.itemsTemp.extend(self.items[pos+1:])
        self.items = self.itemsTemp

append를 이용하는 것과 비슷하게 구현을 했습니다.

슬라이싱을 사용하여 pos+1 전까지 자르고 (그러면 맨 마지막에 pos에 해당하는 값이 옵니다.)

이 때 pop(-1)을 사용하여 리스트 맨 마지막의 값을 제거해줍니다.

그리고 원래 배열의 pos+1부터 마지막까지 값을 뒤에 붙여주면 끝입니다.

 

3.1-3. find() 연산을 파이썬 리스트의 index()를 사용하지 않고 구현하라

    def find(self,item):
        for i,v in enumerate(self.items):
            if v==item:
                return i

사실 find()함수라고 또 있지만 다른 방법을 사용해 보면

enumerate를 사용해서 배열의 index와 value를 동시에 for문 돌릴 수 있는 enumerate를 사용했습니다.

그래서 item 값과 반복문을 돌린 value값이 같다면 인덱스를 return 하는 것입니다.

 

3.1-4. merge() 연산을 파이썬 리스트의 extend()를 사용하지 않고 직접 구현

    def merge(self,lst):
        for i in lst:
            self.items.append(i)

이건 쉽죠?

 

🙋‍♂️라인편집기 코드

---

"""
라인 편집기
"""

def myLineEditor():
    lst = ArrayList()
    while True:
        com = input("Select Menu i-insert, d-delete, r-replace, p-print,l-file_read, s-save, q-quit\n=>")
        #insert
        if com == 'i':
            pos = int(input("Insert line number : "))
            st = input("Insert string : ")
            lst.insert(pos,st)
        elif com == 'd':
            pos = int(input("Remove line number :"))
            lst.delete(pos)
        elif com == 'r':
            pos = int(input("Replace line number : "))
            st = input("Replace string")
            lst.replace(pos,st)
        elif com == 'q': return
        elif com == 'p':
            for line in range(lst.size()):
                print(f'[{line}] {lst.getEntry(line)}')
        elif com == 'l':
            filename='text.txt'
            openFile=open(filename,"r")
            lines=openFile.readlines()
            for line in lines:
                lst.insert(lst.size(),line.rstrip('\n'))
            openFile.close()
        elif com=='s':
            filename='text.txt'
            saveFile = open(filename,"w")
            for i in range(lst.size()):
                saveFile.write(lst.getEntry(i)+"\n")
            saveFile.close()
            

myLineEditor()

 

🙋‍♂️라인편집기 문제

---

3.2-1.지정된 파일이 아니라 사용자가 입력하는 파일을 읽을 수 있도록 'l' 명령 처리 코드를 수정. 

        elif com == 'l':
            filename=input("Write filename : ")
            openFile=open(filename,"r")
            lines=openFile.readlines()
            for line in lines:
                lst.insert(lst.size(),line.rstrip('\n'))
            openFile.close()

input을 통해서 filename 변수에 값 저장한다.

 

3.2-2.지정된 파일이 아니라 사용자가 입력하는 파일에 현재 문서를 저장할 수 있도록 's' 명령 처리 코드를 수정. 

        elif com=='s':
            filename=input("Save filename : ")
            saveFile = open(filename,"w")
            for i in range(lst.size()):
                saveFile.write(lst.getEntry(i)+"\n")
            saveFile.close()

 

3.2-3.문자열을 입력하면 이 문자열을 포함하고 있는 라인들만을 찾아 출력할 수 있는 'f' 명령을 추가하라.

        elif com=='f':
            for line in range(lst.size()):
                if 'f' in lst.getEntry(line):
                    print(f'[{line}] {lst.getEntry(line)}')

 

 

 

🙋‍♂️집합 코드

---

"""
집합
"""

class Set:
    def __init__(self):
        self.items=[]
    def size(self):
        return len(self.items)
    def display(self,msg):
        print(msg,self.items)
    def containse(self,item):        #요소 포함 체크
        return item in self.items
    def insert(self,elem):
        if elem not in self.items:
            self.items.append(elem)
    def delete(self, elem):
        if elem in self.items:
            self.items.remove(elem)
    def union(self,setB):                  #합집합
        setC=Set()
        setC.items = list(self.items)
        for elem in setB.items:
            if elem not in self.items:
                setC.items.append(elem)
        return setC
    def intersect(self, setB):              #교집합
        setC=Set()
        for elem in setB.items:
            if elem in setB.items:
                setC.items.append(elem)
        return setC
    def difference(self, setB):            #차집합
        setC=Set()
        for elem in setB.items:
            if elem not in setB.items:
                setC.items.append(elem)
        return setC

 

🙋‍♂️집합 문제

---

3.3.1 contains() 연산을 in 연산자를 사용하지 않고 다시 구현하라. 집합의 항목을 하나씩 비교해야 할 것이다.

    def containse(self,item):        #요소 포함 체크
        i=0
        tof = True
        while i==0 or i<self.size():
            if self.size()==0:
                tof = False
                break
            else:
                if self.items[i] == item:
                    tof = True
                    break
                else:
                    i+=1
                    tof = False
        return tof

여기서 중요한 개념은 안에 안들었을 때에 대한 처리다.

 

3.3.2 delete() 연산을 in 연산자와 파이썬 리스트의 remove()를 사용하지 않고 다시 구현하라. 이를 위해 앞에서 구현한 contains와 파이썬 리스트의 pop를 사용하라.

    def delete(self, elem):
        if self.containse(elem)==True:
            self.items.pop(self.items.index(elem))

 

3.3.3  insert(), union(), intersect(), difference() 연산도 모두 in 연산자를 사용하지 않고 contains() 메소드를 이용해 다시 구현하라.

    def insert(self,elem):
        if self.containse(elem):
            self.items.append(elem)

    def union(self,setB):                  #합집합
        setC=SetT()
        setC.items = list(self.items)
        i=0
        if setB.size()==0:
            return setC
        while i< setB.size():
            if not self.containse(setB.items[i]):
                setC.items.append(setB.items[i])
            i+=1
            
        return setC

    def difference(self, setB):            #차집합
        setC=SetT()
        i=0
        if setB.size()==0:
            return setC
        while i<setB.size():
            if not setB.containse(self.items[i]):
                setC.items.append(self.items[i])
            i+=1
        return setC

 

3.4 다항식

class Polynomial:
    # 방법2를 사용하여 구현한 Polynomial
    def __init__(self):
        self.coef = []
    
    def degree(self):
        return len(self.coef) - 1 
    
    def add(self, polyB):    
        p = Polynomial()
        if self.degree() > polyB.degree():
            for deg in range(polyB.degree()+1):
                p.coef.append(self.coef[deg] + polyB.coef[deg])
            for deg in range(polyB.degree()+1,self.degree()+1):
                p.coef.append(self.coef[deg])
        else:
            for deg in range(self.degree()+1):
                p.coef.append(self.coef[deg] + polyB.coef[deg])
            for deg in range(self.degree()+1,polyB.degree()+1):
                p.coef.append(polyB.coef[deg])
        return p
    
    def subtract(self, polyB):    
        p = Polynomial()
        if self.degree() > polyB.degree():
            for deg in range(polyB.degree()+1):
                p.coef.append(self.coef[deg] - polyB.coef[deg])
            for deg in range(polyB.degree()+1,self.degree()+1):
                p.coef.append(self.coef[deg])
        else:
            for deg in range(self.degree()+1):
                p.coef.append(self.coef[deg] - polyB.coef[deg])
            for deg in range(self.degree()+1,polyB.degree()+1):
                p.coef.append(polyB.coef[deg])
        return p
    
    def mult(self, polyB):
        p = Polynomial()
        p.coef = [0] * (self.degree() + polyB.degree() + 1)
        
        for degA in range(self.degree(), -1, -1):           
            for degB in range(polyB.degree(), -1, -1):               
                targetDeg = (degA + degB)
                p.coef[targetDeg] += self.coef[degA]*polyB.coef[degB]
        return p
    
    def display(self, msg):
        print(msg, end='')
        for deg in range(self.degree(), 0, -1):            
            print(self.coef[deg], "x^", deg, "+", end='')
        print(self.coef[0])
        
    def evaluate(self, x): # O(n)
        output = 0
        for deg in range(self.degree(), -1, -1):   
            output = output + self.coef[deg] * (x ** deg)
        return output
    
def read_poly():
    p = Polynomial()
    deg = int(input("다항식의 최고 차수를 입력하세요: "))
    for n in range(deg, -1, -1):
        coef = int(input(f"x^{n}항의 계수 : "))
        p.coef.append(coef)
    p.coef.reverse()    
    return p