2. Queue - 기능개발, FloodFill, 전염병, 문자열 압축

2. Queue - 기능개발, FloodFill, 전염병, 문자열 압축

Queue

유형

1) 순차적 탐색

2) BFS

3) 앞에 것을 꺼낸다 >>> 무조건 deque 쓴다 큐의 역할

1) 순차적으로 탐색 >>> 시간단축을 위해 deque 사용 (O(n) >> O(1))

2) BFS에서 다음에 방문할 노드를 순차적으로 방문하기 위해 사용 deque 구현 : from collections import deque BFS 구현 방문한 노드 : visited = [[0] * m for _ in range(n)] # [[0] * m] * n은 에러다 방향 : directions = [[-1,0], [1,0], [0, -1], [0, 1]] 탐색 이중포문 if문 : x, y + 이동한 좌표가 범위를 벗어나지 않고, 어떠한 조건을 만족할 때 방문표시 + 큐에 지금 방문했던 노드를 추가하여, 다음에 큐를 사용하여 방문

기능개발

ceil 함수 사용 작업일과 배포일 따로 구현한 과정을 합치기 단순반복인 경우 while, deque 안쓰고 for loop 사용

from math import ceil def solution(progresses, speeds): max_day = ceil((100 - progresses[0]) / speeds[0]) deployment = 0 answer = [] ''' while dq: day = dq.popleft() # 어차피 순회하는 것이므로, while 쓰지말고 for loop으로 처리 ''' for p, g in zip(progresses, speeds): day = ceil((100 - p) / g) #---------------------------------------- ''' if max_day >= day: deployment += 1 else: max_day = day answer.append(deployment) deployment = 1 ''' if max_day < day: answer.append(deployment) max_day = day deployment = 0 deployment += 1 #---------------------------------------- answer.append(deployment) # 마지막으로 안 넣은 배포일을 추가 return answer

# 리스트의 특성을 이용한 풀이 from math import ceil def solution(progresses, speeds): answer = [[ceil((100 - progresses[0]) / speeds[0]), 0]] # answer = [[진도율, 배포되는 기능 수]] for progress, speed in zip(progresses, speeds): # 첫 번째 기능 부터 비교 duration = ceil((100 - progress) / speed) if answer[-1][0] < duration: # 배열의 끝에 있는 진도율과 비교 answer.append([duration, 0]) # 새로 들어오는 진도율이 duration이 크면, 이전 것들은 배포하고, 새로 배포 기능 수 계산 answer[-1][1] += 1 return [count for _, count in answer]

FloodFill

BFS [[0] * m] * n 에러 directions : [ ]안에, 튜플 사용 float('inf') : 방문 표시 들여쓰기 줄이기 : 예외적인 상황에만 if문 사용, 일반적인 부분은 들여쓰기를 당겨서 사용 이동좌표 : 자주 사용하므로 변수로 할당해서 사용

from collections import deque def solution(n, m, image): # 1. 방문한 노드, 방향 리스트 설정 answer = 0 visited = [[0] * m for _ in range(n)] # [[0]*m]*n 에러 directions = [(0, 1), (0, -1), (-1, 0), (1, 0)] # []안에, 튜플 사용 # 2. 탐색 (for) for i in range(n): for j in range(m): #--------------------------------- # 방문한 곳을 찾아, 이것은 넘어가고, if문 나와서 방문하지 않은 노드에 대해 처리한다. # 들여쓰기를 줄일 수 있다 if image[i][j] == float('inf'): continue target_color = image[i][j] queue = deque([(i, j)]) ''' # 방문하지 않은 노드만 탐색 if visited[i][j] == 0: # 방문표시 & 정답 += 1 visited[i][j] = 1 answer += 1 queue = deque([[i,j]]) # 3. 인접노드 탐색 while queue: .... ''' while queue: x, y = queue.popleft() for dx, dy in directions: # 이동 좌표 : 자주 사용하므로 변수 할당 px = x + dx py = y + dy if px >= n or px < 0 or py >= m or py < 0: continue if image[px][py] == target_color: image[px][py] = float('inf') queue.append((px, py)) answer += 1 return answer

