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://school.programmers.co.kr/learn/courses/30/lessons/64065

풀이 과정

튜플을 표현하는 집합을 문자열로 받아서 튜플을 출력하는 문제이다.

튜플은 순서가 다르면 원소가 같더라도 다른 튜플이지만, 집합은 순서가 달라도 같은 집합이다. 한 튜플을 표현하는 집합은 다양한 순서로 입력받을 수 있는데 어떻게 하나의 튜플을 식별이 가능한가?

어떤 순서로 들어와도 동일하게 처리하기 위해서 집합을 길이가 짧은 순서대로 오름차순 정렬을 해버리면 된다.

{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}가 어떤 튜플을 가리키는지 알기 위해서는 길이 순서대로 정렬을 하면,

{2}, {2, 1}, {1, 2, 3}, {1, 2, 4, 3}이 되는데 숫자가 추가된 순서대로 튜플에 원소를 넣어주면 집합이 어떤 튜플을 표현하는지 쉽게 알 수 있다. 앞에 표현한 집합은 (2, 1, 3, 4) 튜플을 표현함을 알 수 있다.

문자열로 들어온 집합을 어떻게 처리할지는 정답이 없지만 [[1, 2, 3], [2, 1], [1, 2, 4, 3], [2]]와 같은 2차원 리스트로 받은 후 길이 순으로 정렬해서 문제를 해결하게끔 구현하였다.

소스 코드

def solution(s):
    answer = []
    temp = [[]]
    temp_num = 0

    for index in range(len(s)-1):
        if s[index].isnumeric():
            temp_num *= 10
            temp_num += int(s[index])
        elif s[index] == ',':
            if s[index-1] == '}' and s[index+1] == '{':
                continue
            temp[-1].append(temp_num)
            temp_num = 0
        elif s[index] == '}':
            temp[-1].append(temp_num)
            temp_num = 0
            temp.append([])

    del temp[-1]
    temp.sort(key=len)

    for i in temp:
        for j in i:
            if j not in answer:
                answer.append(j)
    return answer

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

https://www.acmicpc.net/problem/11404

풀이 과정

도시와 도시 사이를 오가는 버스의 비용이 주어질 때, 모든 도시의 쌍 (A, B)에 대해 A에서 B로 가는 최소 비용을 구하는 문제이다.

도시는 정점, 버스의 비용은 가중치를 갖는 간선으로 생각하면 하나의 그래프로 모델링할 수 있고, 그래프의 모든 정점의 쌍에 대한 최소 비용을 구하는 문제로 생각할 수 있다.

그래프의 최소 비용 문제에서는 BFS, 다익스트라, 벨만-포드, 플로이드-와샬 알고리즘을 생각해 볼 수 있으며 그중에서 모든 정점의 쌍에 대한 최소 비용은 플로이드-와샬 알고리즘을 사용해서 구할 수 있음이 알려져 있다.

플로이드-와샬 알고리즘을 사용하여 문제를 해결하였다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;

const int INF = 987654321;
int d[105][105];

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

    int n, m;
    cin >> n >> m;

    for (int i = 1 ; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) cout << "0 ";
            else cout << d[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/2606

풀이 과정

컴퓨터와 연결된 네트워크가 주어질 때, 1번 컴퓨터와 네트워크로 연결되어서 웜 바이러스에 걸리게 되는 컴퓨터의 수를 구하는 문제이다.

컴퓨터와 네트워크는 그래프의 정점과 간선으로 모델링 할 수 있고, 1번 정점과 연결된 연결 요소에 포함된 정점의 개수 - 1이 정답이 될 것이다. 연결 요소의 정점의 개수는 DFS 혹은 BFS로 정점들을 탐색하면서 구할 수 있다.

소스 코드

DFS

#include <iostream>
#include <vector>
using namespace std;

vector<int> E[101];
bool visited[101];
int answer = -1;

void dfs(int x) {
    answer++;
    visited[x] = true;

    for (auto next : E[x]) {
        if (visited[next]) continue;
        dfs(next);
    }
}

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

    int computer, edge, u, v;
    cin >> computer;
    cin >> edge;

    for (int i = 0; i < edge; i++) {
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);
    cout << answer << '\n';

    return 0;
}

BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> E[101];
bool visit[101];
int answer;

void bfs(int start_x) {
    queue<int> Q;
    Q.push(start_x);
    visit[start_x] = true;

    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (auto next : E[cur]) {
            if (visit[next]) continue;
            Q.push(next);
            answer++;
            visit[next] = true;
        }
    }
}

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

    int computer, e, a, b;
    cin >> computer;
    cin >> e;

    for (int i = 0; i < e; i++) {
        cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    bfs(1);

    cout << answer << '\n';

    return 0;
}