greentea31's Note

https://leetcode.com/problems/array-partition/

풀이 과정

배열을 입력 받고, 배열의 원소를 2개씩 짝지은 후, 짝에서 작은 값들의 합이 가질 수 있는 최대값을 출력하는 문제이다.

[1, 3, 2, 6, 4, 5]을 생각해보자. 1은 어떤 원소랑 짝지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 다른 수중 가장 작은 수인 2를 가져오는게 맞을 것이다.

3도 마찬가지다 1, 2가 이미 짝지어졌으니 6 4 5중 어떤 수랑 짝이 지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 남은 수중 가장 작은 4랑 묶이는게 맞을 것이다.

이런식으로 생각하다보면 그냥 배열을 오름차순 정렬한 다음에 앞에서 부터 2개씩 짝짓고, 짝의 작은 값을 다 더하면 합의 최대값이 될 것이라고 판단할 수 있다. 짝도 지을 필요가 없다. 정렬후 짝수번째 index의 원소의 합을 구해주면 된다.

소스 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        answer = 0
        nums.sort()
        for i in range(0, len(nums), 2):
            answer += nums[i]
        return answer

좀 더 효율적이고 짧은 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])

https://leetcode.com/problems/3sum/

풀이 과정

배열에서 합이 0을 이루는 3개의 원소를 출력하는 문제이다.

가장 간단하게 생각하면 완전 탐색으로 O(N^3)으로 풀 수 있을 것이다. 하지만 완전 탐색으로 풀이하면 Time Out으로 풀이에 실패한다. 더 빠르게 문제를 해결할 수 있는 효율적인 코드를 찾아야 한다.

정렬후 투 포인터 알고리즘을 사용하면 문제를 해결할 수 있다. 우선 정렬을 한 후, 각 배열의 원소를 축으로 한번씩 둔 다음, 축의 바로 다음 원소를 left 포인터, 배열의 마지막 원소를 right 포인터로 둔 뒤, 합이 0보다 작으면 left 포인터를 전진, 0보다 크면 right 포인터를 후진 시키는 식으로 O(N^2)만에 문제를 해결할 수 있다.

소스 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i, a in enumerate(nums):
            # same value as before so continue
            if i > 0 and a == nums[i-1]:
                continue
                
            l,r = i+1, len(nums)-1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -=1
                elif threeSum < 0:
                    l+= 1
                else:
                    res.append([a,nums[l],nums[r]])
                    l += 1
                    while nums[l] == nums[l-1] and l<r:
                        l+= 1
        return res

https://leetcode.com/problems/longest-palindromic-substring/submissions/

풀이 과정

문자열 내에서 가장 긴 팰린드롬 부분 문자열을 구하는 문제이다.

팰린드롬 문자열은 뒤집어도 뒤집기 전의 문자열과 같은 문자열을 의미한다. DP로 풀 수 있는 잘 알려져 있는 문제이지만 O(N^2)로 부분 문자열을 확장해가며 해결하였다.

다음과 같은 알고리즘을 구현해 문제를 해결하였다.

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(i):
            left, right = i, i
            while left >= 0:
                if s[i] == s[left]:
                    left -= 1
                else:
                    break
            while right <= len(s) -1:
                if s[i] == s[right]:
                    right += 1
                else:
                    break
            
            while left >= 0 and right <= len(s) - 1:
                if s[left] == s[right]:
                    left -= 1
                    right += 1
                else:
                    break
            
            return s[left+1:right]
                
        answer = ''
        for i in range(len(s)):
            answer = max(answer, expand(i), key=len)
        return answer

https://leetcode.com/problems/most-common-word/

풀이 과정

문자열에서 금지되지 않은 단어 중에, 가장 많이 나온 단어를 출력하는 문제이다.

isalpha(), islower() 등의 파이썬 내장 함수로 알파벳, 소문자 처리를 문제 조건에 맞게 처리해준 후, collections 모듈의 Counter 객체를 사용하여 문자열 안에 나온 단어의 개수를 세주었다. 

Counter 사용법

a = [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]이라고 하면,

b = collections.Counter(a) -> Counter({3: 5, 2: 4, 1: 2})

