[Leetcode/Medium] 자신을 제외한 배열의 곱 (LC 238. Product of Array Except Self, Swift)

https://leetcode.com/problems/product-of-array-except-self/description/ 🤔 문제 설명배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하세요.숫자의 접두사 또는 접미사의 곱은 32비트 정수에 들어맞는 것을 보장합니다. 단, 나눗셈을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.nums = [1,2,3,4]// [24, 12, 8, 6] 💡 풀이문제 가장 마지막줄에 나눗셈을 사용할 수 없다는 조건 때문에, 전체 곱을 구해두고 각 요소별로 자기 자신을 나누는 방법은 사용할 수가 없다. 그래서 결국은 누적 곱셈을 이용하는 풀이 방법을 생각했다.우선 입력 리스트 nums 길이에 맞는 re..

[Leetcode/Easy] 배열 파티션 1 (LC 561. Array Partition 1, Swift)

https://leetcode.com/problems/array-partition/description/ 🤔 문제 설명2n개의 정수 배열이 주어지면, n개의 묶음 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하세요.nums = [1,4,3,2]// 4 : min(1, 2) + min(3, 4) = 1 + 3 = 4 💡 풀이# 첫 번째 생각정말 단순하게 생각해보면, 입력받은 nums 배열을 정렬시킨 후 앞에서부터 두 쌍씩 페어를 시켜준 다음, 각 묶음에서 최소값들의 합을 구하면 올바른 답이 도출될 것이다.# 두 번째 생각하지만 생각해보면, 결국 min 함수를 적용하지 않고도 리스트를 정렬시켰다면 인덱스 값에 의해 값을 도출할 수 있다.nums[0], nums[2], nums[4]....값..

[Leetcode/Medium] 세 수의 합 (15. 3Sum, Swift)

https://leetcode.com/problems/3sum/description/ 🤔 문제 설명배열 nums를 입력받아 합으로 0을 만들 수 있는 3개의 요소를 출력하세요.단, 결과 배열에는 동일한 요소가 들어가지 않으며, 중복된 삼중항이 포함되어서는 안 됩니다. nums = [-1,0,1,2,-1,-4]// [[-1,-1,2],[-1,0,1]] 💡 풀이일단 바로 생각나는 것은 반복문 3개를 중첩해서 사용하는 방법이었다.물론 그렇게 해도 올바른 답은 나오겠지만, 그 뻔한 방법 말고 지난번 풀이에서 사용했던 투 포인터 방법을 사용해볼려고 했다.순차적으로 들어온 nums 배열을 반복하면서 값을 하나 빼두고(i) 나머지 뒤의 값을 대상으로 앞 뒤에 포인터를 두어서sum값에 따라 음수라면 왼쪽에 있는 포..

[Leetcode/Hard] 빗물 트래핑 (42. Trapping Rain Water, Swift)

https://leetcode.com/problems/trapping-rain-water/description/ 🤔 문제 설명각 막대의 너비가 1인 높이를 나타내는 음이 아닌 정수 리스트가 주어지면, 비가 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하세요.height = [0,1,0,2,1,0,1,3,2,1,2,1]// 6 💡 풀이예전 수학 문제에서 이와 비슷한 문제를 본 경험이 떠올랐다.문제를 해결하기 위해 생각한 방법은 두 가지였다.하나는 양끝 지점에서 최댓값을 유지하며 좁혀 들어오는 방법, 또 하나는 앞에서부터 쭉 최댓값을 유지하며 값을 채우는 방법나는 이 중에서 전자의 방법을 사용했다. 전문 용어로 이렇게 양 끝 지점에서 범위를 갈수록 줄이는 방법을 "투 포인터"라고 부른다.일단, 그전에 h..

[Leetcode/Medium] 가장 긴 팰린드롬 부분 문자열 (5. Longest Palindrome Substring, Swift)

https://leetcode.com/problems/longest-palindromic-substring/description/ 🤔 문제 설명가장 긴 팰린드롬(Palindrome) 부분 문자열을 출력하세요.팰린드롬에 대한 설명은 2024.06.27 - [Algorithm] - [Leetcode/Easy] 유효한 팰린드롬 (125. Valid Palindrome, Swift) 글 참조s = "babad"// "bab" 💡 처음 생각한 풀이와 코드 (Swift ver.)가장 긴 부분의 팰린드롬을 찾는 문제이기 때문에 문장 전체부터 시작해 길이를 하나씩 줄여가면서 팰린드롬을 확인하는 방식을 생각했다.문제의 예시로 나와있는 "babad"로 설명을 들어보자면, 문장의 길이(=5) 기준으로 처음에는 인덱스 0..

https://leetcode.com/problems/two-sum/description/ 🤔 문제 설명덧셈하여 타깃 숫자를 만들 수 있는 배열의 두 숫자 인덱스를 반환하세요.입력된 nums에는 정확히 하나의 답이 있다고 가정하며, 또한 동일한 요소를 두 번 사용하지 않는다고 가정합니다.답은 임의의 순서로 반환할 수 있습니다.[2,7,11,15], target = 9// [0,1] 🧑🏻‍💻 첫 번째 풀이와 코드 (Swift ver.)단순하게 중첩 반복을 사용하기보다, 한 번의 반복에서 한 값을 가지고 target-num으로 나머지 한 값을 찾는 방법을 생각했다.값은 array.firstIndex(of: target-num) 문법을 사용해서 찾을 수 있었고,자기 자신을 찾는 경우는 생략하기 위해 조..