""" 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/87694 """ # 풀이 과정 """ 사각형들의 모든 점들을 알아낸 후 주어진 점을 이동시키는 것을 실행 그 중 사각형 내부에 있는 점 거르기+중복점 제거 생각 아이디어 그리고 매 순간 그 중 아이템이 있는 점에 도달하는 지 여부 확인+ 최단 거리 구하기 # 주어진 조건들 통하여 알 수 있는 정보: 주어진 점들의 좌표들, 선분들의 좌표, 외부에 있는 점들의 좌표, """ from collections import deque def solution(rectangle, characterX, characterY, itemX, itemY): # sol(내부의 선분등을 제대로 표현하기 힘듬) # # 내부에 있지 않은 점 # check=set([]) # for x1,y1,x2,y2 in rectangle: # new=[] # for v1,w1,v2,w2 in rectangle: # if v1<x1<v2 and w1<y1<w2: # new.append((x1,y1)) # if v1<x2<v2 and w1<y1<w2: # new.append((x2,y1)) # if v1<x1<v2 and w1<y2<w2: # new.append((x1,y2)) # if v1<x2<v2 and w1<y2<w2: # new.append((x2,y2)) # check=check|(set([(x1,y1),(x1,y2),(x2,y1),(x2,y2)])-set(new)) # 이동시킬 맵 m = [[0] * (101) for _ in range(101)] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # 사각형 위의 모든 점 new = [] for x1, y1, x2, y2 in rectangle: for x in [x1 * 2, x2 * 2]: for y in range(y1 * 2, (y2) * 2 + 1): new.append((x, y)) for y in [y1 * 2, y2 * 2]: for x in range(x1 * 2, (x2) * 2 + 1): new.append((x, y)) new = set(new) # 중복 제거 # 사각형 내부의 점 구분 check = [] for x1, y1, x2, y2 in rectangle: for x, y in new: if x1 * 2 < x < x2 * 2 and y1 * 2 < y < y2 * 2: check.append((x, y)) road = new - set(check) for x, y in road: m[x][y] = 1 # m[characterX][characterY]="start" # m[itemX][itemY]="destination" q = [(characterX * 2, characterY * 2)] # 방문처리 확인 v = [[0] * 101 for _ in range(101)] plus = [] # 거리 result = 0 # bfs while q: x, y = q.pop() # 방문 처리 v[x][y] = 1 if x == itemX * 2 and y == itemY * 2: return result // 2 for nx, ny in zip(dx, dy): if 0 <= x + nx <= 100 and 0 <= y + ny <= 100 and v[x + nx][y + ny] == 0 and m[x + nx][y + ny] == 1: plus.append((x + nx, y + ny)) if len(q) == 0: plus = list(set(plus)) q += plus result += 1 plus = []

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42860 """ # 풀이 과정 # 틀린 이유 pop을 해버리면 도중에 다른 곳으로 이동할 때 A로 변한 부분을 거쳐갈 때 거리 커서 계산이 안됨 # 좌우 이동을 dfs로 풀이 # dfs from collections import deque import copy eng = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" # 커서 옮기는 방향 _ 왼쪽 def left(x, y, z): if len(x) == x.count("A"): return x, y, z while True: y += 1 z -= 1 if x[z] != "A": t = eng.find(x[z]) break if t >= 13: t = 26 - t y += t x[z] = "A" return x, y, z # 커서 옮기는 방향 _ 오른쪽 def right(x, y, z): if len(x) == x.count("A"): return x, y, z while True: y += 1 z += 1 if x[z] != "A": t = eng.find(x[z]) break if t >= 13: t = 26 - t y += t x[z] = "A" return x, y, z def solution(name): start = "A" * len(name) check = deque(list(name)) result = [] # 첫번째_커서 시작 위치 k = eng.find(check[0]) if k >= 13: k = 26 - k count = k check[0] = "A" if len(check) == check.count("A"): return count q = deque([check]) count_q = deque([k]) point_q = deque([0]) # 방향키 위치 while q: one = q.popleft() two = count_q.popleft() three = point_q.popleft() one_right = copy.deepcopy(one) two_right = copy.deepcopy(two) three_right = copy.deepcopy(three) left_q, left_num, left_p = left(one, two, three) right_q, right_num, right_p = right(one_right, two_right, three_right) if len(left_q) == left_q.count("A"): result.append(left_num) else: q.append(left_q) count_q.append(left_num) point_q.append(left_p) if len(right_q) == right_q.count("A"): result.append(right_num) else: q.append(right_q) count_q.append(right_num) point_q.append(right_p) return min(result) if len(result) > 0 else 0

""" 출처 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12971 """ # 풀이 과정 from collections import deque def solution(sticker): s = deque(sticker) if len(s) == 0 or len(s) == 1: return max(s) dp_one = [0] * len(s) dp_one[0] = s[0] dp_one[1] = max(s[0], s[1]) for i in range(2, len(s) - 1): dp_one[i] = max(dp_one[i - 1], dp_one[i - 2] + s[i]) k = s.popleft() s.append(k) one = max(dp_one) dp_two = [0] * len(s) dp_two[0] = s[0] dp_two[1] = max(s[0], s[1]) for i in range(2, len(s) - 1): dp_two[i] = max(dp_two[i - 1], dp_two[i - 2] + s[i]) two = max(dp_two) return max(one, two)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12980 """ # 풀이 과정 def solution(n): ans = 0 check = n while check >= 1: if check % 2 == 0: check = int(check / 2) else: check -= 1 ans += 1 return ans

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/70130 """ # 풀이 과정 """ 생각방향 # 부분수열의 모든 경우의 수를 비트마스크로 나타낸 후 스타수열 거르기 """ from itertools import combinations from collections import Counter def solution(a): result = 0 k = Counter(a) k = dict(k) # 최대 9개의 수를 데이터를 정렬하기에 많은 시간 소요 안됨 k_new = sorted(k.items(), key=lambda x: (x[1])) # 최대 숫자 모음 체크 check = [] for i, j in k_new: check.append(i) # 들어있는 숫자 횟수 n = 0 while check: # 스타수열의 교집합이 될 수 s = check.pop() # 스타수열 star = [] for num in range(len(a)): i = a[num] if len(star) % 2 == 0: star.append(i) else: if star[-1] != s and i != s: continue elif star[-1] == s and i != s: star.append(i) elif star[-1] != s and i == s: star.append(i) if len(star) % 2 == 1: star.pop() result = max(result, len(star)) if len(check) > 0: # 이후 만들어질 최대 개수 보다 이미 많을 경우 더이상 무의하기는거 확인 if k[check[-1]] * 2 < result: return result return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42577 """ # 풀이과정 def solution(phone_book): p = phone_book p.sort() for a in range(len(p) - 1): if p[a] in p[a + 1][0:len(p[a])]: return False else: continue return True

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/136797 """ # 풀이 과정 # 목표: 최소한의 시간으로 타이핑을 하는 경우의 가중치 # 이동하지 않고 제자리 누르기:1 상하좌우 이동 후 누르기:2 대각선:3 # 왼손 오른손 중 가중치가 제일 적은 경우의 수들의 합 # 같은 번호에 두 손가락 놓는거 불가 # 상하좌우 두 번 가는것보다 대각선 한 번이 더 이득 # 최솟값+최솟값 = 최솟값 명제는 항상 성립 # 번호판을 dp로 생각 후 마지막 번호의 dp값이 가중치 최솟값으로 생각접근해보기 # 다시 정리하는 dic.items(): key,value 둘다 # dic.keys(): key 값 # dic.values(): values 모두 키값에 관계없이 모두 from collections import deque # 왼손 가중치 계산 def left_hand(new_x, new_y): l = 0 while True: if new_x > 0 and new_y > 0: l += 3 new_x -= 1 new_y -= 1 elif new_x > 0 and new_y == 0: l += 2 new_x -= 1 elif new_x == 0 and new_y > 0: l += 2 new_y -= 1 elif new_x == 0 and new_y == 0: l += 1 break if new_x == 0 and new_y == 0: break return l # 오른손 가중치 계산 def right_hand(new_x, new_y): r = 0 while True: if new_x > 0 and new_y > 0: r += 3 new_x -= 1 new_y -= 1 elif new_x > 0 and new_y == 0: r += 2 new_x -= 1 elif new_x == 0 and new_y > 0: r += 2 new_y -= 1 elif new_x == 0 and new_y == 0: r += 1 break if new_x == 0 and new_y == 0: break return r # 숫자 위치 def point(k, i): # i의 번호 찾기 for a in range(4): for b in range(3): if k[a][b] == i: x = a y = b break return x, y from collections import deque def solution(numbers): k = [["1", "2", "3"], ["4", "5", "6"], ["7", "8", "9"], ["*", "0", "#"]] num = list("123456789*0#") n = list(numbers) last = n[-1] # 이전 가중치 # 이전에 해당번호에 도달했을때 가중치가 가장 적은 경우를 저장한 후 after의 최솟값으로 재갱신 # before={"1":0, "2":0,"3":0,"4":0,"5":0,"6":0,"7":0,"8":0,"9":0,"*":0,"#":7} # m 각 그래프 위치에 따른 가중치 m = [[0] * 12 for _ in range(12)] # i>j for i in range(12): x, y = point(k, num[i]) for j in range(12): dx, dy = point(k, num[j]) new_x = abs(x - dx) new_y = abs(y - dy) m[i][j] = right_hand(new_x, new_y) w = 0 left = "4" right = "6" # 현재 들어있는 손 가중치 now = {} hand = (left, right) now[hand] = w # p: numbers num:위치 인덱스 담은 배열 for c in n: after = {} # 다음 손 가중치 c_num = num.index(c) # c: 누를 번호 # h:손 n_w:손 가중치 (이전 손 위치로부터 온 가중치) # 이전 위치에서 온 가중치들을 저장함과 동시에 도착할 위치중 중복 위치시 최솟값으로 매 번 갱신 그 뿐만 아니라 # 중복된 위치는 dic으로 제거하기에 최대 갯수는 12**2로 유지된다 그 이상으로 늘어나지 않는다 for h, n_w in now.items(): l, r = h # 왼손, 오른손 l_num = num.index(l) r_num = num.index(r) if r == c: if not (l, c) in after.keys() or now[(l, c)] > n_w + 1: # 이해 과정: or 뒤의 두 번째 조건은 최소값일 경우 재갱신을 위해서이다! after[(l, c)] = n_w + 1 elif l == c: if not (c, r) in after.keys() or now[(c, r)] > n_w + 1: after[(c, r)] = n_w + 1 else: if not (l, c) in after.keys() or after[(l, c)] > n_w + m[r_num][c_num]: after[(l, c)] = n_w + m[r_num][c_num] if not (c, r) in after.keys() or after[(c, r)] > n_w + m[l_num][c_num]: after[(c, r)] = n_w + m[l_num][c_num] now = after return min(list(now.values()))

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/86971 """ # 풀이 과정 # 네트워크 2개로 분활 (나누어진 송전탑 개수 거의 비슷하게!) # 목표 나누어진 송전탑들의 차이를 return from collections import deque def bfs(graph, d): visited = [] queue = deque([d]) while queue: n = queue.popleft() if n not in visited: visited.append(n) queue += graph[n] return visited def solution(n, wires): # 탑의 개수 top = [(a + 1) for a in range(n)] result = n - 2 # 송전탑 개수 차이 최대(한 쪽 n-1, 한 쪽 1) for b in range(len(wires)): k = wires.copy() k.pop(b) # 간선을 하나씩 제거 graph = {} for c, d in k: if c not in graph: graph[c] = [d] else: graph[c] += [d] if d not in graph: graph[d] = [c] else: graph[d] += [c] check = bfs(graph, d) num = abs(n - len(check) - len(check)) if num < result: result = num return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12987 """ # 풀이 과정 """ permutations > 시간초과 A의 가장 작은값 순으로 나열시 B가 이기는 경우가 최대이다 A의 큰 값에 한해선 져주는게 이득이다(승을 가장 많이 챙기기 위해) A의 순서는 함정이다 어짜피 B는 그에 맞춰 대응할 수 있어 의미가 없다 그러므로 A의 순서는 자유롭게 바꾸고 그에 맞춰 최대 승수만 구하면 된다! """ from collections import deque def solution(A, B): A.sort() B.sort() A = deque(A) B = deque(B) result = 0 while A: a = A.popleft() while B: b = B.popleft() if b > a: result += 1 break if len(B) == 0: break return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/70129 """ # 풀이 과정 def solution(s): count = 0 count_0 = 0 while True: count += 1 count_0 += s.count("0") s = s.replace("0", "") s = len(s) s = str(bin(s))[2:] if s == "1": return [count, count_0] return 0