본문 바로가기

분류 전체보기

 (2341)
(Python3) - LeetCode (Medium) : 3152. Special Array II https://leetcode.com/problems/special-array-ii부분합으로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 어떤 그룹에 속해있는지 저장하기 위해 prefix_sum을 선언 후 nums의 길이만큼 초기화해줍니다.  같은 홀짝 쌍 누적 기록:prefix_sum 배열을 초기화하고, nums의 인접한 원소를 비교하여 홀짝이 같은 경우를 누적합니다.예: nums = [3, 4, 1, 2, 6]이라면 prefix_sum = [0, 0, 0, 0, 1]→ 인덱스 4에서 2와 6이 같은 홀짝이므로 prefix_sum[4] = 1 2. 정답을 저장할 빈 배열 answer를 초기화합니다.  📔 풀이과정 1. 각 쿼리에 대해, query[0]부터 query[1] 구간에서 같은 홀..
(Python3) - 백준(BOJ) 1939 : 중량 제한 https://www.acmicpc.net/problem/1939dijkstra를 max heap으로 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화노드 개수 n, 간선 개수 m, 양방향 그래프 graph, 시작점 start와 도착점 end를 선언 후 적절히 입력 및 초기화해줍니다.📔 풀이과정어떤 경로에 최소 제한이 곧 이동 가능한 물품의 최대 하중이 됩니다. 따라서 max heap을 사용해 가장 큰 제한을 가진 노드들만 선택해 방문하도록 dijkstra를 구현해줍니다.1. 노드를 탐색할 변수 max_heap , 각 노드별 최대 하중 max_weight 배열을 선언 후 적절히 초기화합니다. 2. python에는 따로 max heap이 없으므로 원소를 저장할때 음수형태로 저장후 꺼내서 비교할 때 ..
(Python3) - LeetCode (Medium) : 2054. Two Best Non-Overlapping Events https://leetcode.com/problems/two-best-non-overlapping-events/descriptiondp와 binary search 를 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화1. end_time에 대해 events를 오름차순으로 정렬합니다.  2. i번째 까지 event를 선택하거나 선택하지 않은 경우의 최댓값을 저장할 max_values_until_current_event를 선언 후 events길이만큼 저장해줍니다. 3. end_times를 따로 events에서 추출해 배열로 저장해줍니다.📔 풀이과정1. 이벤트 정렬: endTime 기준으로 정렬. 이렇게 하면 과거의 이벤트들 중 겹치지 않는 마지막 이벤트를 빠르게 찾을 수 있습니다.2. max_value..
(Python3) - LeetCode (Medium) : 1760. Minimum Limit of Balls in a Bag https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/이분 탐색 문제였습니다.📕 풀이방법📔 입력 및 초기화left, right를 선언해 각각 1, nums의 원소의 최댓값을 저장합니다.📔 풀이과정1. while left while left 이진 탐색에서 범위를 계속 좁혀가며 특정 값에 수렴할 때 사용하는 형태입니다. 반면, while left 정확히 값을 찾거나 특정 조건이 충족되는 순간 탐색을 종료하는 데 주로 사용됩니다.이 문제에서는 최적의 값을 찾기 위해 left와 right가 수렴하는 최종 지점까지 좁혀가야 합니다.left :예를 들어, mid = (left + right) // 2로 계산하고 범위를 조정할 때 left와 right의 ..
(Python3) - LeetCode (Medium) : 2337. Move Pieces to Obtain a String https://leetcode.com/problems/move-pieces-to-obtain-a-string문자열을 다뤄본 문제였습니다.📕 풀이방법📔 입력 및 초기화_는 이동할 수 있는 공간 즉, 비어 있으므로 고려할 필요 없습니다. 만들어야되는 'L', 'R'의 index를 함께 배열 start_idx_char, target_idx_char를 선언해 저장합니다.📔 풀이과정1. start_idx_char과 target_idx_char의 길이가 다르다면 이동해서 target을 만들 수 없으므로 False를 반환합니다. 2. 빈 공간을 제거했는데 start의 'L', 'R'배치와 target의 'L', 'R'배치의 순서가 다르다면 만들 수 없으므로 False를 반환합니다. 3. 같은 길이와 순서를 가진..
(Python3) - LeetCode (Medium) : 2825. Make String a Subsequence Using Cyclic Increments https://leetcode.com/problems/make-string-a-subsequence-using-cyclic-increments two pointer로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화str1의 index i와 str2의 index j를 선언 후 각각 0으로 초기화합니다.📔 풀이과정* 한번에 str1의 여러 index를 골라 다음 알파벳으로 바꿀 수 있습니다. 따라서 i, j를 옮기면서 만들 수 있는지 여부를 비교합니다.i가 str1의 길이 미만이면서 j도 str2의 길이 미만인 동안 while loop를 수행하며 다음을 진행합니다. 1. 현재 단어 c1, c2는 str1[i], str2[j]이므로 지역변수로 선언 후 각각 저장해줍니다. 2. c1이 c2와 같거나 c1..
(Python3) - LeetCode (Easy) : 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence https://leetcode.com/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/description📕 풀이방법📔 입력 및 초기화1. sentence를 선언 후 공백으로 문장을 나눠 split해줍니다. 📔 풀이과정1. sentence의 원소를 순회하며 searchWord가 접두어인 경우 해당 index + 1을 반환합니다.📔 정답 출력 | 반환-1을 반환합니다.📕 Code📔 Python3class Solution: def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: sentence = sentence.split(' ') ..
(Python3) - LeetCode (Easy) : 1971. Find if Path Exists in Graph https://leetcode.com/problems/find-if-path-exists-in-graph/BFS 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 삽입삭제에 O(1)이 걸리는 deque를 사용하기 위해 변수 dq, 방문 여부 판단을 위한 check배열, 인접리스트 형태로 간선을 저장할 edges_map을 선언 후 적절히 초기화합니다. 2. 인접리스트 만들 때 양 방향 그래프인 점 유의하며 넣어줍니다.📔 풀이과정1. 시작점은 source이므로 dq에 source를 넣어주고 방문처리해줍니다. 2. dq가 비어 있는 동안 원소를 pop해 destination인지 비교하고 맞다면 도착가능하므로 True를 바로 반환합니다. 아니라면 인접리스트에 방문 가능한 다음 node를 찾아 dq에 app..

티스토리툴바