전염병

shallow copy 주의 : mutable한 객체간 대입은 값이 할당 되는 것이 아니라, 같은 메모리 주소를 바라보게 한다. https://wikidocs.net/16038 sx, sy에서 -1을 해주기 때문에, nextqueue.append()할때 +1을 해준다. from collections import deque def solution(m, n, infests, vaccinateds): visited = [n * [0] for _ in range(m)] way = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 감염자 queue = deque(infests) for x, y in infests: visited[x-1][y-1] = 1 # 백신 for x, y in vaccinateds: visited[x-1][y-1] = -1 # 예외: 그래프가 다 채워진 경우 for v in visited: if 0 in v: break else: return 0 # 탐색 day = 0 nextqueue = deque() while queue: search = queue.popleft() sx, sy = search[0]-1, search[1]-1 for w in way: wx, wy = w[0], w[1] if 0 <= sx + wx < m and 0 <= sy + wy < n and visited[sx + wx][sy + wy] == 0: visited[sx + wx][sy + wy] = 1 nextqueue.append([sx + wx + 1,sy + wy + 1]) # (X) 오류 : nextqueue.append([sx + wx,sy + wy]) # sx, sy에서 -1을 하기 때문에 여기서 -1이 된 값이 들어가면 안되므로, +1해준다. if (not queue) and nextqueue: while nextqueue: queue.append(nextqueue.popleft()) day += 1 # 예외: 그래프에 빈칸이 있는 경우 for v in visited: if 0 in v: return -1 return day

문자열 압축

from math import ceil def solution(s): length = [] # 예외: 길이가 1일 때 if len(s) == 1: return 1 #------------------------------------------------------------------- for i in range(1, len(s) // 2 + 1): # i : 잘라야 하는 단위 길이 prev, answer, num = '', '', 0 for j in range(ceil(len(s)/i)+1): # i 길이 만큼 자를때, 횟수 : ceil(len(s)/i) cut = s[j*i:(j+1)*i] # 단위 길이 만큼 자른 것 #--------------------------------------------------------------- if prev != cut: # 이전하고 같지 않으면, 정답에 이어 붙인다. if num != 1: # 연속되는 것이 1개가 아니면 숫자도 같이 이어 붙인다 answer += str(num) answer += prev prev, num = cut, 0 # prev를 cut으로 바꿔주고, 숫자 0으로 초기화 #--------------------------------------------------------------------- if prev == cut: # 연속되는 문자일 경우 num += 1 # num += 1 length.append(len(answer[1:])) # 최종적으로 길이를 배열에 추가 return min(length) # 최소의 길이를 출력 # 멘토 풀이 def solution2(s): answer = len(s) for size in range(1, len(s) // 2 + 1): # 자르는 길이의 단위를 1부터 절반까지만 사용하겠다 count = 1 # 반복되는 횟수 compress = 0 prev = s[:size] for i in range(size, len(s) + size, size): # 루프를 돌리는데, size만큼씩 돌린다, len(s) + size를 안해주면 마지막이 빠지게 됨 >>> 루프를 돌린 값은 i이다 curr = s[i:i + size] if prev == curr: # 자른 것이 이전과 같으면 count += 1 # count += 1 else: # 자른 것이 이전과 다르면 # 문자열 길이만 알면 된다 >>> size : 자른 문자열 길이 + count를 문자로 바꿨을때 길이 compress += size + len(str(count)) if 1 < count else len(prev) prev = curr # 문자 바꿔주기 count = 1 # 카운트 초기화 answer = min(answer, compress) return answer

from http://jooseop.tistory.com/26 by ccl(A) rewrite - 2021-08-22 01:26:18