리스트, 연결 리스트

1️⃣ 개념

연결 리스트

특정 자료구조에 삽입, 삭제, 검색 행위를 반복적으로 해야 할 때 사용

• k번째 원소를 확인/변경하기 위해 O(k)가 필요함
• 임의의 위치에 원소를 추가/제거하기 위해 O(1)이 필요함
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만, 할당이 다소 쉬움

2️⃣ 코드

1. extend()
   

​

2. 원하는 값의 위치 찾기
   A.index(찾을 원소)
   -> 오른쪽부터 찾으려면 A.rindex(찾을 원소)

​

3. 특정 요소 개수 구하기 A.count(원소)

​

4. enumerate() - 인덱스와 원소 동시에 접근

for i, letter in enumerate(['A', 'B', 'C']):
	print(i, letter)

'''
0 A
1 B
2 C
'''

​

5. 리스트를 인자로 전달하기

   check([maps[i][j] for j in range(n)]) -> 가로줄
   check([maps[i][j] for i in range(n)]) -> 세로줄

​

6. 이차원 리스트 90도 회전

for i in range(n):
	for j in range(m):
    	result[j][n-i-1] = arr[i][j]

list(zip(*arr[::-1]))

​
리스트의 좌상단 위치가 (0, 0)이 아닌 경우 이동시킨 뒤 회전해야 한다

for i in range(sy, ey+1):
	for j in range(sx, ex+1):
		oy, ox = i-sy, j-sx   
		ry, rx = ox, m-oy-1
		result[ry+sy][rx+sx] = arr[i][j]

3️⃣ 문제 풀이

* 프로그래머스 표 편집 (Lv 3)

https://school.programmers.co.kr/learn/courses/30/lessons/81303
​

def solution(n, k, cmd):
	graph = {i:[i-1, i+1] for i in range(n)}
    graph[0] = [None, 1]
    graph[n-1] = [n-2, None]
    cur = k
    
    dele = []
    answer = ['O'] * n
    
    for c in cmd:
    	# 삭제
        if c == 'C':
        	answer[cur] = 'X'
            prev, next = graph[cur]
            dele.append([prev, cur, next])
            
            # 현재 선택된 행 구하기
            if next == None:   # 삭제된 행이 가장 마지막 행일 때 
            	cur = graph[cur][0]
            else:
            	cur = graph[cur][1]
            
            # 표 상태 변경하기 
            if prev == None:   # 삭제된 행이 가장 처음 행일 때
            	graph[next][0] = None
            elif next == None:    # 삭제된 행이 가장 마지막 행일 때 
            	graph[prev][1] = None
            else:
            	graph[prev][1] = next
                graph[next][0] = prev
        
        # 복구 
        elif c == 'Z':
        	prev, now, next = dele.pop()
            answer[now] = 'O'
            if prev == None:
            	graph[next][0] = now
            elif next == None:
            	graph[prev][1] = now
            else:
            	graph[next][0] = now
                graph[prev][1] = now
        
        # 커서 이동 
        else:
        	c1, c2 = c.split(' ')
            c2 = int(c2)
            if c1 == 'D':
            	for _ in range(c2):
                	cur = graph[cur][1]
            else:
            	for _ in range(c2):
                	cur = graph[cur][0]

	return ''.join(answer)