[Coding Test][Python] List 정리 및 Linked List 구현

1. Python Method 사용법

append(object=)

li = [1,2,3]
li.append(1)
li

 

[1, 2, 3, 1]

 

clear()

li = [1,2,3]
li.clear()
li

 

[]

 

copy()

li = [1,2,3]
# Deepcopy
li2 = li.copy()
print(li2)
li[1] = 1
print(li2)

[1, 2, 3, 1]

 

count(value=)

value가 없어도 Error가 나지 않는다

li = [1,2,2,3]
print(li.count(2))
print(li.count(4))

 

2
0

 

extend(iterable=)

기존 List에 다른 Iterable 한 객체의 원소를 이어붙인다

li = [1,2,3]    
li2 = [1,2,3]
# 원본 리스트를 수정하고 새로운 list를 반환하지 않는다
li.extend([4,5,6])
li2.append([4,5,6])
print(li)
print(li2)

 

[1, 2, 3, 4, 5, 6]
[1, 2, 3, [4, 5, 6]]

 

index(value=,start=,stop)

li = [1,2,3]
li2 = [1,2,3,4,5,6,7]
print(li.index(2))
# 존재하지 않으면 Error
print(li2.index(1, 3, 6))
print(li.index(4))

1
---------------------------------------------------------------------------
ValueError
Traceback (most recent call last)
Cell In[28], line 4
        2 li2 = [1,2,3,4,5,6,7] 
        3 print(li.index(2))
----> 4 print(li2.index(1, 3, 6))
        5 print(li.index(4))
ValueError: 1 is not in list

 

insert(index=, object=)

li = [1,2,3]
# insert(index=, object=)
li.insert(0, 0)
li.insert(1, 5)
li

[0, 5, 1, 2, 3]

 

pop(index=-1)

li = [1,2,3,4,5]
li.pop(0)
print(li)
# default index는 -1
li.pop()
print(li)

[2, 3, 4, 5]
[2, 3, 4]

 

remove(value=)

value가 존재하지 않으면 Error

li = [1,2,3,4,5]
li.remove(1)
print(li)
li.remove(6)
print(li)

[2, 3, 4, 5]
---------------------------------------------------------------------------
ValueError
Traceback (most recent call last)
Cell In[23], line 4
        2 li.remove(1)
        3 print(li)
----> 4 li.remove(6)
        5 print(li)
ValueError: list.remove(x): x not in list

 

reverse()

li = [1,2,3,4,5]
# inplace
li.reverse()
li

[5, 4, 3, 2, 1]

 

sort(key=,reverse=)

li = [3,4,5,2,7,6]
li.sort()
print(li)

li = [3,4,5,2,7,6]
li.sort(reverse=True)
print(li)

li = [[1, 2],
      [1, 3],
      [4, 5],
      [3, 1],
      [2, 4],
      [2, 5]]
# 첫번째 원소는 오름차순, 두번째 원소는 내림차순
li.sort(key=lambda x:(x[0], -x[1]))
print(li)

[2, 3, 4, 5, 6, 7]
[7, 6, 5, 4, 3, 2]
[[1, 3], [1, 2], [2, 5], [2, 4], [3, 1], [4, 5]]

2. List를 활용한 Two Sum 예제

문제

정수가 저장된 배열 nums가 주어졌을 때, nums의 원소 중 두 숫자를 더해서 Target이 될 수 있으면 True, 불가능하면 False를 반환하세요.
제약조건
2 <= nums.lengths <= 10^4
-10^9 <= num[i] <= 10^9 -
10^9 <= target <= 10^9 

input : 4 1 9 7 5 3 16
target : 14
output : True

input : 2 1 5 7
target : 4
output : False

풀이

Left, Right를 가리키는 변수 l, r을 통해 한칸씩 옮겨가며 찾기(정렬이 되어있어야한다)

nums = list(map(int, input().split(" ")))
target = int(input())

