[Python] SWEA 5108 숫자 추가

SW Expert Academy SWEA 5108 숫자 추가 문제는 N개의 10억 이하 자연수로 이뤄진 수열의 임의의 위치에 M개의 숫자를 추가하고 난 수열에서 인덱스 L의 데이터를 출력하는 문제이다. Linked List 연결 리스트 자료구조에 관한 문제로 난이도는 D3이다.

 

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

 

SW Expert Academy 5108 숫자 추가 문제 정보

자료구조 분류

- Linked List 연결 리스트 (단순(Singly), 이중(Doubly))

난이도

- D3

 

숫자 추가 문제 요약

• N개의 10억 이하 자연수로 이뤄진 수열에 M개의 숫자를 지정된 위치에 추가하여 완성한다.  (5≤N≤1000, 1≤M≤1000)
• 완성된 수열에서 인덱스 L의 데이터를 출력한다. (6≤L≤N+M)
• 다음은 숫자를 추가하는 예이다.
  
  • 수열 1 2 3 4 5
  • 2 7 -> 2번 인덱스에 7을 추가하고 한 칸씩 뒤로 이동한다.
  • 수열 1 2 7 3 4 5

 

문제 풀이 과정

단순 연결 리스트를 구현하여 문제를 풀었습니다. 이중 연결 리스트를 구현해 풀어도 됩니다.

1. Node와 단순 연결 리스트를 정의한 클래스를 구현한다.
2. 단순 연결 리스트를 생성한다.
3. 수열의 원소들을 연결 리스트에 추가한다.
4. 특정 위치에 숫자를 추가한다.
5. 테스트 케이스 번호, 특정 인덱스의 원소를 출력한다.

 

코드 및 설명

• def is_empty - 연결 리스트가 비었는지 여부를 반환하는 함수
• def append - 맨 뒤에 원소를 삽입하는 함수
• def insert - 특정 위치에 원소를 삽입하는 함수
• def printItem - 특정 위치의 항목을 출력하는 함수
• def printList - 연결 리스트를 출력하는 함수 (문제와 무관)

class Node(object):
    def __init__(self, data, link=None):
        self.data = data
        self.link = link


class SinglyLinkedList(object):
    def __init__(self):
        self.head = None

    # 연결 리스트가 비어있는지
    def is_empty(self):
        return not bool(self.head)

    # 연결 리스트의 맨 뒤에 삽입
    def append(self, value):
    	# 비었으면 head의 링크를 새 노드의 주소로 바꾸기
        if self.is_empty():
            self.head = Node(value)
        # 링크가 None인(맨 뒤) 노드의 뒤에 삽입
        else:
            prev = self.head
            while prev.link != None:
                prev = prev.link
            newNode = Node(value)
            prev.link = newNode

    # 연결 리스트의 특정 위치에 삽입
    def insert(self, index, value):
        # 비었으면 head의 링크를 새 노드의 주소로 바꾸기
        if self.is_empty():
            self.head = Node(value)
        # 맨 앞에 넣기
        elif index == 0:
            self.head = Node(value, self.head)
        # 중간에 넣기
        else:
            # 이전 노드(넣을 위치의 앞 노드)의 링크 구하기
            prev = self.head
            for i in range(index - 1):
                prev = prev.link
            # 새 노드 생성하기
            newNode = Node(value)
            # 이전 노드의 링크를 새 노드의 주소로 바꾸기
            tmp = prev.link
            prev.link = newNode
            # 새 노드의 링크를 이전 노드의 링크로 바꾸기
            newNode.link = tmp

    # 특정 위치의 원소 출력하기
    def printItem(self, index):
        target = self.head
        for i in range(index):
            target = target.link
        return target.data

    # 리스트 출력하기 (문제와 무관)
    def printList(self):
        target = self.head
        while target:
            if target.link != None:
                print(target.data, '-> ', end='')
                target = target.link
            else:
                print(target.data)
                target = target.link


for tc in range(int(input())):
    sList = SinglyLinkedList()

    N, M, L = map(int, input().split())

    # 연결 리스트에 원소 추가하기
    sequence = list(input().split())
    for s in sequence:
        sList.append(s)

    # 특정 위치에 숫자 추가하기
    for _ in range(M):
        idx, num = map(int, input().split())
        sList.insert(idx, num)

    print("#{} {}".format(tc + 1, sList.printItem(L)))

---

 

그냥 단순 or 이중 연결 리스트를 구현해보라는 의도의 문제 같다. 다음엔 삭제 등 모든 기능을 하는 단일, 이중 연결 리스트를 구현해 봐야겠다.

 

SW Expert Academy SWEA 5108 숫자 추가 문제는 단순(Singly), 이중(Doubly) 연결 리스트 Linked List 활용 문제이며 파이썬으로 구현하였다. 난이도는 D3이다.