In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5 Output: 2 Explanation: Starting with nums = [1,2,3,4]:

• Remove numbers 1 and 4, then nums = [2,3]
• Remove numbers 2 and 3, then nums = [] There are no more pairs that sum up to 5, hence a total of 2 operations. Example 2:

Input: nums = [3,1,3,4,3], k = 6 Output: 1 Explanation: Starting with nums = [3,1,3,4,3]:

• Remove the first two 3's, then nums = [1,4,3] There are no more pairs that sum up to 6, hence a total of 1 operation.

투포인터를 쓰면서 하는 거다. 알아두어야할 것은 처음에 sort()를 해줘야지 투포인터가 효율적으로 작동한다는 것이다. 하지않으면 edge case에서 걸린다 (예: [4,4,1,3,1,3,2,2,5,5,1,5,2,1,2,3,5,4]).

풀 수 있었던 거였는데 operation 숫자 늘리는 게 갑자기 생각 안 나서 멍 때리다가 답지보고 알아냄 🤦

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        operation = 0

        while left < right:
            if nums[left] + nums[right] == k:
                operation += 1
                left += 1
                right -= 1
            elif nums[left] + nums[right] < k:
                left += 1
            else:
                right -= 1

        return operation

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

example1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

투포인터를 써서 하는 거는 알았는데 이걸 어떻게 하는 건가 싶었는데 말 그대로 while 루프를 사용해서 각 포인터에서 넓이를 계산해서 그 중에 가장 큰 넓이를 갖고 있는 걸 계산하는 거였다.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height) # the number of heights
        left = 0
        right = len(height) - 1
        max_area = 0

        while left < right:
            width = right - left
            h = min(height[left], height[right])
            current_area = width * h
            max_area = max(max_area, current_area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

        # Time O(n)
        # Space O(1)

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc" Output: true Example 2:

Input: s = "axc", t = "ahbgdc" Output: false

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

투포인터 쓰는 거는 알았는데 s와 t를 어떻게 비교하면서 하는 지가 당최 떠오르지가 않았다 ㅠ..생각보다 간단한 구현이어서 오늘도 나의 모자람과 멍충함을 께달음.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0] Example 2:

Input: nums = [0] Output: [0]

Constraints:

1 <= nums.length <= 104 -231 <= nums[i] <= 231 - 1

투포인터를 쓰는 건데, 이전에 했던 것처럼 left, right = 0, len(input)-1 같은 게 아니라 left만 0으로 initialize해서 풀어야한다. 않이 투포인터가 이렇게도 쓸 수도 있는 거구나...정형화 시키지 말자. 투포인터란 말 그대로 어떤 테크닉이지 그것의 implementation 코드 또한 정형화된 게 아니란 걸 잊지 말자.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0

        for right in range(len(nums)):
            if nums[right] != 0:
                nums[right], nums[left] = nums[left], nums[right]
                left += 1

        return nums

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s. Otherwise, append the character followed by the group's length. The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3". Example 2:

Input: chars = ["a"] Output: Return 1, and the first character of the input array should be: ["a"] Explanation: The only group is "a", which remains uncompressed since it's a single character. Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"]. Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

처음에 아래처럼 이거 딕셔너리로 해야하나 싶어서 썼는데 되는 줄 알았는데 전혀 아니었다..

class Solution:
    def compress(self, chars: List[str]) -> int:
        dictoutput = {}

        for char in chars:
            if char not in dictoutput:
                dictoutput[char] = 0
            dictoutput[char] += 1

        compressed = len("".join(f'{k}{v}' for k, v in dictoutput.items()))

이건 결과는 내지만 3가지 문제가 있다.

1. compression 방식이 잘못됐다. 기존에 쓴 코드는 주어진 input 리스트에 있는 원소들을 세는 방식으로 해서 딕셔너리에 추가하는 방식이었는데, 문제에서는 consecutive한 문자들만을 compression하는 걸 요구했다. 즉, 내가 쓴 거는 각각의 문자들을 전역적으로 빈도를 계산해서 {"a":2, "b":2, "c":3}를 얻어내는 거지만, 사실 문제에서 제시하는 조건을 따르면 "a2b2c3"와 같은 방식으로 compress해야한다는 거다.
2. 문자들을 리턴하는 방식이 잘못됨. 문제에서는 compressed된 '리스트'의 길이를 리턴하라고 하고있지, '문자열'의 길이나 기존에 내가 쓴 코드와 같이 딕셔너리로 재구성한 다음에 전역적으로 문자들의 빈도수 계산하여 얻은 길이를 리턴하라고 하고있지 않다.

솔루션은 다음과 같다.

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0  # Pointer to track where to write in chars
        read = 0   # Pointer to read through chars

        while read < len(chars):
            char = chars[read]  # Step 1
            count = 0

            # Step 2: Count the occurrences of the current character
            while read < len(chars) and chars[read] == char:
                read += 1
                count += 1

            # Step 3: Write the character to chars
            chars[write] = char
            write += 1

            # Step 4: Write the count to chars if greater than 1
            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1

        # Step 5: The length of the compressed list is the final value of write
        return write

