greentea31's Note

https://leetcode.com/problems/k-closest-points-to-origin/

풀이 과정

유클리드 거리가 가장 가까운 k개의 좌표를 출력하는 문제이다.

그냥 모든 좌표의 유클리드 거리를 구한 뒤, 정렬해서 앞에서 k개를 출력하거나, 우선순위 큐에 넣어서 k개를 pop을 해주는 방법으로 문제를 해결할 수 있다.

소스 코드

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []
        
        for x, y in points:
            dist = x ** 2 + y ** 2
            heapq.heappush(heap, (dist, x, y))
        
        answer = []
        
        for _ in range(k):
            dist, x, y = heapq.heappop(heap)
            answer.append([x, y])
        
        return answer

https://leetcode.com/problems/largest-number/

풀이 과정

여러 숫자를 앞뒤로 이어 붙여 가장 큰 숫자를 만드는 문제이다.

위의 예시에서 보이듯 3, 30, 34, 5, 9의 숫자 모음은 9, 5, 34, 3, 30 순으로 붙여야 가장 큰 수로 만들 수 있다. 커스텀 비교 연산자를 하나 선언해서 문제를 해결할 수 있다. 원래의 비교에 따르면 3과 30을 비교하면 30이 더 큰 숫자이고 34와 5를 비교하면 34가 더 큰 숫자이다. 하지만 이 문제를 해결하기 위해서는 str(x) + str(y) > str(y) + str(x)일때 참을 출력하는 커스텀 비교 연산자를 하나 만들어주어야 한다.

그러면 3과 30은 330 > 303이므로 3이 더 큰 것으로 처리되고 34와 5는 345 < 534이므로 5가 더 큰 것으로 처리될 것이다. 이와 같이 처리해야 문제의 조건을 만족할 수 있다.

소스 코드

class to_swap(str):
    def __lt__(x, y):
        return x+y > y+x

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(i) for i in nums]
        nums.sort(key=to_swap)
        return str(int(''.join(map(str, nums))))

https://leetcode.com/problems/merge-intervals/

풀이 과정

수직선 간의 주어진 구간에서, 겹치는 구간은 합병하는 문제이다.

위의 예시는 1~3 2~6은 겹치는 부분이니 1~6으로 합병한 예시임을 확인할 수 있다.

intervals을 리스트 내의 첫번째 원소를 기준으로 정렬해준 뒤, 각 구간의 현재 시작, 끝점과 이전 시작, 끝점을 비교하면서 이전 끝점이 현재 시작점보다 크면 합병을 해주는 방식으로 진행하였다. 합병 도중 이전 끝점이 현재 끝점보다 크면 합병 구간이 현재 끝점으로 당겨지는 경우가 없도록 예외 처리를 해주어야 한다.

소스 코드

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        prev_start, prev_end = intervals[0][0], intervals[0][1]
        answer = []
        
        for start, end in intervals:
            if prev_end >= end:
                continue
            if prev_end >= start:
                prev_end = end
                continue
            else:
                answer.append([prev_start, prev_end])
                prev_start, prev_end = start, end
        
        answer.append([prev_start, prev_end])
        
        return answer

https://leetcode.com/problems/sort-list/

풀이 과정

연결 리스트를 정렬하는 문제이다.

연결 리스트를 merge sort로 정렬해주거나, 연결 리스트를 리스트에 담고 내장 함수 sort() 이용후 다시 리스트에 담는 두 방법 중 한가지를 이용해주면 문제를 해결할 수 있다.

소스 코드

연결 리스트 -> 리스트 -> 연결 리스트

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = head
        lst = []
        
        while p:
            lst.append(p.val)
            p = p.next
        
        lst.sort()
        
        p = head
        for i in range(len(lst)):
            p.val = lst[i]
            p = p.next
            
        return head

merge sort

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        
        return l1 or l2
    
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # head, head.next 둘다 null이면
        if not (head and head.next):
            return head
        
        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, fast.next.next
        half.next = None
        
        l1 = self.sortList(head)
        l2 = self.sortList(slow)
        
        return self.mergeTwoLists(l1, l2)

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

풀이 과정

여러개의 사각형이 주어질 때, 시작점에서 도착지점까지 사각형의 모서리만 타고 이동할 때의 최소 이동 횟수를 구하는 문제이다.

문제에서 주어진 예시와 같이 사각형의 내부는 방문할 수 없다.

