[SWEA 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

 

 

 

 

내 생각

쉽게 도전했으나, ChatGPT의 도움을 받고야 말았다. 뭐 그래도 얻은게 있으니 다행 !

문제풀이흐름은 이러하다 !

1. 합칠 수열(수열2)의 첫 숫자보다 큰 숫자를 앞 수열(수열1)에서 찾아 그 앞에 끼워넣는다.
2. 큰 숫자가 없는 경우 맨 뒤에 붙인다.
3. 마지막 수열까지 합치고 나면, 그 결과 수열의 맨 뒤부터 10개의 숫자를 역순으로 출력

 

 

 

 

코드

1.

for test_case in range(1, int(input()) + 1):
    N, M = map(int, input().split())
    array = [float('inf')] # 양의 무한대 inf (최대값 구할 때 자주 활용)
    cnt = 0 # 수열 더해질때마다 추가될 cnt
    
    for _ in range(M): # 각 수열에 대해 반복
        a = list(map(int, input().split())) # 개별 수열 a
        # 수열을 합치기 위해 적절한 위치에 삽입
        for i in range(N*cnt + 1):
            if a[0] < array[i]: # 수열 2의 첫 숫자보다 큰 숫자를 찾으면
                array[i:i] = a # 해당 위치에 수열 2를 끼워 넣음
                break 
        cnt += 1 # cnt를 증가시켜 다음 수열과 비교할 위치를 설정
    print(f'#{test_case}', end=' ')
    print(*array[-11:-1][::-1]) # 뒤에서부터 역순으로 출력

 

2.LinkedList

# Node 클래스 정의: 링크드 리스트의 노드를 나타내는 클래스
class Node:
    # 초기화 메소드
    def __init__(self, data):
        self.data = data
        self.link = None

# LinkedList 클래스 정의: 링크드 리스트를 나타내는 클래스
class LinkedList:
    # 초기화 메소드
    def __init__(self):
        new_node = Node('head')  # head 노드 생성
        self.head = new_node
        self.tail = new_node
        self.before = None
        self.current = None
        self.num_of_data = 0

    # 새로운 데이터를 리스트에 추가하는 메소드
    def append(self, data):
        new_node = Node(data)  # 새 노드 생성
        self.tail.link = new_node  # tail과 새 노드 연결
        self.tail = new_node  # tail 갱신
        self.num_of_data += 1

    # 리스트의 첫 번째 데이터를 반환하는 메소드
    def first(self):
        if self.num_of_data == 0:  # 빈 리스트이면 None 리턴
            return None
        self.before = self.head
        self.current = self.head.link
        return self.current.data

    # 리스트의 다음 데이터를 반환하는 메소드
    def next(self):
        self.before = self.current
        self.current = self.current.link
        if self.current is None:
            return None
        return self.current.data

    # 다른 리스트를 현재 리스트에 삽입하는 메소드
    def insertlist(self, new_list):
        insert_num = new_list.first()
        num = self.first()
        # 수열 2의 첫 숫자보다 큰 숫자를 수열 1에서 찾으면
        for _ in range(self.num_of_data):
            if num > insert_num:
                self.before.link = new_list.head.link  # 수열 2 삽입
                new_list.tail.link = self.current
                self.num_of_data += new_list.num_of_data
                break
            num = self.next()
        else:  # 큰 숫자가 없는 경우 맨 뒤에 붙임
            self.tail.link = new_list.head.link
            self.num_of_data += new_list.num_of_data

    # 리스트의 뒤에서부터 역순으로 10개의 데이터를 반환하는 메소드
    def my_result(self):
        lst = []
        num = self.first()
        for _ in range(self.num_of_data):
            lst.append(num)
            num = self.next()
        return ' '.join(map(str, lst[-1:-11:-1]))

# main 함수
T = int(input())
for test_case in range(1, T + 1):
    N, M = map(int, input().split())

    # 빈 LinkedList 생성
    Seq1 = LinkedList()

    # LinkedList 입력받기
    for i in map(int, input().split()):
        Seq1.append(i)

    for _ in range(M - 1):
        # 빈 LinkedList 생성
        Seq2 = LinkedList()
        # LinkedList 입력받기
        for j in map(int, input().split()):
            Seq2.append(j)
        # Seq1에 Seq2 삽입
        Seq1.insertlist(Seq2)
    
    print('#{} {}'.format(test_case, Seq1.my_result()))

 

 

 

 

** 언패킹(unpacking), ' * '

   : 리스트나 튜플과 같은 iterable 데이터를 개별 요소로 풀어서 전달한다.
→ ' , '로 구분되지 않고 개별적으로 띄어쓰기 출력된다.