최초에는 write와 read를 가리키는 두 개의 포인터를 선언해준다. 그 다음 while 루프를 이용해서 input 리스트 내 원소를 처음부터 쭉 읽어나가면서 더 이상 동일한 원소가 읽히지 않는다면 동일한 원소가 나온 것 만큼 숫자를 마지막으로 센 원소에다가 write하고 ([a, a, b, b, b] 이러면 [a, 2, b, b, b] 이런 식으로), 최종적으로 write를 가리키는 포인터의 포지션이 어디에 있는지를 갖고 리턴을 하는 거다.

참고로 while과 for-loop의 차이점을 다시 복기하자면, 전자는 특정한 몇 번을 진행하든지 간에 특정한 조건을 만족할 때까지 루프를 돌리는 거고, for는 어떤 객체가 주어졌을 때 거기에 있는 원소들의 갯수만큼 특정 조건에 맞게 루프를 돌리는 거다.

Example 1:

Input: nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid. Example 2:

Input: nums = [5,4,3,2,1] Output: false Explanation: No triplet exists. Example 3:

Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

전혀 좋지 않았던 내 풀이시도. 투포인터를 이용하려고 했지만 결국 막혔다.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        left, right = 0, len(nums) - 1
        output = []

        while left < right:
            if nums[left] < nums[right]:
                output.append(nums[right])
                left += 1

            if nums[left] > nums[right]:
                output.append(nums[left])
                right -= 1

            # put the elment of the list nums that is in the middle position of the list into ouput?
            # output is constrained to have three elements

        if output[0] < output[1] < ouput[2]:
            True
        else:
            False

모범답안은 다음과 같다

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = second = float('inf')

        for num in nums:
            if num <= first:
                first = num  # smallest so far
            elif num <= second:
                second = num  # second smallest so far
            else:
                # If we find a number greater than both first and second,
                # we have an increasing triplet
                return True

        return False  # no increasing triplet found

가장 작은 숫자(=first)와 그 다음 작은 숫자(=second)를 설정하는 것에서부터 아이디어가 시작하는데, 최초 initialization은 float('inf') 설정한다는 아이디어가 꽤나 낯설면서도 신기했다. 이게 이렇게도 할 수가 있겠구나 싶었다. elif문의 경우 num이 first보단 크지만 second보다 작거나 같은 경우에 second를 update를 하는 것을 의미하며, 마지막 else에서는 num이 first와 second보다 큰 경우를 지칭한다. 흠 이게 이렇게 암시적인 느낌으로 코딩할 수가 있구나...좀 신기하다.

아래는 예시.

Example Walkthrough Let's see how this approach works on an example:

Example Input: nums = [2, 1, 5, 0, 4, 6]

first = inf, second = inf

We start iterating: num = 2: 2 is smaller than first, so we set first = 2. num = 1: 1 is smaller than first, so we set first = 1. num = 5: 5 is greater than first but smaller than second, so we set second = 5. num = 0: 0 is smaller than first, so we set first = 0. num = 4: 4 is greater than first but smaller than second, so we set second = 4. num = 6: 6 is greater than both first and second, so we return True (we found the triplet 0, 4, 6).

1. Passes (Left Pass and Right Pass)

A pass refers to going through the array or list one time from start to finish (or vice versa) to gather or calculate information. In the "Product of Array Except Self" problem, we used two passes (one left-to-right and one right-to-left) to accumulate the products of elements to the left and right of each index.

• Left Pass: Start from the beginning and move to the end, computing cumulative information for each element as you go (like the product of all elements to the left).
• Right Pass: Start from the end and move to the beginning, calculating cumulative information from the opposite direction.

Each pass processes the array independently, often resulting in simpler code that doesn’t need additional logic for managing multiple pointers or indices simultaneously.

2. Pointers (Two-Pointer Technique)

The two-pointer technique involves using two indices (or "pointers") that usually start from opposite ends of the array and move toward each other (or in specific directions). This is helpful when you need to compare or process elements at both ends, like finding pairs, reversing an array, or partitioning based on conditions.

• Pointers Example: For reversing vowels in a string, you can use two pointers:
  • One pointer starts at the beginning of the string (left), and the other starts at the end (right).
  • The pointers move toward each other, swapping vowels whenever they encounter them.

Key Differences

When to Use Each

• Passes are ideal when you need cumulative information about each element independently.
• Pointers work well for problems involving pairs, symmetry, or where elements interact across the array.

In short, passes are about covering the array in phases, while pointers involve coordinating two elements at once for comparison or processing.

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6] Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)

        # Initialize the output array with 1s
        output = [1] * length

        # Left pass: calculate the product of all elements to the left of each index
        left_product = 1
        for i in range(length):
            output[i] = left_product
            left_product *= nums[i]  # Update left_product to include nums[i]

        # Right pass: calculate the product of all elements to the right of each index
        right_product = 1
        for i in range(length - 1, -1, -1):
            output[i] *= right_product  # Multiply with the accumulated right product
            right_product *= nums[i]  # Update right_product to include nums[i]

        return output

