""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/17677 """ # 풀이 과정 def solution(str1, str2): # a,b 모두 공집합일 경우 자카드 유사도 1로 정의 eng = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" eng = list(eng) str1 = list(str1.upper()) str2 = list(str2.upper()) a = [] # str1 집합 b = [] # str2 집합 u = 0 n = 0 for i in range(len(str1) - 1): new = "" if str1[i] in eng: new += str1[i] else: continue if str1[i + 1] in eng: new += str1[i + 1] else: continue a.append(new) for i in range(len(str2) - 1): new = "" if str2[i] in eng: new += str2[i] else: continue if str2[i + 1] in eng: new += str2[i + 1] else: continue if new in a: u += 1 n += 1 k = a.index(new) del a[k] else: u += 1 u += len(a) if u == 0 and n == 0: return 65536 else: return int((n / u) * 65536)

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/43162 """ # 풀이 과정 from collections import defaultdict from collections import deque import copy def solution(n, computers): network = defaultdict(set) result = [] for i in range(len(computers)): network[i].add(i) for j in range(len(computers[0])): if computers[i][j] == 1: network[i].add(j) network[j].add(i) check = deque([i for i in range(n)]) visit = set([]) new = set([]) while check: start = check.popleft() if start in visit: continue q = deque([start]) while q: v = q.popleft() visit.add(v) new.add(v) for end in network[v]: if not end in visit and not end in new: q.append(end) net = copy.deepcopy(new) result.append(net) return len(result)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42586 """ # 풀이 과정 def solution(progresses, speeds): from collections import deque p = deque(progresses) s = deque(speeds) result = [] count = 0 # 작업 개수 check = len(p) # 1사이클 while p: count += 1 a = p.popleft() b = s.popleft() a += b p.append(a) s.append(b) if count == check: finish = 0 for f in list(p): if f >= 100: p.popleft() s.popleft() finish += 1 else: break if finish != 0: result.append(finish) check = len(p) count = 0 else: check = len(p) count = 0 return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12979 """ # 풀이 과정 from collections import deque def solution(n, stations, w): before = set(stations) # 기지국 설치 new = set([]) s = deque(stations) min_network = 0 max_network = 0 result = 0 # 시작부분 범위 내에 없는 경우 if s[0] - w > 1: max_network = 1 + 2 * w new.add(1 + w) result += 1 # 기지국 개설 후 시작 else: max_network = s.popleft() + w while max_network < n: if len(s) > 0: # 이미 설치된 곳의 전파가 드는 권역에 있는 경우(연장하기) if s[0] - w <= max_network <= s[0] + w: max_network = s[0] + w s.popleft() # 전파가 드는 권역이 아닌 경우(최대한 넓은 범위를 커버하게하기) elif s[0] - w >= max_network + 1: result += 1 new.add(max_network + 1 + w) max_network = max_network + 1 + 2 * w # 이미 최대로 설치된 곳의 최대치보다 범위가 현재 넓은 경우 elif s[0] + w < max_network: while True and s: if s[0] + w <= max_network: s.popleft() else: break else: result += 1 new.add(max_network + 1 + w) max_network = max_network + 1 + 2 * w # print(s,max_network) return len(new - before)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/138476 """ #풀이과정 def solution(k, tangerine): count = {} for x in tangerine: if not str(x) in count: count[str(x)] = 1 else: count[str(x)] += 1 count = sorted(count.items(), key=lambda x: -x[1]) result = [] for y, z in count: if k > 0: result.append(y) k -= z else: break return len(result)

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/challenges?order=recent&levels=3&languages=python3&page=3 """ # 풀이 과정 from collections import deque # 기둥 유지 가능 여부 확인 def check_up(x, y, check): # 그 아래 기둥이 있는 경우 if (x, y - 1, x, y) in check: # check.add((x,y,x,y+1)) return True # 그 아래 보가 있을 경우 elif (x - 1, y, x, y) in check or (x, y, x + 1, y) in check: # check.add((x,y,x,y+1)) return True else: return set([(x, y, x, y + 1)]) # 보 유지 가능 여부 확인 def check_right(x, y, check): # 밑에 기둥이 있거나, 양쪽 보가 존재가 할 경우 if (x, y - 1, x, y) in check or (x + 1, y - 1, x + 1, y) in check: # check.add((x,y,x+1,y)) return True # 양쪽 보가 존재할 경우 elif (x - 1, y, x, y) in check and (x + 1, y, x + 2, y) in check: # check.add((x,y,x+1,y)) return True else: return set([(x, y, x + 1, y)]) def solution(n, build_frame): # 기둥,보 설치 확인 check = set([]) for x, y, a, b in build_frame: # 설치 1 if b == 1: # 기둥 if a == 0: # 바닥인경우 if y == 0: check.add((x, y, x, y + 1)) else: # 그 아래 기둥이 있는 경우 if (x, y - 1, x, y) in check: check.add((x, y, x, y + 1)) # 그 아래 보가 있을 경우 elif (x - 1, y, x, y) in check or (x, y, x + 1, y) in check: check.add((x, y, x, y + 1)) # 보 else: if y != 0: # 밑에 기둥이 있거나, 양쪽 보가 존재가 할 경우 if (x, y - 1, x, y) in check or (x + 1, y - 1, x + 1, y) in check: check.add((x, y, x + 1, y)) # 양쪽 보가 존재할 경우 elif (x - 1, y, x, y) in check and (x + 1, y, x + 2, y) in check: check.add((x, y, x + 1, y)) else: q = deque([]) up = [(0, 1, 0, 2), (-1, 1, 0, 1), (0, 1, 1, 1)] # 기둥 right = [(1, 0, 2, 0), (1, 0, 1, 1), (-1, 0, 0, 0), (0, 0, 0, 1)] # 보 # 기둥 if a == 0: k = set([(x, y, x, y + 1)]) check = check - k # 기둥 제거 # 제거되는지 여부 판단 for a, b, c, d in up: if (x + a, y + b, x + c, y + d) in check: # 기둥 if d - b == 1: flag = check_up(x + a, y + b, check) if flag != True: check = check | k break else: flag = check_right(x + a, y + b, check) if flag != True: check = check | k break else: k = set([(x, y, x, y + 1)]) check = check - k # 기둥 제거 """ for a,b,c,d in up: if (x+a,y+b,x+c,y+d) in check: q.append((x+a,y+b,x+c,y+d)) """ # 보 제거 여부 판단 else: k = set([(x, y, x + 1, y)]) check = check - k # 기둥 제거 # 제거되는지 여부 판단 for a, b, c, d in right: if (x + a, y + b, x + c, y + d) in check: # 기둥 if d - b == 1: flag = check_up(x + a, y + b, check) if flag != True: check = check | k break else: flag = check_right(x + a, y + b, check) if flag != True: check = check | k break else: k = set([(x, y, x + 1, y)]) check = check - k # 기둥 제거 """ for a,b,c,d in right: if (x+a,y+b,x+c,y+d) in check: q.append((x+a,y+b,x+c,y+d)) break else: k=set([(x,y,x+1,y)]) check=check-k # 보 제거 """ """ for a,b,c,d in right: if (x+a,y+b,x+c,y+d) in check: q.append((x+a,y+b,x+c,y+d)) """ # 기둥 또는 보를 제거함으로써 주변 제거할 기둥 보 탐색 """ while q: k=q.popleft() # 기둥 if k[3]-k[1]!=0: shape="기둥" exist=check_up(k[0],k[1],check) # 보 else: shape="보" exist=check_right(k[0],k[1],check) if exist==True: continue else: check=check-exist if shape=="기둥": for a,b,c,d in up: if (k[0]+a,k[1]+b,k[0]+c,k[1]+d) in check: q.append((k[0]+a,k[1]+b,k[0]+c,k[1]+d)) else: for a,b,c,d in right: if (k[0]+a,k[1]+b,k[0]+c,k[1]+d) in check: q.append((k[0]+a,k[1]+b,k[0]+c,k[1]+d)) """ # print(check,"check") # 마무리 단계 재 구조화 result = [] for a, b, c, d in check: if d - b == 1: s = 0 else: s = 1 result.append([a, b, s]) result.sort() return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42885 """ # 풀이 과정 def solution(people, limit): from collections import deque answer = 0 people.sort(reverse=True) people = deque(people) while people: a = people.popleft() if len(people) > 0: b = people.pop() else: b = 0 if a + b > limit: people.append(b) answer += 1 return answer

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/388353 """ # 풀이과정 """ 겉면에서 출발하는 bfs실시 후 도착 가능한 알파벳 제거 두 번 반복된 경우 적용할 필요 없음 모두 그냥 빼버리는게 가능 해당 알파벳 찾은 후 빈공간으로 bfs 적용하는 방식이 좀 더 효율적일거라 생각된다. """ """ 겉면에서 출발하는 bfs실시 후 도착 가능한 알파벳 제거 두 번 반복된 경우 적용할 필요 없음 모두 그냥 빼버리는게 가능 해당 알파벳 찾은 후 빈공간으로 bfs 적용하는 방식이 좀 더 효율적일거라 생각된다. 모든 화물에 대해 이동 가능 조사 후 bfs에 나중에 반영 중간중간 반영x 몆 가지 케이스가 시간초과 발생 개선 방법 과정 >수정 방안 고민 > global 맵 생성 후 그 자리를 지나면 지게차로 가능하다 판정 여부 확인 > 없는 알파벳 존재 여부 추가 후 확인 정답 과정: visit한 여부를 이동 직후 바로 도착으로 확인해야 시간을 단축할 수 있다. """ from collections import deque, Counter map = [] def bfs(s, i, j): global map m = len(s) n = len(s[0]) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] q = deque([(i, j)]) flag = False visit = [[False] * n for _ in range(m)] while q: x, y = q.popleft() visit[x][y] = True if map[x][y] == True: return True for nx, ny in zip(dx, dy): if nx + x >= m or nx + x < 0: flag = True break elif ny + y >= n or ny + y < 0: flag = True break else: if s[nx + x][ny + y] == "" and visit[nx + x][ny + y] == False: q.append((nx + x, ny + y)) visit[nx + x][ny + y] = True # 지게차 맵 재갱신 if flag == True: # map[i][j]==True for a in range(m): for b in range(n): if visit[a][b] == True: map[a][b] == True return flag def check_alpha(s, alpha): del_alpha = [] global map map = [[False] * len(s[0]) for _ in range(len(s))] for i in range(len(s)): for j in range(len(s[0])): if s[i][j] == alpha: check = bfs(s, i, j) if check == True: del_alpha.append((i, j)) for x, y in del_alpha: s[x][y] = "" return s, len(del_alpha) def all_alpha(s, alpha): for i in range(len(s)): for j in range(len(s[0])): if s[i][j] == alpha: s[i][j] = "" return s def solution(storage, requests): s = [] all_ = "" for stor in storage: s.append(list(stor)) all_ += stor count_alpha = Counter(all_) for r in requests: if not r[0] in count_alpha: continue if count_alpha[r[0]] == 0: continue if len(r) == 2: alpha = r[0] count_alpha[alpha] = 0 s = all_alpha(s, alpha) else: alpha = r s, num = check_alpha(s, alpha) count_alpha[alpha] -= num count = 0 for i in range(len(s)): for j in range(len(s[0])): if s[i][j] != "": count += 1 return count

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/86053 """ # 풀이 과정 """ 조건: 새 도시를 만들 조건: 금:a 은:b 이해 과정:i번 도시에는 일정 이상의 광물이 있고, 새 도시에 광물을 전달해준다 목표:새로운 도시를 건설하기 위한 최단 시간을 구하시오 """ """ # 필요한 금:a 은:b g[i]:i번 도시에 보유한 금 s[i]:i번 도시에 보유한 은 신도시까지 이동시간: t[i] 옮길 수 있는 최대 양 w[i] """ # 생각 방향: 각 도시에 일정량을 가져오는 경우를 모두 산정 후 그 중 누적 후 시간이 최소인것을 구한다. # 시간 빠른 순으로 트럭을 돌려보내고 받고를 한 후 금과 은 중에 더 많은 광석을 먼저 소비하는 방식으로 한 후 다시 heap 리스트에 추가! # 시간을 1씩 올려서 혹은 내려서 접근하는 방식은 많은 시간을 소요해 시간초과로 이어진다 # 이분탐색(이진탐색)을 바탕으로 접근해야 한다 import heapq def solution(a, b, g, s, w, t): start = 0 end = (10 ** 9) * (10 ** 5) * 4 result = (10 ** 9) * (10 ** 5) * 4 # 도시 개수 city = len(g) while start <= end: gold_max, gold_min = 0, 0 silver_max, silver_min = 0, 0 weight = 0 mid = (start + end) // 2 for k in range(city): # 편도 횟수 count = mid // t[k] # 왕복만 가능 if count % 2 == 0: check = (count // 2) * w[k] if check >= s[k] + g[k]: check = s[k] + g[k] weight += check silver_max += s[k] silver_min += s[k] gold_max += g[k] gold_min += g[k] else: weight += check if check >= s[k]: silver_max += s[k] gold_min += check - s[k] # 실버만 채워야함 else: silver_max += check if check >= g[k]: gold_max += g[k] silver_min += check - g[k] else: gold_max += check # 마지막 편도 한 번까지 가능 else: check = ((count // 2) + 1) * w[k] if check >= s[k] + g[k]: check = s[k] + g[k] weight += check silver_max += s[k] silver_min += s[k] gold_max += g[k] gold_min += g[k] else: weight += check if check >= s[k]: silver_max += s[k] gold_min += check - s[k] # 실버만 채워야함 else: silver_max += check if check >= g[k]: gold_max += g[k] silver_min += check - g[k] else: gold_max += check if weight >= a + b and gold_max >= a and silver_max >= b: result = min(result, mid) end = mid - 1 # num=silver_max # for i in range(gold_min,gold_max+1): # if i >=a and num>=b: # break # else: # num-=1 # else: # start=mid+1 # continue # result=min(result,mid) # end=mid-1 else: start = mid + 1 return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/87377 """ # 풀이 과정 def solution(line): from itertools import combinations # 직선 2개씩 묶음 집합 k = list(combinations(line, 2)) # 교점들의 집합 result = [] line_x, line_y = [], [] for a in k: a = list(a) # ad-bc check 평행 또는 일치 확인 if a[0][0] * a[1][1] - a[0][1] * a[1][0] == 0: continue else: x = (a[0][1] * a[1][2] - a[0][2] * a[1][1]) / (a[0][0] * a[1][1] - a[0][1] * a[1][0]) y = (a[0][2] * a[1][0] - a[0][0] * a[1][2]) / (a[0][0] * a[1][1] - a[0][1] * a[1][0]) if int(x) == x and int(y) == y: result.append([int(x), int(y)]) line_x.append(int(x)) line_y.append(int(y)) ################### 교점까지 완료 ################## # print(result) # print(line_x) line_y.sort() print(line_y) line_x.sort() print(line_y) """ if abs(line_x[0])>=abs(line_x[-1]): max_x=abs(line_x[0]) else: max_x=abs(line_x[-1]) """ check_x = max(line_x) - min(line_x) + 1 # print(check_x,"x") map = [list("." * check_x) for b in range(min(line_y), max(line_y) + 1)] # print(map, "map") result.sort(key=lambda x: (-x[1])) # print(result) for c, d in result: # print(max(line_y)-d,max_x+c,"좌표 확인") map[max(line_y) - d][c - min(line_x)] = "*" for t in range(len(map)): map[t] = "".join(map[t]) # print(map) return map # print(result) # print(int(max_x),int(max_y),"최대값") # result.sort(key=lambda x:(-x[1],x[0])) # result=deque(result) answer = [] check_y = 0 star = "" print(max_x, max_y, "최댓값") print(result) map = [list("." * (max_x * 2 + 1))] * (max_y * 2 + 1) # x,y middle max_x+1: x middle max_y+1: y middle for v, w in result: if v >= 0 and w >= 0: map[max_y - abs(w)][max_x + abs(v)] = "*" elif v >= 0 and w < 0: map[max_y - abs(w)][max_x - abs(v)] = "*" elif v < 0 and w >= 0: map[max_y + abs(w)][max_x + abs(v)] = "*" else: map[max_y + abs(w)][max_x - abs(v)] = "*" for t in range(len(map)): map[t] = "".join(map[t]) # print(map) return answer