greentea31's Note

https://school.programmers.co.kr/learn/courses/30/lessons/42579

풀이 과정

각 노래의 장르와, 플레이 된 횟수가 주어질 때, 가장 많이 플레이된 장르의 노래가 먼저 나오게끔, 각 장르별로 많이 재생된 2개의 노래씩을 모아 베스트 앨범을 만드는 문제이다.

장르: [장르 재생 횟수, [[노래 인덱스, 재생 횟수], [노래 인덱스, 재생 횟수]...] 꼴의 딕셔너리를 만들고, 장르 재생 횟수와 노래 재생 횟수로 적절히 정렬을 수행하여 문제를 해결하였다.

코드에서 딕셔너리 genres_dict와 딕셔너리를 정렬된 리스트로 표현한 temp를 중간에 출력한 테스트 결과이다.

소스 코드

import collections

def solution(genres, plays):
    genres_dict = collections.defaultdict(list)
    for index, genre in enumerate(genres):
        if not genres_dict[genre]:
            genres_dict[genre].append(plays[index])
            genres_dict[genre].append([[index, plays[index]]])
        else:
            genres_dict[genre][1].append([index, plays[index]])
            genres_dict[genre][0] += plays[index]
    temp = sorted(genres_dict.values(), key=lambda x: x[0], reverse=True)
    for song in temp:
        song[1].sort(key=lambda x: x[1], reverse=True)
    answer = []
    for song in temp:
        if len(song[1]) >= 2:
            answer.append(song[1][0][0])
            answer.append(song[1][1][0])
        else:
            answer.append(song[1][0][0])
        
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/1829

풀이 과정

배열로 주어진 그림에서 몇 개의 영역이 있는지, 가장 넓은 영역의 크기는 얼마인지 구하는 문제이다.

그래프에서 연결 요소의 개수와 가장 큰 연결 요소의 크기를 구해달라는 말과 같고, 색칠이 되어 있고, 아직 방문하지 않은 모든 좌표에 대해 BFS 혹은 DFS를 진행해주면 된다.

소스 코드

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

bool visit[101][101];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

int bfs(int y, int x, vector<vector<int>>& picture, int m, int n) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));
    int max_size = 1;
    int color = picture[y][x];
    
    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (0 <= ny && ny < m && 0 <= nx && nx < n && !visit[ny][nx] && color == picture[ny][nx]) {
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
                max_size++;
            }
        }
    }
    
    return max_size;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visit[i][j] && picture[i][j] != 0) {
                int temp = bfs(i, j, picture, m, n);
                number_of_area++;
                if (max_size_of_one_area < temp) max_size_of_one_area = temp;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            visit[i][j] = false;
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

https://leetcode.com/problems/subsets/

풀이 과정

주어진 배열의 부분 집합을 구하는 문제이다.

재귀로 배열의 각 인덱스에 해당하는 원소가 부분 집합에 들어갈지, 안들어갈지 판단해주면서 answer 배열에 추가해주었다. 어떤 배열이 주어지던, 부분 집합에 공집합은 반드시 포함되므로, 정답 배열에 공집합을 넣어놓고 재귀 함수를 수행하였다.

소스 코드

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        answer = [[]]
        output = []
        
        def subset(index):
            if index >= len(nums):
                return
            output.append(nums[index])
            answer.append(output[:])
            subset(index+1)
            output.pop()
            subset(index+1)
        
        subset(0)
        return answer

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

풀이 과정

배열로 주어진 수들의 중복조합의 합이 target이 되는 경우를 구하는 문제이다.

https://greentea31.tistory.com/196?category=947572 

위 문제를 해결했던 것 처럼 어떤 수를 고르고, 안고르고의 경우를 재귀함수로 계산하게끔 하였다. 단 이번 문제는 중복조합이므로, 어떤 수를 골랐어도 다음에도 또 고를 수 있으므로, 어떤 수를 골라서 sum_value가 증가하는 경우, 고를지 말지 판별해야 하는 index가 증가하게끔 하지 않았다.

어떤 수를 고르지 않는 경우에는 index+1을 시켜줘야 한다.

i 안 고름 -> i 안 고름 -> i 안 고름 -> 무한반복 -> i 고름

i 고름

는 같은 경우인데 연산 과정만 늘어나고 재귀를 탈출하지도 못하기 때문이다.

소스 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        output = []
        
        def combination(index, sum_value):
            if sum_value >= target:
                if sum_value == target:
                    answer.append(output[:])
                return
            if index >= len(candidates):
                return
                
            output.append(candidates[index])
            combination(index, sum_value + candidates[index])
            output.pop()
            combination(index+1, sum_value)
        
        combination(0, 0)
        return answer

https://leetcode.com/problems/combinations/

풀이 과정

주어진 n개의 원소의 리스트에서 k개의 숫자로 이루어진 조합을 구하는 문제이다.

https://greentea31.tistory.com/111?category=939228 

위의 글의 코드를 구현하였다. 1~4까지의 수를 원소로 가진 리스트에서 2개를 뽑아 조합을 만들어야 한다면 1을 고르는 것과 안고르는 것, 2를 고르는 것과 안고르는 것, 3을 고르는 것과 안고르는 것, 4를 고르는 것과 안고르는 것... 이런식으로 구하다 골라야 하는 수가 4를 넘어가거나, 이미 고른 수가 2를 넘어가면 그만두게 하고, 이미 고른 수가 2개가 되는 경우마다 정답 배열에 추가해 주면 모든 조합을 구할 수 있다.

책에서 본 좋은 코드도 재귀 2에 기록해 두었고, itertools 모듈의 combinations 함수를 사용하면 문제를 더 쉽게 해결할 수 있다.

소스 코드

재귀 1

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        answer = []
        output = [-1 for _ in range(k)]
        
        def combination(index, selected):
            if selected == k:
                answer.append(output[:])
                return
            if index > n:
                return
            
            output[selected] = index
            combination(index+1, selected+1)
            combination(index+1, selected)
        
        combination(1, 0)
        return answer

재귀 2

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []
        
        def combination(elements, start, k):  # 추가된 원소, 탐색 시작점, 넣어야 될 남은 원소 개수
            if k == 0:  # 다 넣었으면 정답 추가
                results.append(elements[:])
                return
            
            for i in range(start, n+1):
                elements.append(i)  # i를 넣는 경우
                combination(elements, i+1, k-1)
                elements.pop()  # i를 넣지 않는 경우
        
        combination([], 1, k)
        return results

itertools

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(itertools.combinations(range(1, n+1), k))

https://leetcode.com/problems/permutations/

풀이 과정

주어진 리스트의 순열을 구하는 문제이다.

itertools 모듈의 permutation 함수를 사용하면 문제를 쉽게 해결할 수 있다. 또한, DFS로도 순열을 생성할 수 있다.

https://greentea31.tistory.com/110?category=939228 

위의 재귀로 순열을 구현하는 예제가 일종의 dfs - backtracking으로 순열을 구현한 것이다.

재귀 1의 소스코드에서, answer.append(output)을 사용하면 맨 마지막 output이 중복 저장되므로

1. answer.append(output[:])

2. answer.append([i for i in output])

3. import copy

    answer.append(copy.deepcopy(output))

등을 이용해주어야 한다.  위의 2방법은 객체 내의 내부 객체까지는 복사되지 않는 반면, deepcopy를 사용하면 깊은 복사가 되어 내부 객체까지 완벽히 복사된다. 이 문제에서는 리스트 내의 리스트까지 존재하지는 않으므로 위의 2방법을 사용해도 된다.

소스 코드

재귀 1

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        output = [-1 for _ in range(length)]
        answer = []
        discovered = collections.defaultdict(bool)
        
        def go(index, length):
            if index == length:
                answer.append(output[:])  # answer.append(output) 사용시 맨 마지막 output값 중복 저장됨.
                return
            
            for num in nums:
                if not discovered[num]:
                    discovered[num] = True
                    output[index] = num
                    go(index+1, length)
                    discovered[num] = False
        
        go(0, length)
        return answer

재귀 2

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []  # 이미 순열에 넣은 원소의 집합
        
        def dfs(elements):
            if len(elements) == 0:  # 모든 원소를 다 넣었으면 결과 값에 넣는다.
                results.append(prev_elements[:])
                # [:]가 없으면 prev_elements가 변경되면서 results에 들어갔던 값들도 변경된다.
            
            for ele in elements:
                prev_elements.append(ele)
                #  next_elements는 앞으로 순열에 넣어야 할 원소의 집합
                next_elements = elements[:]
                next_elements.remove(ele)
                
                dfs(next_elements)
                prev_elements.pop()
        
        dfs(nums)
        return results

itertools

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

풀이 과정

숫자 문자열이 주어졌을때 문자열의 각 숫자로 만들수 있는 알파벳 조합을 리턴하는 문제이다.

'234'가 주어졌다고 가정하면 2에서 a고르고 3으로 넘어가고, b고르고 3으로 넘어가고, c고르고 3으로 넘어가고... 이러한 방법을 반복해주다가 숫자 문자열의 길이와 내가 고른 알파벳 문자열의 길이가 같아지면 정답 배열에 알파벳 문자열을 추가해주면 된다.

일종의 dfs backtracking 문제이다. 숫자 문자열의 길이보다 작은 길이의 알파벳 문자열을 만드는 문제였으면 특정 숫자를 사용할지 사용하지 않을지 고르는 부분도 추가되어야 했을 것이다.

재귀를 사용해 구현하였다.

소스 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        answer = []
        
        def combi(index, discovered=""):
            if len(discovered) == len(digits):
                if digits:
                    answer.append(discovered)
                return
            for i in dic[digits[index]]:
                combi(index+1, discovered + i)

        combi(0)
        return answer

https://leetcode.com/problems/number-of-islands/

풀이 과정

지도에서 땅으로 연결된 섬의 개수를 찾는 문제이다.

그래프에서 연결 요소를 찾으라는 문제인데, 지도의 모든 칸에 대해 dfs 혹은 bfs로 방문하면 연결요소의 개수를 찾을 수 있다.

보통 visited 이차원 배열을 선언해서 이전에 방문했는지를 판별하는데, 이 문제는 이차원 배열을 선언하지 않고 이미 방문한 땅을 물로 바꿔주면 방문했던 곳을 다시 방문하는 것을 막을 수 있다. 이러면 메모리 효율성이 증가한다.

지도를 보면서 땅인 부분을 bfs로 방문하고, 정답 변수를 1 증가시켜주고, 방문한 땅 및 그와 연결된 땅을 전부다 물로 바꿔주는 방법으로 문제를 해결할 수 있다.

bfs를 중첩 함수로 만들고 지도에서 땅인 부분을 방문하게끔 하였다.

소스 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        answer = 0
        def bfs(start_y, start_x):
            grid[start_y][start_x] = 0
            Q = collections.deque([[start_y, start_x]])
            while Q:
                v = Q.popleft()
                for i in range(4):
                    ny = v[0] + dy[i]
                    nx = v[1] + dx[i]
                    if 0 <= ny < m and 0 <= nx < n and grid[ny][nx] == "1":
                        Q.append([ny, nx])
                        grid[ny][nx] = 0
                        
                        
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    bfs(i, j)
                    answer += 1
        return answer

https://leetcode.com/problems/top-k-frequent-elements/

풀이 과정

배열에서 가장 많이 출현한 원소를 k개 반환하는 문제이다.

파이썬에서는 collections 모듈의 Counter 클래스를 사용해 리스트에서의 원소의 개수를 쉽게 구할 수 있다.

a = [1, 3, 2, 2, 4]

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

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

c = b.most_common(2) = [(2, 2), (1, 1)]

위와 같이 활용된다.

Counter 클래스를 활용해 문제를 해결하였다.

소스 코드

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        ans = collections.Counter(nums).most_common(k)
        answer = []
        for i in (ans):
            answer.append(i[0])
        return answer

https://leetcode.com/problems/longest-substring-without-repeating-characters/

풀이 과정

문자열을 입력받고 반복되는 문자가 없는 가장 긴 부분 문자열을 구하는 문제이다.

2중 for문으로 문자열을 읽으면서 문자를 딕셔너리에 넣고, 새로운 문자가 이전에 나왔는지 확인하면서 길이 변수를 1씩 늘려가는 방법으로도 풀이가 가능하다. O(N^2)으로 풀이가 되기는 하는데 풀고 나면 수행 시간 순위가 바닥임을 확인할 수 있다.

투 포인터로 O(N)에 해결이 가능하다.

문자열을 읽으면서 각 문자가 마지막으로 나온 위치를 used 딕셔너리 (26칸의 크기로 가진 배열로 처리해도 된다.)에 저장하고, 문자가 이전에 출현한 적이 있고, 투포인터의 시작 지점이 문자의 이전 출현 점보다 같거나 이전이면 같은 문자가 2번 이상 나온 것이므로 시작 지점을 1 늘려주고, 아니면 길이와 투포인터의 끝 지점을 갱신하는 방법으로 문제를 해결할 수 있다.

아래 제출 코드는 2중 반복문이고, 위 제출 코드는 투 포인터이다. 실행시간 차이가 20배 넘게 난다. 2중 반복문으로는 해결이 되긴 하지만 비효율적인 풀이이니 투 포인터를 이용해야 한다.

소스 코드

2중 반복문

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        for i in range(len(s)):
            length = 0
            dic = collections.defaultdict(int)
            for j in range(i, len(s)):
                if dic[s[j]] == 1:
                    break
                dic[s[j]] = 1
                length += 1
                answer = max(length, answer)
        return answer

투 포인터

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_len = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:
                max_len = max(max_len, index - start + 1)
            used[char] = index
        return max_len