포인터를 쓰는 줄 알았는데 뭔가 좀 안되는 것 같아서 흠 어쩌지 하다가 결국 솔루션을 봤는데 pass란 걸 써서 하게 된다는 걸 알게 됐다. 두 개가 뭔 차인가 싶었는데 간단하게 말하면. pass의 경우 cumulative한 동작들을 수행할 때, 특히 array나 list를 갖고 쭈르륵할 때 사용되고, 포인터의 경우 인덱스를 갖고서 (투포인터라면 리스트의 양끝에서) 서로가 만나는 지점까지 가거나 어느 특정한 요소를 타겟해서 무언가 계산을 수행할 때 사용된다.

흠 몰랐던 거여서 아쉬운 점도 있지만 이런 방식으로도 계산을 할수 있다란 점에서 좀 재밌었음.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue" Output: "blue is sky the" Example 2:

Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces. Example 3:

Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

투 포인터를 써서 하는 법:

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        left, right = 0, len(words) - 1

        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1

        return " ".join(words) 

파이썬(또는 자바)에서 먹히는 방법

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))

처음엔 정규표현식 써야하나 싶어서 뭔가 좀 막막했는데 하 저 split()이랑 reversed()가 생각이 안 나서 못 풀었음..으아 평소에 코딩을 하자.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

Input: s = "IceCreAm"

Output: "AceCreIm"

Explanation:

The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".

Example 2:

Input: s = "leetcode"

Output: "leotcede"

Constraints:

1 <= s.length <= 3 * 105 s consist of printable ASCII characters.

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
        s = list(s)  # Convert string to a list for easy manipulation
        left, right = 0, len(s) - 1

        while left < right:
            # Move left pointer to the right until it finds a vowel
            while left < right and s[left] not in vowels:
                left += 1
            # Move right pointer to the left until it finds a vowel
            while left < right and s[right] not in vowels:
                right -= 1
            # Swap the vowels
            if left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1

        return ''.join(s)  # Convert list back to string

easy래매...로직이 하나 떠오르긴 했는데 이게 가능은하겠지만 굉장히 복잡해질 것 같아서 흠 뭐지 좀 고민하다가 결국 답을 봤는데 투포인터를 쓰는 거였다. 떠올리지 못해서 좀 아쉬웠지만 이런 경우엔 투포인터 쓴다는 걸 깨달았으니 만족. 참고로 len() 함수는 상기 겸 쓰는 건데 스트링의 경우 character의 갯수(=길이)를 세는 거지만 포인터를 사용할 때는 갯수가 아니라 index를 사용하기 때문에 주어진 스트링의 마지막 캐릭터를 지칭할 때는 len(s) -1 로 선언해야한다. 즉, 'hello'가 있을 때 len()은 5지만, 포인터의 입장에선 길이가 아니라 index를 지칭하는 것이고, 파이썬의 index는 0부터 시작하기 때문에 포인터가 스트링의 가장 왼쪽을 지칭할 때는 0부터 시작하고, 반대로 가장 오른쪽부터 지칭할 때는 len(s) - 1로 선언해야한다. 잊지 말자.

swap the vowels의 과정은 다음과 같다.

First Loop (left < right):

s[left] = 'h' (not a vowel), so move left rightward.

Update: left = 1 (points to 'e').

s[right] = 'o' (vowel), so right pointer doesn’t move.

Swap: Now s[left] ('e') and s[right] ('o') are both vowels, so we swap them.

After swap: s = ['h', 'o', 'l', 'l', 'e']

Move both pointers inward:

left = 2 (points to 'l') right = 3 (points to 'l')

** Second Loop (left < right):**

s[left] = 'l' (not a vowel), so move left rightward. Update: left = 3 s[right] = 'l' (not a vowel), so move right leftward. Update: right = 2

End Condition:

Now left >= right (left = 3, right = 2), so the loop ends.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: true Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2 Output: false

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        f = [0] + flowerbed + [0] # explicitly assume that there are 0s left/right-outside of flowerbed list

        for i in range(1, len(f) - 1): # skip first and last
            if f[i - 1] == 0 and f[i] == 0 and f[i + 1] == 0: # check left, target, and right
                f[i] = 1 # plat a flower
                n -= 1 # decrement the number of flowers remaining to be planted (remaining 되는 방식으로 된다는 거 잊지 말기)
        return n <= 0
        # After iterating through all plots, check if the number of flowers remaining to be planted (n) is less than or equal to 0. If so, return True, indicating that all flowers have been successfully planted without violating the adjacency rule. Otherwise, return False.

