알루 코딩

오늘은 어렵지 않습니다만, 삽질할 가능성이 있는 문제에 대해 다뤄보겠습니다. 이 문제는 알고리즘 복잡도와 효율적인 자료구조 사용에 대한 이해를 시험하는 좋은 연습이 될 것입니다. 해당 문제에서는 주어진 배열 nums 를 비우기 위해 필요한 최소 작업 횟수를 찾는 것입니다. 각 작업에서 nums 내의 똑같은 숫자를 제거할 수 있는데, (2개를 삭제하든지 3개를 삭제하든지) 둘 중 하나의 operation(연산)을 수행하면 서 nums 의 원소들을 제거하는 원리입니다. 최종적으로 nums 가 비워질 때까지 연산을 계속해서 하되, 최소의 연산으로 nums 를 비워야 하고, 이 때 이 최소의 연산 횟수를 반환하는 문제입니다. 제가 처음 접근한 방식은 각 숫자의 빈도수를 계산하여 동적 프로그래밍(DP)를 사용하는..

이 문제는 비교적 간단하지만, 간단하게 풀면 시간초과에 걸리기 때문에 조금은 생각을 해야 하는 문제입니다. 문제에서는 정렬된 정수 배열 nums가 주어집니다. 배열의 각 요소 'i' 에 대해, 해당 요소와 배열 내 다른 모든 요소 'j' 들과의 절대 차이인 |nums[i] - nums[j]| 의 합을 구하는 것이 목표입니다. 이 문제에서 각 원소를 순회하면서 절댓값 계산을 하면 nums의 길이가 10**5 까지 있기 때문에 시간초과가 날 수 밖에 없습니다. 이 문제를 효율적으로 해결하기 위해서는 누적합(prefix)와 역누적합(suffix)를 사용해야 합니다. 누적합(prefix sum)과 역누적합(suffix sum)의 사용은 꼭 알아야 하는 알고리즘 중에 하나입니다. prefix sum에 대해 잠시 ..

해당 문제 'Count Nice Pairs in an Array'는 nums 라는에서 'nice pair'의 수를 찾는 문제입니다. 배열 안의 두 숫자 'i'와 'j' ('i' < 'j') 가 'nice pair'로 간주될 때, "nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])" 이 성립해야 합니다. 여기서 rev(x)는 숫자 x의 자릿수를 반전시킨 결과입니다. 문제의 핵심은 각 숫자와 그 숫자의 반전된 형태의 차이를 이용하는 것입니다. 이 차이가 동일한 숫자들의 쌍이 'nice pair'를 형성합니다. 우선 코드부터 살펴보겠습니다. class Solution(object): def countNicePairs(self, nums): mod = 10 ** 9 + 7 ..

문제 설명부터 해보도록 하겠습니다. digits 이라는 숫자 문자열을 입력값으로 받는데요, 각 숫자 키패드에 해당하는 알파벳 문자열로 만들 수 있는 모든 문자열의 리스트를 출력하는 문제입니다. 예시 1을 보면, digits은 "23"으로 주어졌고, 각 숫자인 "2"에는 "abc"의 알파벳이, "3"에는 "def"의 알파벳이 주어져있습니다. 때문에, "23"으로 만들 수 있는 알파벳 문자열은 "ad"부터 "cf"까지 총 9가지가 될 수 있는 것을 알 수 있습니다. 여기서 캐치해야 할 점은 만들 수 있는 알파벳 문자열의 길이는 digits의 길이와 같을 수 밖에 없다는 점입니다. 흡사 순열과 조합 문제로 이해될 수 있는데, 보통 알고리즘 문제에서는 combination을 사용하거나 product, permu..

