[SWEA] 5110. [파이썬 S/W 문제해결 기본] 7일차 - 수열 합치기 D3 파이썬

문제출처 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ1r6qfkDFAWg

5110. [파이썬 S/W 문제해결 기본] 7일차 - 수열 합치기

여러 개의 수열을 정해진 규칙에 따라 합치려고 한다. 다음은 3개의 수열이 주어진 경우의 예이다.

수열 1

2

3

4

5

수열 2

4

8

7

6

수열 3

9

10

15

16

수열 4

1

2

6

5

수열 2의 첫 숫자 보다 큰 수자를 수열 1에서 찾아 그 앞에 수열 2를 끼워 넣는다.
 

2

3

4

4

8

7

6

5

합쳐진 수열에 대해, 수열 3의 첫 숫자보다 큰 숫자를 찾아 그 앞에 수열 3을 끼워 넣는다. 큰 숫자가 없는 경우 맨 뒤에 붙인다.
 

2

3

4

4

8

7

6

5

9

10

15

16

마지막 수열까지 합치고 나면, 맨 뒤의 숫자부터 역순으로 10개를 출력한다.
 

1

2

6

5

2

3

4

4

8

7

6

5

9

10

15

16

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 수열의 길이 N, 수열의 개수 M, 이후 M개의 줄에 걸쳐 1000이하의 자연수로 구성된 수열이 주어진다. 4<=N<=1000, 1<=M<=1000

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 완성된 수열의 맨 뒤부터 10개의 숫자를 역순으로 출력한다.

---

[풀이 코드] - 파이썬

 

# 5110. [파이썬 S/W 문제해결 기본] 7일차 - 수열 합치기
 
 
class Node:
    def __init__(self, d=0, p=None, n=None):
        self.data = d
        self.prev = p
        self.next = n
 
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
 
def addList(lst, arr):
    first = last = Node(arr[0])
    for val in arr[1:]:
        new = Node(val, last)
        last.next = new
        last = new
 
    if lst.head is None:
        lst.head, lst.tail = first, last
    else:
        cur = lst.head
        while cur is not None:
            if cur.data > arr[0]: break
            cur = cur.next
        if cur is None: # 뒤에 # 순서주의
            first.prev = lst.tail
            lst.tail.next = first
            lst.tail = last
        elif cur.prev is None: # 앞에 
            last.next = lst.head
            lst.head.prev = last
            lst.head = first
        else: # 중간에 추가
            prev = cur.prev
            first.prev = prev
            last.next = cur
            prev.next = first
            cur.prev = last
    lst.size += len(arr)
 
def printList(lst):  # 연결리스트 출력
    if lst.head is None:
        return
    cur = lst.tail
    cnt = 10
    while cnt: # 역방향
        print(cur.data, end=' ')
        cur = cur.prev
        cnt -= 1
    print()
 
# import sys
# sys.stdin = open('input.txt')    
 
for tc in range(1,int(input())+1):
    n,m=map(int,input().split())
    arr = list(list(map(int,input().split())) for _ in range(m)) # 2차원배열로 받기
    mylist = LinkedList()
    for i in range(m):
        addList(mylist, arr[i])
    print(f'#{tc}', end=' ')
    printList(mylist)