뭔가 포인터를 쓰는 것 같았는데 정확히 로직을 어떻게 짜야할지 몰라 결국 못 풀고 답안지를 봤다. easy래매...여튼 재밌던 점은 첫번째로 먼저 flowerbed 리스트에다가 양 옆으로 0이라고 함으로써 명시적으로 가정을 시키는 거였고 (첫번째 라인), 포인터를 사용하는 방식 (왼쪽, 심으려는 꽃 위치, 오른쪽)을 쓰는 법이었고 (if-clause)이었고, 제일 중요한 부분이었던 꽃을 한 번에 다 심는 게 아니라 for-loop 안에서 꽃 하나를 심는데 성공하면 꽃을 심으려는 n개를 한 개씩 줄이는 부분이었다 (n -= 1 부분).

그리고 리턴을 저런 식으로 선언함으로써 True or False를 얻어내는 방식이 있다는 걸 다시 상기시켰다.

Return a boolean array result of length n, where result[i] is true if, after giving the $$i^{th}$$ kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3 Output: [true,true,true,false,true] Explanation: If you give all extraCandies to:

• Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
• Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
• Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
• Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
• Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids. Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1 Output: [true,false,false,false,false] Explanation: There is only 1 extra candy. Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy. Example 3:

Input: candies = [12,1,12], extraCandies = 10 Output: [true,false,true]

풀이

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        output = []
        max_candies = max(candies)

        for i in candies:
            if i + extraCandies >= max_candies:
                output.append(True)
            else:
                output.append(False)

        return output

모범답안이랑 굉장히 근접하게 써서 좋았다. 다만 처음엔 루프 안에서 max(candies)를 적었는데 그렇게하면 매번 candies라는 리스트 안에서 재계산을 하는 수고가 들기 때문에 처음부터 max_candies라는 변수를 만들어 미리 저장해놓고 하는 방식으로 하는 것이 효율적인 걸 알게 되어 저렇게 수정했다.

Return the merged string.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        # create an empty list to store merged characters
        merged = []

        for i, j in zip(word1, word2): # loop to iterate each characters in word1 and word2 
            merged.append(i + j) # append each pair of the characters

        merged.append(word1[len(word2):]) # in case word1 is longer than word2
        merged.append(word2[len(word1):]) # and vice versa

        return "".join(merged) # join each elment in the merged list

Time complexity: O(n + m) Space complexity: O(n + m)

1. 먼저 merge되는 문자들을 저장하는 리스트를 만든다.
2. zip 함수를 이용해서 string으로 구성된 word1, word2의 각 문자들을 짝으로 (ex. "a p", "b q") 불러와 최대한 itration 시킨다. 남는 건 버림. (word1이 word2보다 길어서 word1에 a와 b를 부르고 c, d가 남았다면 안 쓰고 내비둠) 2-1. 불러온 짝은 merged에다가 +(=서로 concatenate) 시켜서 "ap", "bq" 꼴로 추가시켜준다.
3. word1이 word2보다 길 경우, slicing을 이용한다. 예컨대 word1이 abcd고 word2가 pq라면 word1[len(word2):]은 word1[2:]이고, 이는 cd에 접근하는 것이며 따라서 이 cd를 merged에다가 추가 시킨다. 따라서 merged는 ["ap", "bq", "cd"]가 될 것이다. 3-1. 만약 word1가 word2와 길이가 짧거나 같으면 empty string을 append 할 거다.
4. 요건 반대로 word2가 word1보다 길이가 긴 경우다.
5. 3혹은 4를 처리한 후, prefix를 ""로 하면서 merged 리스트 안에 있는 각 원소들을 join 시켜 리턴한다. 3번 과정을 예를 든다면 결국 apbqcd가 될 것이다.

역시나 못 풀었던 문제였다. 로직은 짰는데 사실상 brute-force식이었는데 그마저도 어떻게 구현해야할지 감이 도저히 안 와서 좌절했었는데, 원체 어려운 문제였다. 왜냐하면 dynamic programming(DP) 관련 문제였기 때문. 하지만 뭔가 굉장히 많이 배운 문제였는데, 솔루션이 다양해 분석하는 맛이 있었기 때문이었다. 코드가 어떻게 굴러가는지에 대해서도 잘못알고 있던 게 있어서 배운 게 많았음. 아래 솔루션들은 가장 많은 호응을 받은 포스트에서 긁어온 거다.

솔루션 1: Brute force

아이디어(혹은 직관) → 시작점과 끝지점을 모두 하나하나 체크하면서 substring이 회문인지 아닌지 체크

• 알고리즘

1. 리스트로 구성된 substring의 시작 인덱스를 선택하며, 이는 0부터 n-2까지의 모든 인덱스다.
2. 마찬가지로 리스트로 구성된 substring의 마지막 인덱스를선택하며, 이는 i+1부터 n-1까지의 인덱스다.
3. i번째 인덱스부터 j번째까지의 substring이 회문인지 확인한다.
4. 3번 단계에서 참을 얻고 해당 substring의 길이가 기존 설정한 길이보다 길다면, 최대 길이 변수와 최대 길이 substring을 업데이트한다.
5. 최대 길이(=가장 긴 or longest) substring을 출력한다.