문제의 로직은 간단했습니다. 주어진 배열 nums에서 마크되지 않은 최소값을 더해가며 총 합을 출력하면 되는 문제였습니다. 여기서 마크되지 않았다는 것은 문제에서 주어진 예시를 보면 잘 이해가 될 것입니다. 쉬운 문제라고 생각했지만, 처음에는 풀지 못했습니다. 제가 처음에 풀었던 코드는 아래와 같습니다. class Solution: def findScore(self, nums: List[int]) -> int: res = 0 mark = [0 for _ in range(len(nums))] tmp = nums[:] while len(tmp)!=1: res += min(tmp) target = tmp.index(min(tmp)) print("index:",target,"min value:",min(tmp)..

한 번 문제를 이해해봅시다. 입력값으로 주어진 asteroids 배열은 소행성 배열입니다. 이 소행성은 양수값을 가질 수도 있고, 음수값을 가질 수도 있습니다. 양수값을 가진 소행성은 오른쪽으로 움직이고, 음수값을 가진 소행성은 왼쪽으로 움직입니다. 모든 소행성은 크기에 관계없이 같은 속도로 움직이기 때문에, 추월, 정지 등의 사건이 발생하지 않습니다. 두 소행성이 충돌했을 때는, 소행성의 크기의 절댓값에 따라서 소행성이 사라집니다. 예를 들어, '2'의 소행성과 '-5'의 소행성이 충돌했다면, '-5'의 소행성이 더 절댓값이 크기 때문에 '2'의 소행성이 없어지고, '-5'의 소행성은 계속해서 움직였던 방향대로 지나갑니다. 이 때, 두 소행성의 크기의 절댓값이 같다면, 두 소행성이 충돌했을 때는 두 소..

해당 문제는 팰린드롬 문제입니다. '팰린드롬'이라는 것은 문자열을 앞에서 읽나 뒤에서 읽나 동일한 문자열 형태를 띄는 문자열을 말하는데요, 'a'라는 단일문자도 팰린드롬에 속하는 것을 유의하면 됩니다. 이 문제에서는 주어진 문자열 s 에 들어있는 팰린드롬 문자열이 총 몇개인지 파악하는 문제입니다. 첫번째 예시에서 문자열 s는 'abc'인데, 각 단일문자만이 팰린드롬이고, 그 외에는 팰린드롬이 아니기에 결과를 3을 리턴합니다. 두번째 예시에서 문자열 s는 'aaa'인데, 결과가 6이 나왔습니다. 먼저 각 위치에서 'a'가 단일문자로서 팰린드롬을 형성하고, 첫번째,두번째 문자로 이루어진 'aa'와 두번째, 세번째 문자로 이루어진 'aa'가 총 2개 있습니다. 마지막으로 'aaa'도 팰린드롬 문자열이기에 결과..

이 문제를 처음봤을 때, 최장수열과 관련한 풀이가 떠올랐습니다. 최장수열은 대표적인 DP 유형의 문제로서 기억을 하고 있기에 보자마자 DP를 활용해보고자 했습니다. 이 문제의 핵심은 문자열 S를 순회하면서 반복되지 않는 문자를 가지는 문자열의 최대 길이를 반환하는 것입니다. 그렇다면, 순회를 할 때 계속해서 알아야 하는 값은 현재 위치에서 조건에 맞는 문자열을 만들 수 있는 최장길이 이전에 똑같은 문자가 나왔는지에 대한 여부 로 정리할 수 있겠습니다. 그럼, 바로 코드를 살펴보고, 코드 해석을 해보도록 하겠습니다. 코드는 아래와 같습니다. class Solution(object): def lengthOfLongestSubstring(self, s): if s == "": return 0 dp = [1] ..

이 문제를 푸는 것에 있어서 O(n^2)으로는 바로 풀 수 있겠지만, 결과적으로 시간초과가 나고, follow up을 보면, 공간복잡도를 O(1)로 풀기를 제안하고 있습니다. 처음에 제가 접근한 방식은 배열의 길이를 2배로 늘려서 [1,2,3,4] 가 인풋 배열이라면, [1,2,3,4,1,2,3,4] 로 만든 후, 1을 바라볼 때는, [2,3,4] 의 곱을 2를 바라볼 때는 [3,4,1], 3을 바라볼 때는 [4,1,2], 4를 바라볼 때는 [1,2,3] 을 곱해서 결과 배열을 만드려고 했습니다. 위와 같은 방식으로 문제를 풀 때, 많은 변수들이 필요했고, 파이썬의 for문을 돌면서, index를 다시 뒤로가도록 하는 것에 있어서 어려움을 겪었습니다. 결국, 저는 문제를 O(n)의 방식으로 30분만에 풀..