[코딩테스트] 배열 / 연결리스트

배열

- 연속된 메모리를 이용한 자료구조

- 같은 자료형의 묶음

 

ADT

class Array:
    def __init__(self, size:int = 10):
        self.data = [None for _ in range(size)]
        self.size = size
    
    def isEmpty(self):
    
    def isFull(self):
    
    def insert(self, index, data):
        if 
        self.data[index] = data
    
    def add(self, data):
        if 
    
    def remove(self, index):
        
        self.data[index] = None

연결리스트

- 파편화된 메모리 사용(연속되지 않음)

- Node간의 연결에서 포인터 필요

 

ADT

class Node:
    def __init__(self, data=None) -> self:
        self.data = data
        self.prev = None
        self.next = None
        
    def setPrev(self, prev:Node = None):
        self.prev = prev
    
    def setNext(self, next:Node = None)
        self.next = next
    
    def getData(self):
        return self.data
        
    def getPrev(self):
        return self.prev
        
    def getNext(self):
        return self.next
        
class DoublyLinkedList:
    def __init__(self, size:int = 10):
        self.start = None
        self.end = None
        self.cur = None
        self.size = 0
        
    def addData(self, data):
        if self.start is None:
            self.start = Node(data)
            self.cur = self.start
            self.end = self.start
        else:
            tmp = Node(data)
            self.cur.setNext(tmp)
            tmp.setPrev(self.cur)
            self.cur = tmp
            self.end = tmp
        self.size += 1
        
    def find(self, value) -> Node|None:
        if self.start in None:
            return None
        else:
            tmp = self.start
            while tmp:
                if tmp.getDate() == value:
                    return tmp               
            
    def insert(self, index, data):
        if (self.start is not None) and (self.size > index) and (index >= 1):
            cur = self.start
            for _ in range(index-1):
                cur = tmp.getNext()
            tmp = Node(data)

문제 추천

- 두 개 뽑아서 더하기(Lv1)

- 모의고사(Lv1)

- 행렬의 곱셈(Lv2)

- 실패율(Lv1)

- 방문 길이(Lv2)

+)

- 배열의 평균값(Lv0)

- 배열 뒤집기(Lv0)

- n^2 배열 자르기(Lv2)

- 나누어 떨어지는 숫자 배열(Lv1)

---

문제 풀이

두 개 뽑아서 더하기

- O(N^2) + O((N^2)*log(N^2)) => O((N^2)*log(N^2))

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            answer.append(numbers[i] + numbers[j])
    answer = list(set(answer))
    return sorted(answer)

모의고사

- O(N) + O(1) => O(N)

def solution(answers):
    answer = []
    students = [
        [1, 2, 3, 4, 5],
        [2, 1, 2, 3, 2, 4, 2, 5],
        [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    ]
    scores = [0 for _ in range(3)]
    
    for i in range(len(answers)):
        if answers[i] == students[0][i%5]:
            scores[0] += 1
        if answers[i] == students[1][i%8]:
            scores[1] += 1
        if answers[i] == students[2][i%10]:
            scores[2] += 1
    
    # 다른 방식
    '''
    for i, answer in enumerate(answers):
        for j, student in enumerate(students):
            if answer == pattern[i%len(student)]:
                scores[j] += 1
    '''            
            
    max_score = max(scores)
    for i, score in enumerate(scores):
        if score == max_score:
            answer.append(i+1)
    return answer

행렬의 곱셈

- O(N^3)

def solution(arr1, arr2):
    answer = []
    r1, c1 = len(arr1), len(arr1[0])
    r2, c2 = len(arr2), len(arr2[0])
    
    result = [[0 for _ in range(c2)] for _ in range(r1)]
    for i in range(r1):
        for j in range(c2):
            for k in range(c1):
                result[i][j] += arr1[i][k] * arr2[k][j]
    return result

실패율

- O(N) + O(M) + O(N) + O(NlogN) => O(M+NlogN)

def solution(N, stages):
    answer = []
    ret = [0 for _ in range(N+2)]
    total = 0
    for user in stages:
        ret[user] += 1
        total += 1
    
    fails = {}
    for i in range(1, N+1):
        if ret[i] == 0:
            fails[i] = 0
        else:
            fails[i] = ret[i]/total
            total -= ret[i]
    answer = sorted(fails, key=lambda x: fails[x], reverse=True)
    return answer

방문 길이

- N은 dirs 길이

- O(N)

def is_valid(x, y):
    return (0 <= x) and (x < 11) and (0 <= y) and (y <= 11)
    
def solution(dirs):
    answer = 0
    return answer

배열의 평균값

def solution(numbers):
    answer = 0
    total = 0
    for i in range(len(numbers)):
        total += numbers[i]
    answer = total / len(numbers)
    return answer

배열 뒤집기

def solution(num_list):
    answer = [i for i in num_list]
    list_len = len(num_list)
    for i in range((list_len//2) + 1):
        answer[i], answer[list_len-i-1] = answer[list_len-i-1], answer[i]
    return answer

 n^2 배열 자르기

def solution(n, left, right):
    answer = []
    for i in range(left, right+1):
        answer.append(max(i//n, i%n)+1)

    return answer

나누어 떨어지는 숫자 배열

def solution(arr, divisor):
    answer = []
    for i in arr:
        if (i % divisor) == 0:
            answer.append(i)
    if len(answer):
        answer.sort()
    else:
        answer.append(-1)
    return answer