Algorithm/코딩테스트 (Python)

[SWEA 5108][파이썬 S/W 문제해결 기본]. 7일차 - 숫자 추가

싱브이 2023. 11. 18. 20:07
728x90
반응형

문제

N개의 10억 이하 자연수로 이뤄진 수열이 주어진다.
이 수열은 완성된 것이 아니라 M개의 숫자를 지정된 위치에 추가하면 완성된다고 한다.
완성된 수열에서 인덱스 L의 데이터를 출력하는 프로그램을 작성하시오.
다음은 숫자를 추가하는 예이다.

인덱스 0 1 2 3 4
수열 1 2 3 4 5

 

2 7 -> 2번 인덱스에 7을 추가하고 한 칸 씩 뒤로 이동한다.

인덱스 0 1 2 3 4 5
수열 1 2 7 3 4 5


4 8 -> 4번 인덱스에 8을 추가하고 한 칸 씩 뒤로 이동한다.

인덱스 0 1 2 3 4 5 6
수열 1 2 7 3 8 4 5


[입력]
첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 첫 줄에 수열의 길이 N, 추가 횟수 M, 출력할 인덱스 번호 L이 주어지고, 다음 줄에 수열이 주어진다.
그 다음 M개의 줄에 걸쳐 추가할 인덱스와 숫자 정보가 주어진다. 5<=N<=1000, 1<=M<=1000, 6<=L<=N+M

[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
 

 

 

 

내 생각

간단하게 풀 수 있으나, LinkedList 이용해보라고 낸 문제같아서 LinkedList로도 구현하였다. 어,, 쉽지 않다.

1번 코드는 너무 간단해서 설명할 것도 없다. 그냥 해당 index자리에 값을 넣으면 끝!

2번 코드의 함수는 이러하다. 

1. def append(self, data) : 주어진 데이터를 새로운 노드로 만들어서 연결 리스트 끝에 추가하는 함수이다.

2. def insert(self, index, data) : 주어진 데이터를 가진 새로운 노드를 지정된 인덱스에 삽입하는 함수이다.

3. def get_index(self, index) : 연결 리스트에서 지정된 인덱스의 데이터를 가져오는 함수이다. 

자세한 설명은 주석으로 달았는데, 뭔가 말로 적으려니 어렵다.

설명을 더 잘 할 수 있을 때까지 연습해봐야겠다 !

 

 

 

 

내 코드

1.

T = int(input())
for test_case in range(1, T + 1):
    N, M, L = map(int, input().split())
    arr = list(map(int, input().split()))
    for _ in range(M):
        idx, num = map(int, input().split())
        arr.insert(idx,num)
    print(f'#{test_case} {arr[L]}')

 

2. Linked List

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data): # 연결 리스트의 맨 뒤에 삽입
        new_node = Node(data)
        if not self.head: # head가 비었으면 새 노드의 head, tail로 주소 바꾸기
            self.head = new_node
            self.tail = new_node
        else: #head가 있다면 맨 뒤 노드의 뒤에 삽입
            self.tail.next = new_node
            self.tail = new_node

    def insert(self, index, data): #연결 리스트의 특정 위치에 삽입
        new_node = Node(data) #새로운 노드를 생성하고 주어진 데이터 설정
        if index == 0: # 맨 앞에 넣음
            new_node.next = self.head #새 노드의 다음 링크를 현재 head로 설정
            self.head = new_node #head를 새 노드로 업데이트
        else: #중간에 넣음
            current = self.head #넣을 위치의 앞 노드의 링크를 구함
            for _ in range(index - 1):
                if current.next:
                    current = current.next
                else:
                    break
            new_node.next = current.next # 새 노드의 다음 링크를 현재 위치의 다음 노드로 설정
            current.next = new_node #현재 위치의 다음 노드를 새 노드로 업데이트

    def get_index(self, index): #특정 위치의 원소 index 가져오는 함수
        current = self.head
        for _ in range(index + 1):
            if current and current.next:  
                current = current.next
            else:
                break
        if current: # 현재 위치가 있다면
            return current.data # 현재 위치의 데이터 반환
        else:
            return None


T = int(input())
for test_case in range(1, T + 1):
    N, M, L = map(int, input().split())
    sequence = LinkedList()

    for num in input().split():
        sequence.append(int(num)) #연결리스트 채우기

    for _ in range(M):
        idx, num = map(int, input().split())
        sequence.insert(idx, num) #삽입

    result = sequence.get_index(L - 1)
    print(f'#{test_case} {result}')
728x90
반응형