👨💻📱✍️🎢314 BOJ 18111 - 마인크래프트 문제 백준 온라인 저지 - 18111번 풀이 과정 격자 형태의 땅이 주어지고 높이를 맞추기 위한 최소 시간과 그때의 높이를 구하는 문제입니다. 처음에는 이분 탐색 을 이용해서 최소 시간을 구하려고 했지만 동일한 시간에 높이가 최대인 경우를 찾는 과정이 명확하지 않아서 그냥 완전 탐색 으로 해결하는 것으로 방향을 잡았습니다. 총 0 ~ 256 의 높이를 탐색하면 되는데 이때 격자를 O(N^2) 으로 탐색하면 시간 초과가 발생합니다. 대신 전처리 과정을 통해 각 격자의 높이 값을 저장하고 기준 높이보다 작거나 큰 개수를 세어 필요한 시간 값을 계산하면 됩니다. 코드 import sys N, M, B = list(map(int, sys.stdin.readline().split())) board = [list(.. 2021. 3. 8. BOJ 1806 - 부분합 문제 백준 온라인 저지 - 1806번 풀이 과정 투 포인터 를 활용해서 연속된 수열의 합이 S 이상인 구간 중 가장 길이가 짧은 구간을 찾는 문제입니다. 모든 숫자가 양의 정수이므로 두 개의 포인터 head, tail 을 사용해서 합이 S 보다 커질 경우 head 를 증가시키고 S 보다 작아질 경우 tail 을 증가시키면 됩니다. 코드 import sys N, S = list(map(int, sys.stdin.readline().split())) nums = list(map(int, sys.stdin.readline().split())) def solution(): answer = sys.maxsize head, tail = 0, 1 acc = nums[head] + nums[tail] while head 2021. 3. 8. BOJ 6186 - Best Grass 문제 백준 온라인 저지 - 6186번 풀이 과정 인접한 잔디 뭉치의 개수를 찾는 문제입니다. 잔디 뭉치는 서로 인접하지 않기 때문에 각 좌표를 순회하면서 잔디가 발견되면 인접한 네 방향을 모두 방문해보는 방법으로 모든 잔디 뭉치를 탐색할 수 있습니다. 코드 import sys R, C = list(map(int, sys.stdin.readline().split())) grass = [list(sys.stdin.readline().strip()) for _ in range(R)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def solution(): clump = 0 visit = [[0] * C for _ in range(R)] for r in range(R): for c in .. 2021. 3. 8. 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. 이전 1 ··· 32 33 34 35 36 37 38 ··· 53 다음