입력값을 확인하면서 사각형의 모서리는 board값 1, 사각형 내부는 2, 내부와 모서리가 겹치는 경우는 내부가 우선해서 모서리 처리 안되게끔 board값을 처리하고 이동 가중치가 전부 1이니까 BFS로 board를 탐색하면서 최소 이동 거리를 구하면 답이 나올 것 같다. 하지만 이렇게 해결시 몇몇 테스트 케이스에서 오류가 발생한다.

위의 그림에서 (x, y) = (3, 5)인 지점을 보자. (4, 5)도 방문이 가능하지만 (3, 6)도 거리가 1만큼 떨어저 있고 사각형의 모서리에 해당하므로 방문이 가능하다고 판단해서 방문해버린다. 실제로는 (3, 6)을 방문하려면 (4, 5), (4, 6)을 먼저 방문해야 함에도 불구하고 말이다.

ㄷ자 모양의 모서리부분이 존재할 시, 바로 방문 불가능한 점을 방문이 가능하다고 처리하는 문제가 발생하는 것이다. 가장 간단한 해결방법은 좌표계를 2배 확대해서 보는 것이다. (1, 1)과 (1, 2) 사이에 2칸이 있다고 생각하는 것이다.

좌표계를 2배로 잡아서 보고 시작점, 도착지점 다 2배씩 해준 다음에 마지막에 구한 최소 이동 횟수도 2로 나눠주면 ㄷ자 모양의 모서리에서도 오류가 발생하지 않고 정상적으로 답을 구할 수 있다.

소스 코드

import collections

def solution(rectangle, characterX, characterY, itemX, itemY):
    board = [[0 for _ in range(102)] for _ in range(102)]
    for rec in rectangle:
        a, b, c, d = rec
        a *= 2; b *= 2; c *= 2; d *= 2
        for y in range(b, d+1):
            for x in range(a, c+1):
                if board[y][x] == 2:
                    continue
                if y == b or y == d or x == a or x == c:
                    board[y][x] = 1
                else:
                    board[y][x] = 2
    
    def bfs(start_y, start_x):
        dy = [0, 1, 0, -1]
        dx = [1, 0, -1, 0]
        discovered = [[False for _ in range(102)] for _ in range(102)]
        Q = collections.deque()
        Q.append([start_y, start_x, 0])
        discovered[start_y][start_x] = True
        
        while Q:
            cur_y, cur_x, dist = Q.popleft()
            if cur_y == itemY*2 and cur_x == itemX*2:
                return dist // 2
            for i in range(4):
                ny = cur_y + dy[i]
                nx = cur_x + dx[i]
                if 1 <= ny <= 100 and 1 <= nx <= 100 and board[ny][nx] == 1 and not discovered[ny][nx]:
                    Q.append([ny, nx, dist+1])
                    discovered[ny][nx] = True
        
    answer = bfs(characterY*2, characterX*2)
    return answer

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

풀이 과정

ICN에서 시작해 주어진 비행기 표를 모두 사용하는 여행 경로를 짜는 문제이다. 가능한 경로가 여러개라면 사전식으로 앞선 경로를 답으로 내야 한다.

모든 도시를 방문할 수 없는 입력은 들어오지 않으므로 모든 도시를 DFS로 방문하면 된다. 비행기 표를 defaultdict에 담아놓는데, pop으로 비행기표를 꺼내면서 알파벳 순이 앞선 도시를 먼저 방문하기 위해 티켓 리스트를 도착지를 기준으로 알파벳 내림차순으로 정렬해놓고 defaultdict에 담았다.

https://greentea31.tistory.com/202

LeetCode의 332번 문제와 아주 유사한 문제이고 풀이도 유사하게 하면 된다.

소스 코드

import collections

def solution(tickets):
    answer = []
    ticket_list = collections.defaultdict(list)
    tickets.sort(key=lambda x: x[1], reverse=True)
    
    for depart, arrive in tickets:
        ticket_list[depart].append(arrive)
    
    print(ticket_list)
        
    def dfs(go):
        while ticket_list[go]:
            dfs(ticket_list[go].pop())
        answer.append(go)  # 재귀를 사용해 여행순서가 반대 순서대로 answer에 저장된다.
        
    dfs('ICN')
    return answer[::-1]  # 그래서 반대로 출력해주어야 한다.

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

풀이 과정

words 배열에 있는 단어 중, 현재 단어와 한 글자 차이 나는 단어로 이동이 가능하다고 할 때, begin에서 target까지 가는 가장 짧은 변환 과정을 구하는 문제이다. 변환이 불가능하면 0을 출력하면 된다.

