본문 바로가기
728x90
반응형

Leetcode47

162. Find Peak Element 어진 정수 배열에서 peak element를 찾는 문제입니다. Peak element는 해당 위치에서 좌우의 원소보다 큰 값을 갖는 원소를 의미합니다. 예를 들어, 배열 [1, 2, 3, 1]에서 3은 peak element입니다. 배열 [1, 2, 1, 3, 5, 6, 4]에서 6도 peak element입니다. 이 문제를 풀기 위한 일반적인 방법은 이진 검색(Binary Search)을 사용하는 것입니다. 이진 검색을 사용하면 O(log N)의 시간 복잡도로 peak element를 찾을 수 있습니다. public int FindPeakElement(int[] nums) { if (nums.Length == 0) { return -1; // 배열이 비어있는 경우 } // 배열의 길이가 1인 경우 if.. 2023. 11. 16.
160. Intersection of Two Linked Lists 두 개의 연결 리스트가 주어졌을 때, 두 리스트가 교차하는 지점을 찾는 문제입니다. 교차 지점이 없으면 null을 반환해야 합니다. List A: A1 → A2 ↘ C1 → C2 → C3 ↗ List B:B1 → B2 → B3 이 경우, 리스트 A와 리스트 B는 C1에서 교차하고, 이 지점이 교차 지점이 됩니다. 두 연결 리스트의 길이를 각각 계산합니다. 두 리스트의 길이 차이를 구하고, 길이가 더 긴 리스트의 포인터를 그 차이만큼 이동시킵니다. 이제 두 포인터를 동시에 이동시켜 교차 지점을 찾습니다. public class ListNode { public int val; public ListNode next; public ListNode(int val = 0, ListNode next = null) {.. 2023. 11. 15.
455. Assign Cookies 이 문제에서는 어떤 아이들이 존재하며, 각각의 아이들은 만족할 수 있는 최소한의 쿠키 크기를 가지고 있습니다. 또한, 쿠키들도 각각의 크기를 가지고 있습니다. 이 문제에서는 아이들에게 쿠키를 나눠주는 방법을 찾아야 합니다. 이때, 각 아이들은 최대 한 개의 쿠키만 받을 수 있습니다. 따라서, 가능한 많은 아이들에게 쿠키를 나눠주는 방법을 찾아야 합니다. 이 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다. public class Solution { public int FindContentChildren(int[] g, int[] s) { Array.Sort(g); Array.Sort(s); int i = 0; for (int j = 0; i < g.Length && j < s.Length; j++).. 2023. 11. 10.
144. Binary Tree Preorder Traversal 이진 트리를 전위 순회(preorder traversal)하는 방법을 구현하는 문제입니다. 문제 설명: 주어진 이진 트리를 전위 순회(preorder traversal)하는 방법은 다음과 같습니다: 루트 노드를 방문합니다. 왼쪽 서브트리를 전위 순회합니다. 오른쪽 서브트리를 전위 순회합니다. 전위 순회는 루트 노드를 가장 먼저 방문하고, 그 다음에 왼쪽 서브트리와 오른쪽 서브트리를 방문하는 순서입니다. 이 과정을 재귀적으로 수행하면 전체 이진 트리를 전위 순회할 수 있습니다. 예를 들어, 다음과 같은 이진 트리가 주어진 경우: 1 / \ 2 3 / \ 4 5 전위 순회(preorder traversal)는 다음과 같은 순서로 노드를 방문합니다: 1 -> 2 -> 4 -> 5 -> 3 이 문제를 해결하기 .. 2023. 11. 9.
389. Find the Difference 주어진 두 개의 문자열 s와 t에서 t에 추가된 한 문자를 찾는 문제입니다. 이 문제에서 s는 t에 랜덤하게 하나의 문자가 추가된 문자열입니다. 예를 들어, s = "abcd"와 t = "abcde"가 주어진 경우, t에 추가된 문자는 'e'입니다. 이 문제를 해결하는 일반적인 방법은 다음과 같습니다: 문자열 s와 t를 모두 순회하면서 각 문자의 등장 횟수를 카운트합니다. 이를 위해 두 개의 배열이나 딕셔너리를 사용할 수 있습니다. 두 문자열을 비교하면서 s에는 있지만 t에는 없는 문자를 찾습니다. 이 문자가 t에 추가된 문자입니다. public char FindTheDifference(string s, string t) { int[] count = new int[26]; foreach(char c in.. 2023. 11. 8.
367. Valid Perfect Square 주어진 양의 정수가 완전한 제곱수인지를 확인하는 문제입니다. 즉, 어떤 양의 정수 num이 주어질 때, 이 숫자가 다른 정수의 제곱으로 나타낼 수 있는지 여부를 판단해야 합니다. 예를 들어, 16은 4의 제곱으로 나타낼 수 있으므로 완전한 제곱수입니다. 반면에 14는 다른 정수의 제곱으로 나타낼 수 없으므로 완전한 제곱수가 아닙니다. 주어진 숫자 num이 1보다 작거나 같은 경우, true를 반환합니다. 왜냐하면 1은 이미 완전한 제곱수입니다. 이진 검색(binary search)을 사용하여 num의 제곱근을 찾습니다. 즉, num의 제곱근을 sqrt라고 했을 때, sqrt * sqrt가 num보다 크면 sqrt를 감소시키고, sqrt * sqrt가 num보다 작으면 sqrt를 증가시킵니다. 이 과정을 .. 2023. 11. 8.
350. Intersection of Two Arrays II 두 개의 정수 배열에서 중복된 원소들의 목록을 찾는 문제입니다. 이 문제에서는 중복된 원소를 모두 포함해야 합니다. 즉, 중복된 원소가 여러 번 나타날 수 있으며, 그만큼 결과 목록에도 여러 번 나타나야 합니다. 예를 들어, 두 배열 nums1 = [1, 2, 2, 1]과 nums2 = [2, 2]가 주어진 경우, 이 두 배열의 중복된 원소는 [2, 2]입니다. 이 문제를 해결하기 위한 일반적인 접근 방법은 다음과 같습니다: 하나의 배열을 Dictionary 또는 HashMap에 저장합니다. 이때, 배열의 각 원소를 키로 사용하고, 해당 원소의 빈도(나타난 횟수)를 값으로 저장합니다. 다른 배열을 순회하면서, 각 원소가 Dictionary에 이미 존재하면 빈도를 줄이고 결과 목록에 추가합니다. 빈도가 0.. 2023. 11. 7.
728x90
반응형

티스토리툴바