• 구현

  class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1: # 회문 자체를 얻어낼 수 없는 경우엔 s로 리턴. 길이가 1보다 작거나 같으면 회문이 안됨.
            return s
  
        Max_Len = 1
        Max_Str = s[0]
        for i in range(len(s)-1): # step 1 cf. (range(n)) = (0, n-1)    
            for j in range(i+1, len(s)): # step 2 cf. (range(x, y)) = ((x, y-1))
                if j-1+1 > Max_Len and s[i:j+1] == s[i:j+1][::-1]: # step 3
                    Max_Len = j-i+1
                    Max_Str = s[i:j+1]
  
        return Max_Str

솔루션 2: Expand around center

아이디어(혹은 직관) → Two-pointer가 있고 얘네들이 string의 중앙을 중심으로 확장하는 방식.

• 접근법

1. 회문은 기본적으로 중앙을 중심으로 양쪽의 문자들이 거울처럼 바라보는 것임. 따라서 회문은 중앙에서부터 확장되며, 그러한 중앙의 갯수는 2n-1개.
2. 왜 2n-1개인가? 그냥 n개의 중앙이 아니라? 왜냐하면 회문의 중심이 두 개의 문자 사이에 있을 수 있기 때문임. 그런 회문은 짝수 갯수의 문자를 갖고 있고 (ex. "abba") 그 중심은 두 개의 'b' 사이인 경우임.

• 알고리즘

1. 시작점에서 max_str = s[0], max_len = 1로 설정하는데 원론적으로 모든 개개의 문자 그 자체는 회문이기 때문임.
2. 주어진 스트링에 대해서 계속 반복적으로 처리하면서 모든 문자에 대해서 중앙을 중심으로 확장함.
3. 홀수 길이의 회문에 대해선 현재 포인팅이 된 문자를 중앙으로 간주하고 이를 중심으로 확장.
4. 짝수 길이의 회문에 대해선 현재 포인팅이 된 문자와 그 다음 문자를 중앙으로 간주하고 이를 중심으로 확장.
5. 그러면서 최대 길이와 최대 길이의 substring 추적.
6. 가장 긴 회문을 찾으면 출력함.

• 구현

  class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
  
        def expand_from_center(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]
  
        max_str = s[0]
  
        for i in range(len(s) - 1):
            odd = expand_from_center(i, i)
            even = expand_from_center(i, i + 1)
  
            if len(odd) > len(max_str):
                max_str = odd
            if len(even) > len(max_str):
                max_str = even
  
        return max_str

솔루션 3: Dynamic Programming 아이디어(혹은 직관) → 일종의 Table을 만들어서 그 안에서 계산하면서 True가 뜰 때 마다 회문인 걸 확인하고선 저장하는 방식..위에 두 개도 좋긴한데 이게 나한텐 더 직관적임.

• 알고리즘 (작성중)

• 구현

  class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
  
        Max_Len=1
        Max_Str=s[0]
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = True
            for j in range(i):
                if s[j] == s[i] and (i-j <= 2 or dp[j+1][i-1]):
                    dp[j][i] = True
                    if i-j+1 > Max_Len:
                        Max_Len = i-j+1
                        Max_Str = s[j:i+1]
        return Max_Str

끝.

• 공통점 1) 리스트를 정렬한다. 2) key와 reverse라는 매개변수가 있으며, key의 경우 예컨대 str.lower 이렇게 되어있으면 대소문자 구분없이 정렬하며, reverse의 경우 True로 설정하면 내림차순으로 정렬한다.

• 차이점 sort() 1) 다음과 같은 꼴로 사용: variable.sort() 2) 제자리 정렬(In-place Sort)라 하며 입력을 출력으로 덮어써 별도의 추가공간을 요구하지 않아 리턴값이 없다. 따라서 x = y.sort()와 같은 방식으로 변수를 지정하면 None을 리턴한다. 3) 리스트에다가만 쓸 수 있다! sorted() 1) 다음과 같은 꼴로 사용: sorted(variable) 2) 리스트, 튜플, 딕셔너리, 셋(set), 스트링, range()에서 얻을 수 있는 Iterable한 객체에다가도 쓸 수 있다. 3) 그러나 리턴값은 항상 리스트형이다!

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

내가 푼 것

-> 못품 ㅠㅠㅠㅠㅠ 주석으로 로직은 맞게 썼는데 함수를 뭘 써야하는지 도저히 생각이 안났음 ㅠㅠ 실제로도 모르는 거였음...그래도 풀 죽지말고 하자!

솔루션

import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list)

        for word in strs:
            anagrams[''.join(sorted(word))].append(word) 

        return list(anagrams.values())

알아둘 것은 다음과 같다.

