본문 바로가기

코딩테스트

Leetcode 75 day22 (Successful Pairs of Spells and Potions, Find Peak Element, Total Cost to Hire K Workers) 힙 1문제, 이진 탐색 2문제를 풀었다. 이진 탐색처럼 보이지 않는 문제인데, 이진 탐색이 관련된 태그라서 좀 당황했었다. 그런데 풀어보니 진짜 이진 탐색이 맞더라.. 문제를 봤을 때 실마리가 안 잡히는 경우는 어떻게 하는 게 좋을까? 2300. Successful Pairs of Spells and Potions 양의 정수 배열 spells와 potions가 주어졌다. 배열의 크기는 각각 n, m이고 spells[i]는 i번째 스펠의 세기를 나타내고 potions[j]는 j번째 포션의 세기를 나타낸다. success라는 정수값이 주어졌을 때, 스펠과 포션 쌍의 곱이 success보다 크거나 같을 때 성공적이다(successful)고 한다. pairs[i]는 i번째 스펠이 성공적인 쌍을 형성하는 개수를 .. 더보기
Leetcode 75 day21 (Maximum Subsequence Score, Evaluate Division, Reorder Routes to Make All Paths Lead to the City Zero) Heap 1문제, DFS 2문제를 풀었다. 문제가 어려워지면서 푸는 데에 시간이 들기도 하고 답을 유추하는 과정이 복잡해지니 포스팅도 소홀해지기 시작했다... 😅 그리고 문제를 풀고 몰아서 포스팅을 쓰려고 하니까 어떻게 풀었는지 기억나지 않는 경우도 많은 것 같다. 문제를 풀 때 어떤 아이디어로 접근했는지 기록해 두면 다시 봤을 때 도움이 될 것 같다. 2542. Maximum Subsequence Score 길이가 n인 배열 num1, num2가 주어지고, 양수 k가 주어졌다. num1 배열에서 k 개의 인덱스를 선택했을 때, 스코어는 선택된 nums1의 요소 합 * nums2의 선택된 요소 중 최소값이다. 이 스코어의 최댓값을 구하라. You are given two 0-indexed integer .. 더보기
Leetcode 75 day20 (Determine if Two Strings Are Close, Decode String, Dota2 Senate) 휴가를 다녀와서 오랜만에 풀어보는 코딩 문제들.. 그래도 푹 쉬고 와서인지 나름 수월하게 풀린 것 같다. 해쉬 맵, 스택, 큐 사이좋게 한 문제씩 풀어봤다. 1657. Determine if Two Strings Are Close 주어진 두 문자열은 다음 두 명령으로 하나에서 다른 하나를 얻을 수 있다면 '가깝다'고 할 수 있다. 명령 1: 존재하는 두 문자열을 서로 바꿔치기한다. 명령 2: 단어에 출현한 하나의 문자 모두를 다른 하나의 문자 모두로 바꾼다. 예를 들어 a 모두를 b로 바꾸고, b를 모두 a로 바꾼다. 위 두 명령을 필요한 만큼 수행할 수 있다고 할 때, word1과 word2과 '가깝다'면 true, 그렇지 않으면 false를 리턴하라. Two strings are considered .. 더보기
Leetcode 75 day19 (Sliding Window 3문제) 휴가 중에 잠시 짬을 내서 풀어보는 리트코드 75 문제… 19일째 연속 포스팅인데 내일이 고비가 될 것 같다. 더 이상은 문제를 봐도 감이 오지 않기 때문에..😅 슬라이딩 윈도 3 문제를 풀어봤는데, 두 번째, 세 번째 문제는 거의 같은 문제라고 봐도 될 거 같았다. 1456. Maximum Number of Vowels in a Substring of Given Length 주어진 문자열 s와 정수 k가 있을 때, 길이가 k인 s의 부분 문자열 중 모음 개수를 가장 많이 가지는 경우를 구하라. Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k. 내가 .. 더보기
Leetcode 75 day18 (Path Sum III, Lowest Common Ancestor of a Binary Tree, Longest ZigZag Path in a Binary Tree) 리트코드 75 18일 차, 이제 일주일치(21개) 남았는데, 여름휴가를 즐기는 중이다. 비행기, 숙소 예약까지 이미 끝난 거라 마음이 심란하지만 힐링한다고 생각하고 일정대로 가기로 했다. 이 포스팅은 예약 발행될 예정이다. 여행 가기 전에 일주일 치 포스팅을 미리 해놓으면 좋을 텐데, 아마 힘들 것 같다. 😂 이진트리 문제를 3개 풀어봤다. 437. Path Sum III 주어진 이진트리 root와 정수 targetSum이 있을 때, 경로를 따르는 노드 값들의 합이 targetSum이 되는 경로의 수를 구하라. 경로는 시작 또는 끝이 루트 노드이거나 리프 노드일 필요는 없지만 항상 아래 방향(부모 노드에서 자식 노드 방향으로)으로 가야 한다. Given the root of a binary tree an.. 더보기
Leetcode 75 day17 (Product of Array Except Self, Increasing Triplet Subsequence, Combination Sum III) 리트코드 75 17일 차, Array/String 문제 2문제, Backtracking 문제를 한 문제 풀었다. 배열 문제들은 아무리 생각해도 풀 수가 없어서 솔루션을 봤다. 수능 4점짜리 문제를 푸는 기분이랄까? 문제를 풀 수 있는 아이디어가 안 떠오르고 심지어는 솔루션을 봐도 이해가 안 되는 문제가 있다. 이런 문제들은 앞으로 어떻게 연습해야 할지 고민이 된다. 238. Product of Array Except Self 주어진 정수 배열 nums에 대해서 answer[i]는 nums[i]를 제외한 모든 nums의 곱인 answer 배열을 리턴하라. nums의 곱은 모두 32비트 정수임을 보장한다. 나누기를 사용하지 않고 O(n) 시간 복잡도 안에 동작하는 알고리즘을 작성하라. Given an int.. 더보기
Leetcode 75 day16 (Maximum Level Sum of a Binary Tree, Delete Node in a BST, Letter Combinations of a Phone Number) 리트코드 75 16일 차. 이진트리 1문제, BST 1문제, 백트래킹 1문제를 풀었다. 벌써 2주가 지났다. 48문제를 푼 건데 남은 27문제는 혼자서는 도저히 안 풀릴 것 같은 문제들이다 😢 각 잡고 30분 동안 풀어보고, 못 풀면 해답 보고 풀이를 이해하는 식으로 공부해보려고 한다. 1161. Maximum Level Sum of a Binary Tree 주어진 이진 트리에서 루트를 레벨 1, 그다음 자식 노드들을 레벨 2, 3...으로 정의할 때 각 레벨의 모든 노드 값의 합이 최대가 되는 가장 작은 레벨을 구하라. Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on... 더보기
Leetcode 75 day15 (Odd Even Linked List, Maximum Twin Sum of a Linked List, Count Good Nodes in Binary Tree) 리트코드 75 15일 차, 링크드 리스트 2문제, 이진트리 순회 1문제를 풀어봤다. 포인터를 활용하는 문제는 언제 풀어도 헷갈리는 면이 있어서 손으로 한번 검증해 보는 게 좋은 것 같다. 328. Odd Even Linked List Linked list의 head가 주어졌을 때 홀수번째 노드들을 묶고 그 다음에 짝수번째 노드들을 묶은 순서로 바꿔서 리턴하라. 솔루션의 시간 복잡도는 O(n), 공간 복잡도는 O(1) 이 돼야 한다. Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered li.. 더보기

티스토리툴바