Algorithm202 LeetCode 1578 - Minimum Deletion Cost to Avoid Repeating Letters (Medium) 문제 LeetCode - 1578번 풀이 과정 연속된 문자열에서 인접한 각 쌍의 문자가 서로 달라야 하는데 필요한 보정 값을 구하는 문제입니다. 때문에 각 문자를 하나씩 순회하며 같은 문자로 이루어진 인접한 그룹들을 찾고, 이 그룹 내에서 가장 비용이 큰 문자를 제외하고 다른 모든 문자들을 선택해서 제거하면 됩니다. 저 같은 경우 각각의 그룹을 먼저 만들고 비용을 계산했는데, 사실 이럴 필요없이 그냥 각 문자를 순회하며 인접한 문자들이 서로 같을 때 그때그때 그룹을 만들어서 비용을 체크해줘도 됩니다. 코드 /** * @param {string} s * @param {number[]} cost * @return {number} */ var minCost = function (s, cost) { const .. 2021. 3. 8. LeetCode 904 - Fruit Into Baskets (Medium) 문제 LeetCode - 904번 풀이 과정 최대 2종류의 과일을 담을 수 있는 바구니를 이용해서 가능한 많은 과일을 담은 경우를 찾는 투 포인터 문제입니다. head 와 tail 을 이용해서 과일을 하나씩 순회하는데, 2종류의 제약조건을 만족시키는 과일이면 tail 을 증가시키고 그렇지 않을 경우 이를 만족할때까지 head 를 증가시키는 방법을 이용해서 구현합니다. 코드 /** * @param {number[]} tree * @return {number} */ var totalFruit = function (tree) { let head = 0; let tail = 0; let answer = 1; const basket = new Map(); basket.set(tree[head], 1); while.. 2021. 3. 8. BOJ 8972 - 미친 아두이노 문제 백준 온라인 저지 - 8972번 풀이 과정 플레이어와 미친 아두이노의 동작을 시뮬레이션하는 구현 문제입니다. 조건이 많은 구현문제이기 때문에 모듈화에 신경을 많이 써서 해결했습니다. 플레이어와 로봇의 위치를 나타내는 객체를 게임판과 별도로 선언하고 게임판 이동, 게임 종류 유무를 판단해줬습니다. 문제 구현하면서 python 에서 제공하는 any 함수를 알게되었습니다. Javascript 의 some 고차함수와 유사한데 콜백을 인자로 받지 않아 사용방법이 좀 다르다는 차이점이 있습니다. 이외에도 플레이어와 로봇이 이동할 때 각 위치에서 여러개의 로봇이나 플레이어가 파괴되기 전 동시에 위치할 수 있기 때문에 deque 를 이용해서 관리했습니다. 코드 import sys from collections i.. 2021. 3. 8. BOJ 19941 - 햄버거 분배 문제 백준 온라인 저지 - 19941번 풀이 과정 햄버거와 사람의 위치가 주어질 때 가장 많은 햄버거를 먹는 방법을 찾는 그리디 문제입니다. 일정 범위내의 햄버거를 먹을 수 있기 때문에 왼쪽부터 오른쪽으로 하나씩 먹을 수 있는 햄버거를 찾으면 됩니다. 코드 import sys N, K = list(map(int, sys.stdin.readline().split())) table = sys.stdin.readline().strip() def solution(): eat = [0] * N answer = 0 for i in range(N): if table[i] == 'P': for offset in range(-K, K + 1): ni = i + offset if 0 2021. 3. 8. BOJ 16469 - 소년 점프 문제 백준 온라인 저지 - 16469번 풀이 과정 넉살, 스윙스, 창모 세 사람의 좌표가 주어질 때 마미손 이 위치할 수 있는 좌표를 찾는 문제입니다. 맨 처음 접근 방법은 마미손 은 세 사람이 모일 수 있는 한 좌표까지의 거리 값이 가장 짧은 곳에 위치하기 때문에 이를 위해서 각 점에 대해서 다익스트라 알고리즘으로 최단 거리를 계산했었습니다. 그러나 이 경우 시간 복잡도가 O(V^2*ElogV) 이기 때문에 시간 초과가 발생하였고, 다른 방법으로의 접근이 필요했습니다. 생각해보면 모든 좌표에서 다익스트라 를 수행할 필요 없이 그냥 넉살, 스윙스, 창모 세 사람을 기준으로 탐색을 수행한 다음, 각 좌표들에 대해서 거리 최댓값끼리 비교해주면 됩니다. 따라서 그냥 BFS 를 이용해서 세 사람을 시작지점으로 .. 2021. 3. 5. BOJ 13565 - 침투 문제 백준 온라인 저지 - 13565번 풀이 과정 섬유의 바깥쪽에서 안쪽으로 침투가 가능한지 판단하는 BFS 문제입니다. 0번째 행에서 시작해서 M-1 번째 행에 도달 가능한지 판단하면 됩니다. 코드 import sys from collections import deque M, N = list(map(int, sys.stdin.readline().split())) board = [list(sys.stdin.readline().strip()) for _ in range(M)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def in_range(x, y): return 0 2021. 3. 5. 이전 1 ··· 18 19 20 21 22 23 24 ··· 34 다음