1. join() 기본적으로 리스트와 같은 iterable한 것들을 선형적으로 이어붙이는(concatenate) 함수. 여기서 prefix는 이어붙일 때 그 사이에 뭘 넣어서 할 것이냐를 지칭한다. 예컨대 어떤 리스트가 ['a', 'b', 'c']로 되어있을 때, prefix가 ''(=empty string)이면 'abc'가 되고, 'd'이면 'adbdc'로 합쳐지는 거다.

2. sorted() (vs sort()) 정렬 함수인데, 이건 좀 중요하고 동시에 헷갈리는 거라서 따로 쓴 포스틀 보자.

3. for 루프는 도대체 어떻게 돌아가는가? 지금껏 딕셔너리의 key에 뭘 추가 시키는 건 dictionary[key] = 0 뭐 이런 것만 해봤지 저런 식으로 하는 건 한 번도 본적이 없다. 처음엔 그래서 이 부분 이해하는 게 시간이 걸렸다. 특히나 이게 어떻게 anagram들 끼리만 모으는지가 이해가 안 갔음...예시를 들어서 보니깐 훨씬 더 이해가 빨랐다. 과정은 다음과 같다. 다음과 같은 리스트가 있다고 치자.

   strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

   for 루프의 첫번째 iteration (word = "eat"인 경우)는 다음과 같다.

   • sorted(word)에서 "eat"를 ['a', 'e', 't']로 정렬
   • ''.join(sorted(word))를 통해 정렬된 각 문자를 "aet"로 이어붙임.
   • anagrams["aet"].append("eat")가 anagrams에서 "aet"라는 key에다가 "eat"을 list로 이루어진 value에다가 추가시킨다. (최초에 angrams를 정의할 때 list가 되어있는 걸 상기하자. 그리고 알게된 사실 하나!! -> value를 리스트로 할 수 있따!!!!)
   • 이제 'anagrams'는 {'aet': ['eat']}과 같은 구조를 갖게 된다. 두번째 iteration (word = "tea"인 경우)
   • 첫번째 iteration과 동일하다.
   • 이제 'anagrams'는 {'aet': ['eat', 'tea']}과 같은 구조를 갖게 된다. 세번째 iteration (word = "tan"인 경우)
   • 첫번째랑 두번째랑 동일하게 돌아가는데, 정렬되었을 때 ['a', 'e', 't']가 아니라 ['a', 'n', 't']니깐 결국 "ant"란 새로운 key가 생기게 되고 이에 대한 리스트 형태의 value로서 "tea"가 추가가 된다.
   • 따라서 'anagrams'는 {'aet': ['eat', 'tea'], 'ant': ['tea']}와 같은 구조를 갖게 되는 거다!! 이렇게 anagram이 되는 것들 끼리 모으는 거다. (이 부분이 참 신기하게 느껴졌다 ㅋㅋ) 이후 iteration도 동일한 방식으로 진행된다.

4. values()로 반환 마지막 return에서 angrams을 이루는 단어들 끼리 출력을 해야하니깐 values()로 뽑은 다음 이를 list() 함수에 넣어 nested list 형태로 반환한다.

꽤나 많은 걸 배운 문제였음. 특히 저 for 루프 돌아가는 게 처음엔 도대체 왜????? 이러다가 이해하니깐 신기했다 정말..오늘도 직관을 얻어서 좋았다.

끝.

A function which is defined inside a class body. If called as an attribute of an instance of that class, the method will get the instance object as its first argument (which is usually called self).

그리고 이 메소드는 두가지 방식으로 불러올 수 있는데, 메소드 자체를 불러오는 것과, 메소드가 반환한 결과를 불러오는 거다. 좀 미묘한 차이라서 헷갈리게 쉬운데 (나만 그런가?), 표면적 예시론 전자의 경우 함수에 늘 붙는 인자를 넣는 괄호를 넣지 않는 경우 (예: x.get)이고 후자는 괄호를 넣는 경우다. 그렇담 그 차이는 무엇일까? 그니깐, 언제 괄호를 빼고 써야하는 거고 언제 괄호를 넣고 써야하는 걸까? 결론부터 말하면 전자의 경우 메소드를 참조값으로 불러오는 거고, 후자는 그렇지 않은 경우다. 즉, 전자의 경우 메소드 (혹은 어떤 함수) 자체를 하나의 참조값으로 통과시킨 다음 나중에 그 참조값을 다른 함수를 통해 불러오기 위한 경우고, 후자는 그렇지 않고 메소드 또는 어떤 함수를 즉각적으로 사용해 얻은 반환값을 사용할 때다.

비유를 통해 설명하면, 괄호를 사용하지 않는 메소드 자체 부르기는 누구한테 가는 방법만 설명해주고 나중에 본인이 알아서 방법을 쓰고 그래서 슈퍼 가서 뭘 사든 알아서 하라는 거고, 괄호를 사용하는 메소드가 발환한 결과 부르기는 누구한테 슈퍼 가는 방법이랑 거기가서 장볼거리 리스트 줘서 장을 봐오라는 거랑 비슷하다.

