배열 관련 해결방안

SA Jung·2022년 9월 28일
1

Python 함수 정리

목록 보기
6/7

list에서 idx를 알아내거나 요소를 반환할때 시간복잡도는 O(n)이다.
deque 라이브러리를 만들어서 stack 및 queue로 활용한다면 시간복잡도를 O(1)으로 줄일 수 있어 코딩테스트를 푸는데 있어 시간 개선의 효과가 있고 효율성이 있는 문제의 효율성을 높일 수 있다.

1. deque

1-1. deque import하기

from collections import deque
stack = deque()
queue = deque()

1-2 deque로 요소 추가 및 반환하기

# 추가 append
a.append(1)
print (a)
# deque([1])

# 왼쪽 (0번 idx) 추가
a.appendleft(0)
print (a)
# deque([0, 1])

# 가장 오른쪽 요소 반환 및 제거
a = deque([1,2,3])
tmp = a.pop()
print (tmp)
# 3
print (a)
# deque([1,2])

# 0번 idx 요소 반환 및 제거
a= deque([1,2,3])
tmp = a.popleft()
print (tmp)
# 1
print (a)
# deque([2,3])

1-3 deque로 list 통째로 넣기

  • 리스트 요소를 하나하나 넣을 때 필요함.
  • 단 오름차순으로 들어감.
# extend - list 오른쪽 추가 (오름차순)
a.extend([1,2])
print(a)
# deque([1, 2])

# extendleft - list 왼쪽 추가 (오름차순)
a.extendleft([3,2,1] )
print(a)
# deque([1, 2, 3, 1, 2])

1-4 deque로 요소 회전시키기

  • deque 내 요소들을 기준으로 회전시킬 수 있다.
    (양수 = 시계방향, 음수 = 반시계방향)
# 양수방향
a=deque([1,2,3,4,5,6])
a.rotate(1)
print(a)
# deque([6, 1, 2, 3, 4, 5])
a.rotate(2)
print(a)
# deque([3, 4, 5, 6, 1, 2])
# 음수방향
a=deque([1,2,3,4,5,6])
a.rotate(-1)
print(a)
# deque([2, 3, 4, 5, 6, 1])
a.rotate(-3)
print(a)
# deque([5, 6, 1, 2, 3, 4])

2. list 각종 해결방안

2-1. list 내 중복값 제거하기

  • set명령어를 활용하면 중복된 값을 제거하고 unique하게 set 타입으로 반환해준다. 그리고 list로 다시 변환하여 사용하면 간편하다.
a= [1,1,2,1,3,4,5,2,3,4,5]
print (set(a))
# {1, 2, 3, 4, 5}

2-2. 2개의 List의 중복된 요소 찾기

# 리스트 중복된거 찾기 (리스트 중복검사는 set)
a = [2,3,4]
b = [4,5,6]

common = set(a).intersection(b)
print (common)
# {4}

2-3 리스트 컴프리헨션(List Comprehension) 사용하기

  • 기본 사용법은 [생성될 원소 for 반복될 값 조건]이다.

2-3.1 리스트 컴프리헨션 + if문 같이쓰기

# 1부터 10까지 중 짝수인 수만 tmp_list에 추가

# (1) list선언하고, for문 안에 if문 안에 append(추가) 사용
tmp_list = []
for i in range(1, 11):
    if i % 2 == 0:
        tmp_list.append(i)

# (2) 리스트 컴프리헨션으로 한줄로 list생성
tmp_list = [i for i in range(1,11) if i%2==0]

print (tmp_list)
 # [2, 4, 6, 8, 10]
  • 위의 (1)은 단순한 방법으로 원하는 값을 list에 추가하는 방식이고,
    아래 (2)의 방식은 리스트 컴프리헨션을 통해 판단 즉시 리스트에 추가할 수 있게해주는 방식이다.
    단, 한줄로 코드가 너무도 깔끔해진다!!

2-3.2 enumerate을 이용한 (idx, value) list 생성하기

# 단, 한 줄로 인덱스와 값을 [idx, value] 형태로 list 만들기.
tmp= [10,20,30,40,50]
queue = [[i, p] for i, p in enumerate(tmp)]
print (queue)
 # [[0, 10], [1, 20], [2, 30], [3, 40], [4, 50]]
  • enumerate 내장함수를 통해 단, 한줄로 코딩테스트를 하는데 유용한 리스트를 쉽게 만들 수 있다.
  • 리스트 컴프리헨션을 사용해서 코드를 깔끔하게 만들자!!

2-3.3 이중for문을 컴프리헨션으로 한줄로 구현하기

  • [생성될 원소 for 1번째 for문에서 반복될 값 조건 for 2번째 for문 안에서 반복될 값 조건]
# 이중 for문
tmp_list = [x * y for x in range(2, 5) for y in range(1, 10)]
print (tmp_list)
 # [2, 4, 6, 8, 10, 12, 14, 16, 18, 
 #	3, 6, 9, 12, 15, 18, 21, 24, 27, 
 #  4, 8, 12, 16, 20, 24, 28, 32, 36]
  • 이중 for문을 한 줄로 표현 가능하다.
visit =[[False for c in range(col)] for r in range(row)]
profile
Tomorrow will be better than yesterday :)

0개의 댓글