수열 편집 Python(SW Expert Academy)

난이도 : D4

문제번호 : 5122

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

N개의 10억 이하 자연수로 이뤄진 수열이 주어진다. 이 수열은 완성된 것이 아니라 M번의 편집을 거쳐 완성된다고 한다. 완성된 수열에서 인덱스 L의 데이터를 출력하는 프로그램을 작성하시오. 다음은 미완성 수열과 편집의 예이다. 만약 편집이 끝난 후 L이 존재하지 않으면 -1을 출력한다.

 

입력

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

출력

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

예시

입력	출력
3 5 3 4 1 2 3 4 5 I 2 7 D 4 C 3 8 5 5 2 15171 7509 20764 13445 10239 C 3 18707 C 1 20250 D 2 D 2 C 0 7158 10 10 8 27454 29662 2491 1819 10118 15441 7357 23618 972 398 D 7 D 1 D 6 I 3 2906 C 1 27121 D 3 D 2 D 1 D 2 C 2 20794	#1 5 #2 10239 #3 -1

---

2. 문제풀이

연결리스트만 구현할 수 있다면 어려운 문제가 아니었다. 연결리스트의 개념과 구현방법이 궁금하면 자료구조를 공부해자.   들어오는 커맨드에따라 조건분기를 하고 삽입, 삭제, 수정을 하면 된다. LIST를 이용해 간단하게 구현도 가능하다.

---

3. 소스코드

 

#D4 5122 수열 편집
 
#연결리스트에 사용될 노드
class Node:
    def __init__(self, item):
        self.back_link = None
        self.item = item
        self.next_link = None
 
#연결리스트 클래스
class Linked_List:
    #생성시 첫시작부분과 마지막부분, 길이를 가진다.
    def __init__(self):
        self.head = None
        self.length = 0
        self.rear = None
    
    #특정 인덱스의 값을 바꾼다면
    def change(self, index, item):
        back_index = self.length - index
        #앞쪽부터 접근이 가깝다면
        if back_index > index:
            #헤드부터 접근한다.
            temp = self.head
            for i in range(index):
                temp = temp.next_link
        #뒤부터 접근이 가깝다면
        else:
            #뒤에서부터 접근한다.
            temp = self.rear
            for i in range(back_index-1):
                temp = temp.back_link
        #원소의 값 바꾸기
        temp.item = item
 
    #뒤에 추가하는 함수
    def append(self, item):
        node = Node(item)
        #노드가 하나라도 있다면
        if self.length:
            #생성한 노드 연결한다.
            self.rear.next_link = node
            node.back_link = self.rear
        #노드가 하나도 없다면 헤드가 노드를 가리키도록 한다.
        else:
            self.head = node
        #길이 하나 늘려주고
        self.length += 1
        #추가한 값을 꼬리부분으로 바꾸기
        self.rear = node
    
    #노드가 있다면 제일 앞부분의 데이터를 리턴한다.
    def getFirst(self):
        if not self.length:
            return None
        return self.head.item
    #노드가 있다면 제일 뒷부분의 데이터를 리턴한다.
    def getLast(self):
        if not self.length:
            return None
        return self.rear.item
 
    #인덱스를 이용한 데이터 얻기
    def get(self, index):
        #길이가 없다면 None을 리턴
        if not self.length:
            return None
        #접근하는 인덱스가 길이를 넘어가면 제일 마지막 값 리턴
        if index >= self.length:
            return self.rear.item
        #접근한 인덱스를 길이에서 빼본다.
        back_index = self.length - index
        #앞부분과 뒷부분 어디에서 접근하는게 빠른지 판단한다.
        #앞부분에서 빠르다면
        if back_index > index:
            temp = self.head
            for i in range(index):
                temp = temp.next_link
        #뒷부분에서 빠르다면
        else:
            temp = self.rear
            for i in range(back_index-1):
                temp = temp.back_link
        #결과값 리턴
        return temp.item
 
    #값을 추가하는 함수
    def insert(self, index, item):
        node = Node(item)
        #노드가 없다면
        if not self.length:
            self.head = node
            self.rear = node
        #인덱스가 길이를 넘어가면 마지막에 추가
        elif self.length <=index:
            self.rear.next_link = node
            node.back_link = self.rear
            self.rear = node
        #넣는 인덱스가 0번이라면
        elif not index:
            #제일 앞부분에 데이터를 넣고 주소위치를 바꿔준다.
            self.head.back_link = node
            node.next_link = self.head
            self.head = node
        #위의 상황이 아니라면
        else:
            #앞과 뒤쪽중 어디서 접근하는게 빠른지 찾는다.
            back_index = self.length - index
            #앞부분의 접근이 빠르다면
            if back_index > index:
                temp = self.head
                for i in range(index):
                    temp = temp.next_link
            #뒷부분의 접근이 빠르다면
            else:
                temp = self.rear
                for i in range(back_index-1):
                    temp = temp.back_link
            #찾은 값을 기준으로 노드를 추가하고 주소를 변경
            temp.back_link.next_link = node
            node.back_link = temp.back_link
            node.next_link = temp
            temp.back_link = node
        self.length += 1
 
    #원소를 꺼내며 가지고 있던 값 리턴
    def pop(self,index=-1):
        value = None
        #길이가 없다면 반환할 값이 없다.
        if not self.length:
            value = None
        #길이가 1이라면 원소가 하나이므로 head와 rear를 None으로 바꿔준다.
        elif self.length == 1:
            value = self.head.item
            self.head = None
            self.rear = None
        #0번 인덱스를 꺼낸다면 헤드를 1번인덱스에 연결해줘야 한다.
        elif not index :
            self.head = self.head.next_link
        #인덱스가 음수이거나 길이보다 크다면 제일 마지막 값을 리턴
        elif index < 0 or index >= self.length-1:
            value = self.rear.item
            self.rear = self.rear.back_link
            self.rear.next_link = None
        else :
            #앞쪽과 뒤쪽중 가까운곳 부터 찾아서 리턴
            back_index = self.length - index
            if back_index > index:
                temp = self.head
                for i in range(index):
                    temp = temp.next_link
            else:
                temp = self.rear
                for i in range(back_index-1):
                    temp = temp.back_link
            #주소 변경작업
            value = temp.item
            back_node = temp.back_link
            next_node = temp.next_link
            back_node.next_link = next_node
            next_node.back_link = back_node
        self.length -=1
        return value
 
 
