Algorithm (2138) 썸네일형 리스트형 (Rust) - LeetCode (Easy) : 3477. Fruits Into Baskets II https://leetcode.com/problems/fruits-into-baskets-ii/description전수조사로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화i번째 바구니를 사용했는지 여부를 확인하기 위해 vector checked 변수를 mut으로 선언해줍니다.📔 풀이과정📑 i번째 fruit를 담을 j번째 basket 크기를 비교fruits에 대해 iter수행하며 for_each마다 basket에 enumerate 했을 때 j번째가 현재 fruit 이상이라면 담을 수 있으므로 j번째 checked 를 true로 바꿔줍니다. 📑 checked배열에서 false인 값을 변수 unplaced 📑 시간 복잡도O(n^2)📑 공간 복잡도O(n)📔 정답 출력 | 반환unplaced를 .. (Rust) - LeetCode (Easy) : 1979. Find Greatest Common Divisor of Array https://leetcode.com/problems/find-greatest-common-divisor-of-array/description/gcd를 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화유클리드 호제법으로 gcd를 반환할 함수를 구현합니다. 시간복잡도는 O(logN)을 가집니다.📔 풀이과정nums의 최댓값, 최솟값을 뽑아 값이 있는 경우 max_num, min_num변수에 저장합니다.📑 시간 복잡도O(logN)📑 공간 복잡도O(N)📔 정답 출력 | 반환 값이 있는 경우 두 변수의 gcd값을 반환하며 아닌 경우 아무의미 없는 값 0을 반환합니다. if let문은 해당 분기 외의 조건에도 반환값을 강제하기 때문입니다.📕 Code📔 Rustuse std::cmp::max;impl.. (Python3) - LeetCode (Medium) : 802. Find Eventual Safe States https://leetcode.com/problems/find-eventual-safe-statesdfs 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 node별로 state를 저장할 배열을 선언합니다.📔 풀이과정📑 terminal node인지 검사하는 dfs를 구현합니다.기저 반환값을 지정합니다: cycle이 발생한다면 말단이 아니므로 False를 아니라면 말단이므로 True를 반환합니다.중간 계산값을 반환합니다: 현재 node의 state를 1로 만들어주고 이웃이 말단인지 검사해 그 중 하나라도 말단이 아니라면 False를 반환합니다.이웃들이 모두 말단이므로 현 node도 말단이기 때문에 True를 반환합니다.📑 시간 복잡도각 node별로 한 번 씩 검사하므로 O(N.. (Python3) - LeetCode (Medium) : 1267. Count Servers that Communicate https://leetcode.com/problems/count-servers-that-communicate구현 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 행 길이 rows, 열 길이 cols, 정답 변수 can_communicate, 방문여부 배열 ck를 선언 후 적절히 초기화합니다.📔 풀이과정📑 grid의 원소를 순회현재 행에 대해 수평으로, 현재 열에 대해 수직으로 server개수를 세줍니다.📑 방문하지 않았고 통신 가능한 server 개수 세기세준 서버의 개수가 1개를 초과한다면 통신이 가능합니다.해당 조건을 만족한다면 다시 현재 행에 대해 수평으로, 현재 열에 대해 수직으로 방문하지 않은 server개수를 세주며 방문해줍니다.방문하지 않은 server 개수를.. (Python3) - LeetCode (Medium) : 1765. Map of Highest Peak https://leetcode.com/problems/map-of-highest-peakbfs로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 행 길이 rowLength📑 열 길이 colLength📑 인접 방향을 탐색할 배열 dr, dc 및 deque dq📑 순회를 마쳤을 때 배열 정답 변수 grid, 방문여부 ck📔 풀이과정📑 water인 지점에서 얼만큼 떨어져 있는지의 거리가 높이와 같으므로 bfs로 해결가능합니다. bfs함수를 구현합니다.📑 isWater를 이차원으로 순회하며 물인 지점을 먼저 방문하며 각 행,열을 먼저 순회하기 위해 dq에 append합니다.📑 dq에 대해 순회하며 인접한 좌표를 확인하며 범위를 넘지 않으며 방문하지 않았다면 이전 거.. (Python3) - LeetCode (Medium) : 2017. Grid Game https://leetcode.com/problems/grid-game누적합을 이용한 문제였습니다.📕 풀이방법📔 입력 및 초기화열 개수 colLength, 첫 번째와 두 번째 행의 누적합을 구할 prefix_row0, prefix_row1, 정답 변수 result를 선언 후 적절히 초기화합니다.📔 풀이과정📑 robot1의 역할:robot1은 게임에서 최대한 많은 점수를 가져가는 것이 목표입니다.하지만 단순히 점수를 많이 가져가는 것만이 아니라, robot2가 가져갈 점수를 최소화해야 합니다.따라서 robot1은 경로를 선택할 때 robot2가 가져갈 수 있는 점수의 최댓값을 최소화하는 방식으로 움직입니다.📑 robot2의 역할:robot2는 robot1이 지나간 후 남은 점수 중에서 최대한 많.. (Python3) - LeetCode (Medium) : 2683. Neighboring Bitwise XOR https://leetcode.com/problems/neighboring-bitwise-xorxor의 특성을 이용한 문제였습니다.📕 풀이방법📔 입력 및 초기화📑 derived의 xor한 결과를 저장할 xor_sum를 선언 후 0으로 초기화합니다.📔 풀이과정📑 derived 배열의 xor 특성`derived` 배열은 인접한 `original` 배열의 xor 결과로 정의됩니다:$$ derived[i] = original[i] \oplus original[(i+1) \mod n] $$derived 배열의 모든 값을 \(\oplus\)하면:$$ derived[0] \oplus derived[1] \oplus \dots \oplus derived[n-1] $$이를 original 배열로 치환하면: .. (Python3) - LeetCode (Medium) : 2425. Bitwise XOR of All Pairings https://leetcode.com/problems/bitwise-xor-of-all-pairingsxor의 특성에 대해 파악해 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 nums1의 xor을 저장할 xors1와 num2의 xor한 결과를 저장할 xors2를 선언해 각 배열들을 xor한 값을 각각 저장합니다.📑 nums1, nums2의 길이 len1, len2를 선언 후 저장합니다.📔 풀이과정📑 10만이 배열 최대 길이이므로 O(n^2)로 풀 수 없습니다. xor의 특성을 이용해야 합니다. 예제로 살펴보겠습니다. 숫자들을 알파뱃으로 바꿔 표현하면 여러 경우에 대해 다음과 같이 표현할 수 있습니다.1. nums1 = [a,b], nums2 = [c]인 경우 .. 이전 1 2 3 4 ··· 268 다음