이동 가능한 단어간의 거리는 1, 구해야 하는 것은 가장 짧은 경로.... 문제를 읽다보면 BFS가 바로 떠오른다. 이미 방문한 적이 있는 단어는 방문하지 않게끔 처리하면서 BFS로 단어들을 탐색하면서 거리를 측정하면 된다. 각 단어는 노드, 한 글자씩 차이나는 단어 노드들간에 간선이 존재하는 그래프로 생각할 수 있다.

어떤 진행 경로에서 방문하지 않았던 단어여도, 다른 진행 경로에서 방문한 단어면 방문 할 필요가 없다. 예를 들어 cat -> cot 경로가 존재하고 cat -> cet 경로에서 다음 단어를 찾는다고 가정해보자. BFS 진행 중, cat -> cet -> cot로 방문이 가능해야 하지만 어차피 이건 cat -> cot 경로보다 정답에 도달하는게 무조건 느리다. 따라서 방문을 할 필요가 없고, 다른 경로에서 이미 방문한 단어이므로 방문 불가능 처리를 해주면 된다. 즉, 경로마다 각자의 진행 경로를 저장할 필요 없이 어떤 경로에서든 이미 방문한 단어 노드이면 방문이 불가능하다고 생각해야 필요없는 경로를 구성하지 않으면서 답을 구할 수 있다.

소스 코드

import collections


discovered = []

def solution(begin, target, words):
    def transferable(a, b):
        same_char = 0
        length = len(a)
        for i in range(length):
            if a[i] == b[i]:
                same_char += 1
        if same_char == length-1:
            return True
        else:
            return False
    
    def bfs(start, words):
        Q = collections.deque()
        Q.append([start, 0])
        discovered = [False for _ in range(len(words))]
        
        while Q:
            cur_word, dist = Q.popleft()
            print(f'cur_word: {cur_word}, dist: {dist}')
            if cur_word == target:
                return dist
            for index, word in enumerate(words):
                if discovered[index]:
                    continue
                if not transferable(cur_word, word):
                    continue
                discovered[index] = True
                Q.append([word, dist+1])
        
        return 0
        
    
    if transferable(begin, target):
        return 1
    
    answer = bfs(begin, words)
    
    return answer

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

풀이 과정

상하좌우로 이동 가능한 좌표계에서, 통과 가능한 공간과 통과 불가능한 벽이 주어질 때, 시작점 (1, 1)에서 도착점 (n, m)까지 경로의 최단 거리를 구하는 문제이다.

문제의 예시에서 보이듯이, 위처럼 지도가 주어지면 최단 경로의 길이는 11이 된다.

좌표간의 가중치가 존재하지 않으므로 그냥 BFS를 돌려서 최단거리를 구하면 된다.

파이썬에서 BFS를 구현 시, 이미 접근한 좌표를 discovered 배열에 넣는, 예를 들어 discovered = [] 상태에서 [1, 1] 방문시 discovered.append([1, 1])로 좌표를 넣어주고 BFS로 진행할 좌표를 찾을 때 not in discovered 조건으로 구현하는 경우가 있다. 그러나 이 문제에서는 효율성 테스트에서 시간 초과가 발생할 것이다. set이나 dictionary 자료형이 아니면 in이나 not in으로 자료형을 탐색하는 연산의 시간복잡도는 O(N)이 된다.

이 문제 같은 경우에는 이미 방문한 점을 map에서 2로 바꿔준다거나 하는 방법으로 해결이 가능하다. 별도의 discovered 리스트로 방문 점을 판별하고 싶다면 discovered = [[0 for _ in range(m)] for _ in range(n)] 과 같이 별도의 방문점을 판별하는 2차원 배열을 선언후 값을 바꿔주어야 방문 가능 판단 연산이 O(1)이 된다.

소스 코드

import collections

def solution(maps):
    def bfs(maps, n, m):
        Q = collections.deque()
        Q.append([0, 0, 1])
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        
        while Q:
            cur_y, cur_x, dist = Q.popleft()
            for i in range(4):
                ny = cur_y + dy[i]
                nx = cur_x + dx[i]
                ndist = dist + 1
                if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == 1:
                    Q.append([ny, nx, ndist])
                    maps[ny][nx] = 2
                    if ny == n-1 and nx == m-1:
                        return ndist
        
        return -1
                
            
    answer = bfs(maps, len(maps), len(maps[0]))
    return answer

# discovered = [] 와 in으로 방문 여부 판단하면 in이 O(N)이라서 시간초과가 발생한다.

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

풀이 과정

A로만 이루어져 있는 글자가 주어질 때, 원하는 문자열로 바꾸려면 조이스틱을 몇 번 조작해야 하는지 구하는 문제이다.

