-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/148653 """ # 풀이 과정 def solution(storey): x = list(str(storey)) x = list(map(int, x)) count = 0 if len(x) == 1: return x[0] if x[0] <= 5 else 10 - x[0] + 1 for k in range(len(x) - 1, 0, -1): a = 10 - x[k] b = x[k] if b < 5: count += b elif b == 5: if k - 1 >= 0 and x[k - 1] >= 5: x[k - 1] = x[k - 1] + 1 count += b else: count += b else: count += a if k - 1 >= 0: x[k - 1] += 1 if x[0] <= 5: return count + x[0] else: return count + 10 - x[0] + 1
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/67258 """ # 풀이 과정 """ 투포인터 """ import heapq from collections import defaultdict from collections import deque from collections import Counter def solution(gems): # 종류 check = len(set(gems)) start, end = 0, 0 my = defaultdict(int) result = float("inf") result_start, result_end = float("inf"), float("inf") my[gems[start]] += 1 while start <= len(gems) - 1: if len(my) != check: if end < len(gems) - 1: end += 1 my[gems[end]] += 1 else: break else: if end - start < result: result = end - start result_start, result_end = start, end if start == end: return [start + 1, end + 1] else: my[gems[start]] -= 1 if my[gems[start]] == 0: del my[gems[start]] start += 1 # 마지막 if not result_start <= len(gems) and not result_end <= len(gems): return [1, len(gems)] return [result_start + 1, result_end + 1]
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/169199 """ # 풀이 과정 def solution(board): from collections import deque check = deque() finish = [] m, n = len(board), len(board[0]) check_board = [[" "] * n for k in range(m)] # 최소 거리를 담는 보드 for x in range(len(board)): # 출발 및 목적지 위치 확인 for y in range(len(board[0])): if board[x][y] == "R": check.append([x, y, 0]) if board[x][y] == "G": finish.append([x, y]) if check and finish: break f_x, f_y = finish[0][0], finish[0][1] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while check: a, b, c = check.popleft() for v, w in zip(dx, dy): new_a = a new_b = b while True: if 0 <= new_a + v < len(board) and 0 <= new_b + w < len(board[0]) and board[new_a + v][ new_b + w] != "D": new_a += v new_b += w else: if check_board[new_a][new_b] == " ": check.append([new_a, new_b, c + 1]) check_board[new_a][new_b] = c + 1 break else: if check_board[new_a][new_b] > c + 1: check.append([new_a, new_b, c + 1]) check_board[new_a][new_b] = c + 1 break return -1 if check_board[f_x][f_y] == " " else check_board[f_x][f_y]
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42579 """ # 내 풀이 from collections import defaultdict def solution(genres, plays): g = defaultdict(int) g_num = defaultdict(list) for i in range(len(genres)): g[genres[i]] += plays[i] g_num[genres[i]].append((plays[i], i)) check = [] for k in g_num.keys(): g_num[k].sort(key=lambda x: (-x[0], x[1])) check.append((g[k], k)) check.sort(reverse=True) result = [] for i, j in check: n = 0 for count, num in g_num[j]: result.append(num) n += 1 if n == 2: break return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/132265 """ # 풀이과정 def solution(topping): from collections import Counter k = Counter(topping) check = set() result = 0 for a in topping: k[a] -= 1 check.add(a) if k[a] == 0: del k[a] if len(k) == len(check): result += 1 return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/150365 """ # 풀이 과정 # 같은 곳을 두 번 방문할 수 있다 # 거리가 k로 고정 # bfs 같은 곳 방문 여러번 가능 단 거리는 k여야 한다 # dx dy [1,0]은 아래로 가는 것이다 위x 격자 미로에서 상상해야 한다 # 시간 초과 발생: 길이가 k가 되는 것들을 모아 다시 도착 지점에 있는지 확인 하는 방법 생각해보고 접근해보기! # d,l,r,u # ddd 다음 ddl ddr 이런 방향성에서 생각해보기 dfs로 접근도 생각해보기 bfs가 아닌 # 먼저 갈 방향성이 정해져 있다는 사실 인지 후 풀이 재구성 from collections import deque def solution(n, m, x, y, r, c, k): dx = [1, 0, 0, -1] dy = [0, -1, 1, 0] # s=[x,y] # 출발 지점 # d=[r,c] # 도착 지점 # n*m 격자 result = "" while True: if 1 <= x + 1 <= n and abs(x + 1 - r) + abs(y - c) + len(result) + 1 <= k: result = result + "d" x += 1 elif 1 <= y - 1 <= m and abs(x - r) + abs(y - 1 - c) + len(result) + 1 <= k: result = result + "l" y -= 1 elif 1 <= y + 1 <= m and abs(x - r) + abs(y + 1 - c) + len(result) + 1 <= k: result = result + "r" y += 1 elif 1 <= x - 1 <= n and abs(x - 1 - r) + abs(y - c) + len(result) + 1 <= k: result = result + "u" x -= 1 else: return "impossible" # len(result)==k if len(result) == k: if x == r and y == c: return result else: return "impossible"
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12913 """ # 풀이과정 # 통째로 사고하기!! # 하나 하나씩 골라서 생각하는게 아닌 모두 수에 최대값을 추린 후 거듭 더해준 후 그 중 최대값을!! def solution(land): for i in range(1, len(land)): for j in range(4): land[i][j] += max(land[i - 1][:j] + land[i - 1][j + 1:]) return max(land[len(land) - 1])
-
""" 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/76503 """ # 풀이 과정 """ 생각방향: 리프노드를 모두 0으로 만든 후의 생각 접근 핵심 접근 생각 방향 시작:한 곳으로 모으기 생각 #각 점이 간선의 개수가 많은 곳으로 옮기기 #각 점이 간선의 개수가 같다면 가중치가 많은 쪽으로 이동 #위의 두 개 조차 같다면 번호가 작은쪽으로 # 모든 점들이 서로 연결되지 않은 경우 생각해서 체크 필요 # 한 곳으로 모으기 vs 여러 곳으로 나눠모으기 목표:모든 점들의 가중치를 0으로 만들기 """ from collections import defaultdict from collections import deque import sys sys.setrecursionlimit(10 ** 6) # 간선 연결 확인 m = defaultdict(list) result = 0 def dfs(c, p, a): global m, result for up in m[c]: if up != p: dfs(up, c, a) a[p] += a[c] result += abs(a[c]) return result def solution(a, edges): global m, result for i, j in edges: m[i].append(j) m[j].append(i) # a: 각 점의 가중치를 의미 edges: 간선 n = len(a) if sum(a) != 0: return -1 dfs(0, 0, a) return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/154539 """ # 풀이 과정 def solution(numbers): stack = [] answer = [-1] * len(numbers) for i in range(len(numbers)): while stack and numbers[stack[-1]] < numbers[i]: answer[stack.pop()] = numbers[i] stack.append(i) return answer
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42893 """ # 풀이 과정 """ 조건: 기본점수: 검색어가 등장하는 횟수 외부링크 수:다른 외부 페이지와 연결된 개수 링크점수:기본점수/외부링크 수 총합 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다. """ from collections import defaultdict from collections import deque import re def solution(word, pages): mylink = defaultdict(list) linkbasic = defaultdict(int) url_list = [] # 기본점수, 외부 링크점수 check = [[0] * 2 for i in range(len(pages))] # 웹페이지별 구분 linkpage = [] # 내부 링크 구분 및 링크 정리 > linkpage for n in range(len(pages)): url = re.search('<meta property=\"og:url\" content=\"https://([\S]+)\".*/>', pages[n]).group(1) linkpage.append(url) url_list.append(url) page = re.findall('<a href=\"https://([\S]+)\">', pages[n]) if len(page) > 0: mylink[url] = page else: mylink[url] = [] # if page is None: # check[n][1]=0 # else: # check[n][1]=len(page) count = 0 for w in re.findall('[a-zA-Z]+', pages[n]): if w.upper() == word.upper(): count += 1 linkbasic[url] = count # mylink=defaultdict(list) # linkbasic=defaultdict(int) result = -1 final = defaultdict(int) for my, another in mylink.items(): # 홍보를 받는 다른 곳 for link in another: if len(mylink[my]) > 0: final[link] += linkbasic[my] / len(mylink[my]) final[my] += linkbasic[my] for r in range(len(url_list)): if final[url_list[r]] > result: result = final[url_list[r]] answer = r return answer