위와 같이 각 원소가 a에서 몇번 나왔는지 카운터 객체로 반환받을 수 있다.

c = b.most_common() -> [(3, 5), (2, 4), (1, 2)]

most_common() 함수를 통해 튜플을 포함한 리스트의 형태로 반환받을 수 있으므로 c[0][0]으로 접근해 a에서 가장 많이 나온 원소가 무엇인지 파악할 수 있다.

소스 코드

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        real_para = ""
        
        for letter in paragraph:
            if not letter.isalpha():
                letter = ' '
            else:
                letter = letter.lower()
            real_para += letter
        
        paragraph = real_para.split()
        paragraph = collections.Counter(paragraph)
        
        for word in paragraph.most_common():
            if word[0] not in banned:
                return word[0]

https://leetcode.com/problems/reorder-data-in-log-files/

풀이 과정

Letter-logs와 Digit-logs로 나누어 정렬하되, Letter-logs가 Digit-logs보다 앞에 와야 하고, Digit-logs는 입력받은 순서대로 정렬하고 Letter-logs는 사전적으로 정렬을 해야하는 문제이다.

logs의 원소들을 split(' ')으로 공백을 기준으로 쪼갠 후, Letter와 Digit을 분류해주었다.

lets.sort(key=lambda x: (x.split()[1:], x.split()[0]))으로 letter log를 사전식으로 정렬하고, [1], [2], [3]...의 모든 원소가 같으면 identifiers로 정렬하게끔 하였다. 

소스 코드

class Solution:
    def reorderLogFiles(self, logs: list[str]) -> list[str]:
        lets, digs = [], []

        for log in logs:
            if log.split(' ')[1].isdigit():
                digs.append(log)
            else:
                lets.append(log)

        lets.sort(key=lambda x: (x.split()[1:], x.split()[0]))
        return lets + digs

https://leetcode.com/problems/reverse-string/

풀이 과정

문자열 s를 뒤집는 문제이다.

크게 3가지 방법을 떠올릴 수 있다.

1. 내장 함수 사용

그냥 파이썬 내장 함수 써서 뒤집는 방법이다. s.reverse()를 사용하면 된다.

2. 투 포인터 사용

문자열의 시작과 끝에 포인터 2개를 두고 포인터의 인덱스에 해당하는 문자끼리 서로 바꿔가면서 왼쪽 포인터는 한칸 전진, 오른쪽 포인터는 한칸 후퇴하면서 계속 바꿔가면 된다. 이 방법대로 문제를 풀이하였다.

3. 문자열 슬라이싱

s = s[::-1]로 뒤집어서 할당해주면 될 것 같지만 문제에서 공간복잡도를 O(1)로 제한하였다. s[:] = s[::-1] 같은 트릭을 사용하여 이 방법으로도 문제를 해결 할 수 있다.

소스 코드

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

https://leetcode.com/problems/valid-palindrome/

풀이 과정

문자열 s가 팰린드롬인지 확인해주는 기능을 구현하면 된다.

팰린드롬이란 문자열을 뒤집어도 똑같은 문자열을 말한다. 예를 들면 기러기, 토마토, 스위스, 인도인, 별똥별, 우영우, 역삼역 등의 단어는 모두 팰린드롬을 만족하는 단어이다.

문제의 조건에 맞게 대문자는 소문자로 바꿔주고, 알파벳이 아닌 문자는 문자열에서 전부 무시해준 다음, 문자열 s와 s[::-1]을 비교해 같으면 팰린드롬 문자열이라고 판단하였다.

굳이 s와 동일한 원소를 가진 s'를 선언해서 s'.reverse()로 뒤집은 다음 s == s'인지 비교할 필요 없이 문자열 슬라이싱으로 더 빠르게 해결할 수 있다.

소스 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        chars = []
        for char in s:
            if char.isalnum():
                char = char.lower()
                chars.append(char)
        if chars == chars[::-1]:
            return True
        else:
            return False

큐를 활용해 너비 우선 탐색을 시행하는 예시 코드이다.

C++ - Flood Fill BFS

// BFS 예시 코드

#include <bits/stdc++.h>
using namespace std;