다음은 메소드 자체 부르기(a.k.a. 괄호 안 씀)에 대한 예시다.

token_count = {'cat': 1, 'saves': 2, 'world': 3}

# pass the method itself
most_frequent = max(token_count, key = token_count.get)

위 코드에서 마지막 라인에서 get()을 메소드 자체로서 불러와 참조값으로 할당이 되었으니 max()이제 그 참조 받은 값을 토대로 자신의 기능을 수행하는 거다.

그리고 다음 건 메소드가 반환한 결과 부르기(a.k.a. 괄호 씀)에 대한 예시다.

token_count = {'cat': 1, 'saves': 2, 'world': 3}

# call the method and pass the result
count = token_count.get('cat') # this returns 1
most_frequent = max(token_count, key = count) # obviously gives you an error

보다시피 max()의 key는 함수(또는 메소드)를 받아야하는데(!!) 어떤 정적인 값을 받으니 오류를 낼 수밖에 없다.

요약하면 어떤 메소드 또는 함수 그 자체를 참조 방식으로 부름으로서 다른 함수가 이를 사용하게 하는 방식이 아니라 메소드 그 자체를 불러오는 거고, 그래서 괄호를 빼서 쓰는 거라고 할 수 있다.

끝.

The words in paragraph are case-insensitive and the answer should be returned in lowercase.

내가 쓴 거

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        # make a banned word list
        banned = set(word.lower() for word in banned)

        # get rid of special characters while lowering cases and spliting
        lowered_s = re.sub(r'[^A-za-z0-9]', ' ', paragraph).lower().split()

        # get rid of banned words
        preprocessed = []
        for i in lowered_s:
            if i not in banned:
                preprocessed.append(i)

        # count words
        word_count = {}
        for words in preprocessed:
            if words not in word_count:
                word_count[words] = 0
            word_count[words] += 1

        # pick the most frequent word and then return it
        return max(word_count, key = word_count.get)

솔루션

import re

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:

        # convert to lower case and split string into words by spaces and punctuation
        a = re.split(r'\W+', paragraph.lower())

        # make new list consisitng of words not in banned list (remove banned words)
        b = [w for w in a if w not in banned]

        # return value that counted max times in the new list
        return max(b, key = b.count)

처음 내가 푼 것의 경우 일단 banned를 하드코딩(내 경우 'hit'이라고 리스트 안에 따로 저장)했는데 오류가 나서 저렇게 했다. 어떻게 할지 몰라서 결국 챗지피티한테 물어보니 저렇게 함..list comprehension을 사용하고 그걸 lower() 시킨 다음 set()으로 씌워서 해당 word를 unique하게 하는 방식이었다. 왜냐하면 banned word 개개는 독립적인 거니깐.

복습 겸 알아둘 것들은 다음과 같다.

단어 세기

• 단어의 갯수를 세는 방법의 경우, 내 경우에는 저렇게 미리 텅 빈 딕셔너리를 명시화한 다음에 하는 게 있다. 즉, 미리 word_count라는 딕셔너리를 만든 다음, 전처리한 리스트 안에 원소들(=words)이 word_count에 '없다면' word_count의 키로서 각각의 word들은 그 value가 0으로서 지정이 된다. 이후 if 문밖에서 각각의 word가 발견될 때 마다 key로서 저장되어 value가 1씩 증가하는 방식임. 그니깐 미리 value가 0인 word들을 넣어놓고 이후 word를 찾을 때 마다 value값을 1씩 증가시키는 거다.
• 혹은 솔루션과 같은 방식으로 a란 변수 안에서 split()으로 쪼개는데 정규식에도 나와있다시피 'W'ord가 아닌 것이 한 번 혹은 한 번 이상이 나온 것을 기준으로 쪼갠다. 그 다음에 b라는 리스트 안에다가 list comprehension을 사용하여 banned에 해당되지 않는 단어들을 한 개씩 넣는다.

get()과 count() 이 함수는 딕셔너리에서 어떤 key의 value를 리턴한다. 안 넣으면 인자 없다고 오류남(None으로 처리한다는 뜻). count는 함수이름곧내. 마찬가지로 안 넣으면 인자 없다고 오류남.

max() 함수제목곧내

return이 뭘 하는지는 알겠는데 왜 max()에 get()과 count()에 괄호가 없나여? 왜냐하면 max()의 key로서 x.get 혹은 x.count로 통과시키면 메소드를 불러온 결과를 부르는 게 아니라, 메소드 그 자체를 불러오는 방식이기 때문이다. 즉, 어떠한 참조값을 해당 메소드에 통과시킴으로서 max()가 딕셔너리 (혹은 리스트)의 각각의 item들을 내부적으로 불러오는 거다. 따라서 실제 max()는 다음과 같은 방식으로 작동된다.

