[SW Intermediate] Linked List - 활용

Linked List - 활용

---

스택(Stack)

[스택의 원소: 리스트의 노드]

- 스택 내 순서는 연결리스트의 링크를 통해 연결됨

- push: 연결 리스트의 맨 앞에 노드 삽입

- pop: 연결 리스트의 맨 앞 노드 반환/삭제

 

[변수 top]

- 연결 리스트의 맨 앞 노드를 가리킴

- 초기상태: top = None

 

---

우선순위 큐(Priority Queue)

1) 우선순위 큐의 구현

- 연결리스트 이용한 우선순위 큐

2) 우선순위 큐의 기본 연산

- 삽입: enQueue

- 삭제: deQueue

 

[연결리스트 이용한 우선순위 큐 구현]

- 연결리스트를 이용하여 자료 저장

- 원소를 삽입하는 과정에서 리스트 내 노드의 원소들과 비교하여 적절한 위치에 노드를 삽입하는 구조

- 리스트의 가장 앞쪽에 최고 우선순위가 위치하게 됨

 

[배열 대비 장점]

- 메모의 삽입/삭제 연산 이후 원소의 재배치가 필요 없음

- 메모리의 효율적인 사용이 가능

 

---

문1: 숫자 추가

T = int(input())
for test_case in range(1, T + 1):
    n, m, l = map(int, input().split())
    num_list = list(map(int, input().split()))
    for _ in range(m):
        index, num = map(int, input().split())
        num_list.insert(index, num)

    print(f'#{test_case} {num_list[l]}')

 

문2: 수열 합치기

T = int(input())
for test_case in range(1, T + 1):
    n, m = map(int, input().split())
    # m개의 수열
    num_list = [list(map(int,input().split())) for _ in range(m)]
    new_list = num_list[0]

    for i in range(1, m):
        for index, data in enumerate(new_list):
            if data > num_list[i][0]:
                # 특정 위치에 삽입 시, 리스트의 슬라이싱을 이용할 수 있다.
                new_list[index:index] = num_list[i]
                break
            if index == len(new_list)-1:
                new_list = new_list + num_list[i]
                break
    res = []
    for item in new_list[::-1]:
        if len(res) == 10:
            break
        res.append(str(item))

    print(f'#{test_case} {" ".join(res)}')

 

문3: 암호

'''
조건을 다 찾아서 구현했지만,
문제에 대한 이해가 부족해서 잘못구현하느라
시간을 많이 썼던 문제이다.

Linked list 를 이용해서 구현하는 문제 파트인데..
Linked List 는 어떻게 활용해서 풀어햐 할까..?

'''

T = int(input())
for test_case in range(1, T + 1):
    n,m,k = map(int, input().split())
    num_list = list(map(int, input().split()))
    st = 0

    for _ in range(k):
        st = st + m
        if st > len(num_list):
            st -= len(num_list)
        if not st:
            num_list.insert(0, num_list[-1]+num_list[0])
        elif st == len(num_list):
            num_list.append(num_list[-1] + num_list[0])
        else:
            num_list.insert(st, num_list[st-1] + num_list[st])

    res = []
    for item in num_list[::-1]:
        if len(res)==10:
            break
        res.append(str(item))
    print(f'#{test_case} {" ".join(res)}')

 

문4: 수열 편집

T = int(input())
for test_case in range(1, T + 1):
    # n: 수열의 길이, m: 추가 횟수, l: 출력할 인덱스 번호
    n,m,l = map(int, input().split())
    num_list = list(map(int,input().split()))

    # I : Insert
    # D : Delete
    # C : replace

    for _ in range(m):
        # connad, index, num
        command = list(input().split())
        if 'I' in command:
            num_list.insert(int(command[1]), command[2])
            continue
        if 'D' in command:
            del num_list[int(command[1])]
            continue
        if 'C' in command:
            num_list[int(command[1])] = command[2]
            continue
    if l < len(num_list):
        print(f'#{test_case} {int(num_list[l])}')
    else:
        print(f'#{test_case} {-1}')