int board[502][502];
bool vis[502][502];
int n = 7, m = 10; // n은 가로 길이, m은 세로 길이
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<pair<int, int>> Q;
    vis[0][0] = true;
    Q.push(make_pair(0, 0));

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        cout << '(' << cur.second << ", " << cur.first << ") -> ";
        for (int dir = 0; dir < 4; dir++) {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[ny][nx] || board[ny][nx] != 1) continue;
            vis[ny][nx] = true;
            Q.push(make_pair(ny, nx));
        }
        
    }
    
    return 0;
}

Python - 인접 리스트로 주어진 그래프에 대한 BFS

import collections

graph =[[], [1], [1, 3]] # 인접 리스트로 주어진 그래프


def bfs(start_v):
    discovered = [start_v]
    queue = collections.deque([start_v])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

연결되어 있고 방문하지 않은 정점들을 전부다 큐에 넣고 방문 처리한다.

큐가 빌 때 까지 큐의 맨 앞의 정점에 대해 이를 반복한다.

출처

C++ 코드

https://blog.encrypted.gg/941?category=773649 

Python 코드

https://book.naver.com/bookdb/book_detail.nhn?bid=16406247 

https://leetcode.com/problems/trapping-rain-water/

풀이 과정

다음과 같은 input이 들어올 때, 고이는 물의 총부피를 구하는 문제이다.

가장 높은 바닥을 기준으로 왼쪽 영역과 오른쪽 영역으로 나눠서 생각하면 풀이 방법이 빠르게 떠오른다.

왼쪽 영역은 왼쪽에서부터, 오른쪽 영역은 오른쪽에서 부터 읽어 나가면서, 여태 나왔던 바닥의 최대 높이를 저장하고, 바닥의 최대 높이 - 현재 바닥의 높이만큼 물이 고일 것이므로 그만큼을 정답 변수에 더해주면 된다.

소스 코드

class Solution:
    def trap(self, height: List[int]) -> int:
        left_max, right_max = 0, 0
        max_height_index, max_height = 0, 0
        answer = 0
        
        for i in enumerate(height):
            if max_height < i[1]:
                max_height_index, max_height = i[0], i[1]
                
        for i in range(0, max_height_index):
            if left_max < height[i]:
                left_max = height[i]
            else:
                answer += left_max - height[i]
        
        for i in range(len(height)-1, max_height_index, -1):
            if right_max < height[i]:
                right_max = height[i]
            else:
                answer += right_max - height[i]
        
        return answer

https://leetcode.com/problems/two-sum/

풀이 과정

합이 target이 되는 배열 값을 가리키는 인덱스 2개를 구하라는 문제이다.

완전 탐색을 돌려서 O(N^2)로 답을 구할 수 있다. 그런데 후속 조치로 O(N^2) 보다 적은 시간 복잡도를 가진 알고리즘으로 해결할 수 있냐는 질문이 달려있다.

1. 투 포인터로 풀기

입력된 리스트에 enumerate로 index 붙여주고, x:x[1]에 대해 정렬시킨 뒤, 포인터를 배열의 시작, 끝부분에 위치시키고 포인터에 해당하는 배열의 합이 타겟보다 작으면 left += 1, 아니면 right -= 1 시켜가면서 답을 구했다.

정렬이 O(NlogN)이고 투포인터로 배열 탐색이 O(N) 걸리니 알고리즘의 시간 복잡도는 O(NlogN)이다. 105ms의 실행시간을 가지는 효율적 방법이다.

2. 딕셔너리로 풀기

딕셔너리[값] = 인덱스를 저장해나가면서, 타겟 - 값을 키로 갖는 밸류가 딕셔너리에 존재하는지 살펴본다. 배열을 1회만 탐색하면 되므로 O(N)인데 실행시간이 112ms가 나와 투 포인터보다 의미 있게 빠르진 않았다.

소스 코드

투 포인터

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        s_nums = sorted(enumerate(nums), key=lambda x:x[1])
        
        while (left < right):
            sum = s_nums[left][1] + s_nums[right][1]
            if sum == target:
                return [s_nums[left][0], s_nums[right][0]]
                break
            elif sum < target:
                left += 1
            else:
                right -=1

딕셔너리

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], i]
            dic[num] = i