위의 예시를 읽으면서 생각해보면 조이스틱을 위나 아래로 몇 번 조작해야 하는지는 구하기가 간단할 것 같다. A는 0, B는 1, C는 2, ... M은 12, N은 다시 12, O는 11 ... Z는 1번 조이스틱을 조작해서 만들 수 있다.

문자열의 문자를 읽으면서 각 문자에 대응하는 숫자를 조이스틱의 이동 횟수에 더해주면 위, 아래 조작수는 전부 답에 더해진다. 하지만 왼쪽, 오른쪽 조작은 몇 번 해야할까? 문자열의 길이만큼 조작한다고 하기엔 BBAAA는 좌우 이동이 오른쪽으로 한번만 필요한 문자이다.

펜대를 굴려가며 여러 예시를 쓰면서 생각해보면 결국 가장 긴 연속된 A 문자열을 지나가지 않도록 좌우 이동을 해야 최소 이동횟수가 나오겠다는 생각이 든다. 그러면 가능한 최소 경우는 아래와 같다.

1. 그냥 문자열의 길이 - 1 만큼 좌우 이동을 해야하는 경우

ex) BABAB -> 모든 B를 A로 바꿔주려면 결국 4번 이동해야 한다. 다른 방법은 존재하지 않는다.

2. 왼쪽으로 진행하다 꺾어서 오른쪽으로 진행

ex) ABBBBAAAB -> 왼쪽으로 한번 진행후 B를 A로 바꿔준 뒤, 오른쪽으로 가면서 모든 B를 A로 바꿔주는게 최소 경우이다. 좌우 이동횟수 6번이 최소 횟수이다. 문자열의 길이 - 1 = 8보다 적게 이동이 가능함을 알 수 있다. 가장 긴 연속된 A 문자열 AAA 안쪽은 굳이 지나갈 필요가 없기 때문이다.

3. 오른쪽으로 진행하다 왼쪽으로 꺾어서 진행

2번과 비슷한 예시를 생각해볼 수 있다.

소스 코드

def solution(name):
    answer = 0
    minimum_move = len(name) - 1
    
    for i, char in enumerate(name):
    	# 상하 최소 조작 횟수를 구하는 부분
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        nxt = i + 1
        
        while nxt < len(name) and name[nxt] == 'A':
            nxt += 1
            
        # 좌우 최소 이동횟수를 구하는 부분          
        minimum_move = min([minimum_move, 2 *i + len(name) - nxt, i + 2 * (len(name) - nxt)])
        
    answer += minimum_move
    return answer

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

풀이 과정

limit의 무게 제한이 있는 2인용 구명보트에 임의의 무게를 가진 사람들을 모두 태우고 나가려면 구명보트가 몇 대가 있어야 하는지 구하는 문제이다.

투 포인터를 이용하여 문제를 쉽게 해결할 수 있다. 무게 배열을 오름차순으로 정렬하고, left 포인터를 0, right 포인터를 오른쪽 끝에 위치시키자.

people[left] + people[right]가 limit를 넘으면 people[right]는 배열 내의 어떤 사람이랑 짝을 지어도 무조건 limit를 넘게 된다. (정렬했으므로 people[left]가 무조건 최소 무게 사람) 따라서 right번째 있는 사람은 무조건 배를 혼자 타야 하므로 right 포인터를 1 감소시키고, 사용한 배의 횟수를 1 증가시켜주면 된다.

people[left] + people[right]가 limit를 넘지 않는다면, 2명이서 배를 탈 수 있으므로, left 포인터 증가, right 포인터 감소, 사용한 배의 횟수를 1 증가시켜주면 된다. 

첫번째 입출력 예시에 위의 알고리즘을 적용한다면

people.sort() -> [50, 50, 70, 80]

1. 50 + 80 안되므로 80kg 혼자 배에 태우고 right -= 1

2. 50 + 70 안되므로 70kg 혼자 배에 태우고 right -= 1

3. 50 + 50 가능하므로 둘이 배에 태우고 left += 1, right -= 1

4. left, right가 교차했으므로 -> 모든 사람이 배에 탔으므로 사용한 배의 횟수 출력

순으로 돌아갈 것이다.

소스 코드

def solution(people, limit):
    people.sort()
    answer = 0
    left = 0
    right = len(people) - 1
    
    while left < right:
        if people[left] + people[right] <= limit:
            answer += 1
            left += 1
            right -= 1
        else:
            right -= 1
            answer += 1
    
    if left == right:
        answer += 1
    
    return answer