def twoSum_two_pointer(nums, target):
    nums.sort()
    l, r = 0, len(nums)-1
    while l<r:
        if nums[l] + nums[r] == target:
            return True
        elif nums[l] + nums[r] > target:
            r -= 1
        elif nums[l] + nums[r] < target:
            l += 1

    return False
    
twoSum_two_pointer(nums, tarrget)

3. Linked List 개념

1) Linked List 란?

Linked List란 데이터를 저장하는 Node들이 순차적으로 연결된 선형 자료구조이다.

각 Node는 데이터와 함께 다음 노드에 대한 Pointer를 포함하고 있다.

Array와 달리 메모리에 연속적으로 저장되지 않으며 동적으로 크기를 조정할 수 있다.

2) Linked List 구조

• NODE : Linked List의 기본 단위
  
  • Data : 저장할 데이터
  • Next : 다음 Node의 주소를 가리키는 Pointer
• Head : Linked List의 시작 Node을 가리키는 Pointer
• Tail(Optional) : Linked list의 마지막 Node를 가리키는 Pointer

3) Linked List 종류

• Singly Linked List : 각 Node는 다음 Node만을 가리킨다.
  • Node1 -> Node2 -> Node3 -> None
• Doubly Linked List : 각 Node는 이전 Node와 다음 Node를 모두 가리킨다.
  • None <- Node1 <-> Node2 <-> Node3 -> None
• Circular Linked List : 마지막 Node가 첫 번째 Node를 가리켜 순환 형태를 만든다.
  • Node1 -> Node2 -> Node3 -> Node1

3. Singly Linked List 구현

1) Node 정의

class Node:
    def __init__(self, value=0, next=None):
        self.value = value
        # 다음 Node를 가리킬 Pointer
        self.next = next

2) Linked List 정의

다양한 Method를 필요에 맞게 정의하여 사용할 수 있다.

class LinkedList(object):
	def __init__(self):
    	self.head = None
        self.tail = None
    
	def insert_front(self, value):
    	new_node = Node(value)
        if self.head == None:
        	self.head = new_node
            self.tail = new_node
        else:
        	new_node.next = self.head
            self.head = new_node
    
    def insert_back(self, value):
    	new_node = Node(value)
        if self.head == Node:
        	self.head = new_node
            self.tail = new_node
        else:
        	self.tail.next = new_node
            self.tail = new_node
            
    def insert_at(self, idx, value):
    	new_node = Node(value)
        if self.head == None
        	self.head = new_node
            self.tail = new_node
        else:
        	curr = self.head
            for _ in range(idx):
            	curr = curr.next
            next = curr.next
            curr.next = new_node
            new_node.next = next
            
    def remove_front(self):
    	if self head is not None:
        	self.head = self.head.next
        
    def remove_back(self):
    	if self.head is not None:
        	curr = self.head
            while curr.next != self. tail:
            	curr = curr.next
            self.tail = curr
            curr.next = None
            
    def remove_at(self, idx):
    	if self.head is not None:
        	curr = self.head
            before = None
            for _ in range(idx):
            	before = curr
            	curr = curr.next
            before.next = curr.next
            
     def get(self, idx):
     	if self.head is not None:
        	curr = self.head
            for _ in range(idx):
            	curr = curr.next
            return curr.value
            
    def show(self):
    	if self.head is not None:
        	curr = self.head
            while curr.next:
            	print(curr.value, end=' ')
                curr = curr.next
            print(curr.value)

3) Linked List 예제

linkedlist = LinkedList()

linkedlist.insert_back(1)
linkedlist.insert_back(2)
linkedlist.insert_front(0)
linkedlist.insert_back(3)
linkedlist.insert_back(4)
linkedlist.insert_back(5)
linkedlist.show()

0 1 2 3 4 5

 

linkedlist.remove_front()
linkedlist.show()
print()
linkedlist.remove_back()
linkedlist.show()
print()
linkedlist.remove_at(1)
linkedlist.show()

1 2 3 4 5
1 2 3 4
1 3 4