1. 기능참조: x.get (혹은 x.count, 이하 get으로 통일)는 x의 get 메소드에 대한 참조가 됨.
2. 내부적으로 불러오기: max 함수가 get 메소드를 불러옴으로써 x의 item들을 비교함.
3. 최대치 찾기: max 함수는 x.get(key)을 통해 리턴된 값을 얻어서 어떤 게 최대치인지 결정.

끝.

defaults write -g ApplePressAndHoldEnabled -bool false defaults write -g InitialKeyRepeat -int 10 defaults write -g KeyRepeat -int 1

순서대로 첫번째는 키보드에서 키를 꾹 누르고 있을 때 나올 수 있는 기능들 (예: 알파벳에 첨자가 들어간 기호들을 선택할 수 있는 기능)을 해지시키는 것이고, 두번째는 특정 키를 최초로 다시 누를 때 딜레이 시간을 10ms로 하는 거고, 마지막은 이후 키를 반복적으로 누를 때 반응속도비율을 1로 함으로써 최대한 빠르게 하는 거다.

위 명령어들을 터미널에 입력하고 재부팅하고 나니깐 키 반응속도가 전체적으로 진짜 엄청 빨라졌다. 물론 단점도 있는데 더 이상 키 홀드를 함으로써 나올 수 있는 기능을 사용하지 못하게 된다는 것과, 너무 민감해진 나머지 오타가 좀 쉽게 날 수 있다는 것. 근데 난 굉장히 만족하고 있기 때문에 당분간 저 셋팅으로 하고 나중에 저 값들을 조절하든가 할 생각이다.

물론 이런 거 다 필요없고 그냥 vim 쓰면 된다

You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

• Letter-logs: All words (except the identifier) consist of lowercase English letters.
• Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The digit-logs maintain their relative ordering. Return the final order of the logs.

솔루션

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        # seperate letter logs and digit logs
        letters, digits = [], []
        for log in logs:
            # check whether the second substring of an element is digit or not
            if log.split()[1].isdigit(): 
                digits.append(log)
            else:
                letters.append(log)

        # use lambda expression to sort letters 
        # (we don't care digits as they are sorted relatively)
        letters.sort(key=lambda x: (x.split()[1:], x.split()[0])) # remember [1:]
        return letters + digits # notice this adding pattern   

어떻게 코드를 짤지에 대한 논리적 흐름은 잘 맞췄는데 이에 대응되는 함수들을 떠올리지 못해 풀지 못했었다 :( 복습과 평소 코딩 이것저것 해봄의 중요성을 느낌..

알아둘 것들은 다음과 같다.

split() 주어진 문자열을 띄어쓰기(=speace-delimited)를 기준으로 분리한다. 위 솔루션의 경우, logs라는 리스트에서 각 원소(=log)를 split()을 이용해 띄어쓰기를 기준으로 쪼갠 후, 여기서 index == 1인 경우를 선택한 뒤 이것이 디짓인지 아닌지 판단한다. 디짓이라면 digits이란 리스트에 추가, 아니면 letters에 추가한다.

isdigit() 함수 제곧내. 물론 isalpha()도 있다.

lambda 매개변수 : 표현식 맨날 봤는데 까먹는 이눔의 람다...위 코드에서 람다는 다음과 같이 작동한다. 먼저 람다가 사용된 것만 떼어놓고 보자.

letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))

1. sort() 함수에서 key 매개변수는 정렬을 하기 위해 각 원소를 비교하기 이전에 각 리스트들의 원소들에 대한 함수를 무엇으로 할지 구체화한다.
2. lambda x 이하는 주어진 리스트 x의 각 원소들을 쪼갠 뒤 튜플((x, y) 꼴로 생긴 걸 주목하자)로 리턴한다.
3. x.split()[1:]는 리스트 x의 원소들 중 index == 1인 것부터 시작해 그 뒤 나머지 원소들을 띄어쓰기를 기준으로 접근한다. 3-1. 예컨대 ''2 A'',이라면 '['A']'로 접근할 것이고, 3-2. ''2 A B''라면 '['A', 'B']'로 접근할 것이다 ([1:]니깐!)
4. x.split()[1:], x.split()[0]을 수행한 후 이 람다 함수는 2에서는 말한 것처럼 이 모양꼴 그대로 튜플로 리턴할 것이므로, 예컨대 ''2 A''라면 '(['A'], '2')'로 리턴할 것이다.
5. 이렇게 출력된 튜플들은 다시 sort()를 통해 정렬될 것이고, 이 때 정렬함수는 튜플의 index == 0인 원소를 기준(이 경우 알파벳 또는 lexicographically순)으로 정렬될 것이다.

return digits + letters 두 개의 리스트를 더할 때 따로 정렬없이 그대로 더해진다. 예컨대 digts = [1], letters =[a]라면 위 리턴 함수는 [1, a]를 출력할 것이고, 반대로 적혀있다면 [a, 1]로 출력될 것이다.