for t in range(1, int(input()) + 1):
    #N 수열의 길이, M 추가횟수, 출력인덱스 L
    N, M, L = map(int, input().split())
    temp = input().split()
    linked_list = Linked_List()
    for i in temp:
        linked_list.append(i)
    #명령횟수만큼 반복
    for _ in range(M):
        command = input().split()
        #추가할때
        if command[0] == 'I': linked_list.insert(int(command[1]), command[2])
        #삭제할때
        elif command[0] == 'D': linked_list.pop(int(command[1]))
        #변경할때
        else: linked_list.change(int(command[1]), command[2])
    #인덱스를 벗어났을때 결과
    result = -1
    #인덱스를 벗어나지 않으면 값바꿔주기
    if linked_list.length > L: result = linked_list.get(L)
    #결과값 출력하기
    print('#{} {}'.format(t, result))
 
'''
for t in range(1, int(input()) + 1):
    #N 수열의 길이, M 추가횟수, 출력인덱스 L
    N, M, L = map(int, input().split())
    linked_list = input().split()
    #명령횟수만큼 반복
    for _ in range(M):
        command = input().split()
        #추가할때
        if command[0] == 'I': linked_list.insert(int(command[1]), command[2])
        #삭제할때
        elif command[0] == 'D': linked_list.pop(int(command[1]))
        #변경할때
        else: linked_list[int(command[1])] = command[2]
    #인덱스를 벗어났을때 결과
    result = -1
    #인덱스를 벗어나지 않으면 값바꿔주기
    if len(linked_list) > L: result = linked_list[L]
    #결과값 출력하기
    print('#{} {}'.format(t, result))
'''