greentea31's Note

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

풀이 과정

원형으로 앉아있는 사람들 N명끼리 1 ~ N이 써져 있는 카드를 뽑고 버린 후, 뽑은 숫자만큼 공을 오른쪽으로 패스해서, 모든 사람들이 1번씩 공을 패스받았을 때 공이 이동한 순서를 출력하는 문제이다.

N번 카드를 뽑는 것은 공을 맨 처음 가지고 있는 1번 사람만이 가능하다. 1번 사람을 제외한 모든 사람은 공을 받으려면 일단 타인에게 패스를 받아야 하는데, N번 카드를 뽑으면 공이 한 바퀴 돌아서 자신에게 돌아오기 때문에 패스를 2번 받게 되어버리기 때문이다.

첫 번째 사람을 N번 카드를 뽑는다고 고정시키면, 나머지 카드는 1 ~ N-1이 남게 된다. 그런데 N이 홀수라면, 남은 카드의 합 (N(N-1) / 2) - N이 N의 배수가 되어 첫 번째 사람이 패스를 최소 1번 추가로 받게 된다. 따라서 N이 1을 제외한 홀수인 경우 모든 사람이 한 번씩만 패스를 받을 수는 없다.

N이 짝수인 경우 N, 1, N-2, 3, N-4, 5, N-6, 7 ... 순으로 카드를 뽑아서 패스할 경우 모든 사람이 한 번씩만 패스를 받을 수 있다. 다른 경우도 더 존재할 것 같지만 저런 케이스를 출력하여 문제를 해결하였다.

소스 코드

import sys

N = int(sys.stdin.readline())
if N == 1:
    print(1)
    exit(0)
if N % 2 == 1:
    print(-1)
    exit(0)

answer = []
left = N
right = 1
while(True):
    answer.append(str(left))
    left -= 2
    if len(answer) == N:
        break
    answer.append(str(right))
    right += 2
    if len(answer) == N:
        break

print(' '.join(answer))

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

풀이 과정

직사각형 NxM 텃밭에 즈티가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 K개의 딸기를 심고, 레오가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 토마토 K개를 심는다. 씨앗의 종류에 상관 없이 씨앗이 심어진 영역의 좌표가 주어질 때, 딸기와 토마토가 모두 자라는 텃밭 영역의 칸 수와 해당 칸수를 출력하는 문제이다.

텃밭에서 씨앗이 심겨진 칸의 개수를 seed라 하자. 그렇다면 2K - seed의 값이 딸기와 토마토가 같이 심어진 칸의 수임을 쉽게 유추할 수 있을 것이다. 이 경우에 아래의 3가지 경우를 고려할 수 있다.

1. 2K == seed

이 경우에는 딸기와 토마토가 어떠한 영역에도 같이 심어지지 않았을 것이다. 같이 심어졌으려면 seed가 2K보다는 적어야 한다. 그냥 0을 출력해주면 된다.

1.5. K == 1

2K == seed가 아니면서 K == 1이면 board를 살펴보다가 1이 나오는 순간 그 지점의 좌표를 출력해주면 된다.

2. 2K - 1 == seed

딸기와 토마토가 같이 심겨진 영역이 한 칸만 존재하는 경우이다. 딸기를 심는 영역과 토마토를 심는 영역이 가로, 세로 직선이 교차하면서 생기는 경우가 있는데, 그 경우에는 같이 심기는 공간이 1칸만 존재할 수 있고, 2K - 1 == seed일때 이러한 상황이 발생할 수 있다. 따라서 2K - 1일때 모든 칸에 대해 현재 칸에 씨앗이 심겨져 있고, 가로로 왼쪽 혹은 오른쪽에 씨앗이 존재하면서 세로로 위쪽 혹은 아래쪽에 씨앗이 존재하는 경우에는 교차하면서 같이 심기는 경우로 판단하여 한 칸의 좌표만 출력해주었다.

3. 2K - 1 >= seed

seed가 2K - 1보다 작거나, 2K - 1 == seed 인데 가로 세로 직선이 교차하면서 같이 심기는게 아닌 경우가 있다. 이 때는 딸기 영역과 토마토 영역이 가로 직선 - 가로 직선이 겹치거나, 세로 직선 - 세로 직선이 겹쳐서 같이 심기는 영역이 발생하는 경우이다. board를 확인하면서 가로-가로, 세로-세로 겹침중 어느 것인지 판단 후, 겹친 갯수와 겹친 부분을 출력해주면 된다. 겹친 부분은 겹치기 시작한 부분 + seed - K부터 1씩 늘려가면서 2K-S개를 세주면 구할 수 있다. 왜 이렇게 되는지 모르겠다면 코드를 참고하고 그림을 그려가며 생각해보자.

소스 코드

import sys


def one_check(b, N, M):
    dx = [1, -1]
    dy = [1, -1]
    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:
                continue
            check_x = False
            check_y = False
            for i in range(2):
                nx = x + dx[i]
                if 0 <= nx < M and board[y][nx] == 1:
                    check_x = True
                ny = y + dy[i]
                if 0 <= ny < N and board[ny][x] == 1:
                    check_y = True
            if check_x and check_y:
                return f'{y+1} {x+1}'

    return None


N, M, K = map(int, sys.stdin.readline().split())
board = []
for _ in range(N):
    board.append(list(map(int, sys.stdin.readline().split())))

seed = 0

for i in board:
    for j in i:
        if j == 1:
            seed += 1

if 2*K == seed:
    print(0)
    exit(0)

print(2*K - seed)

if K == 1:
    for y in range(N):
        for x in range(M):
            if board[y][x] == 1:
                print(f'{y+1} {x+1}') 
                exit(0)

if 2*K - 1 == seed:
    check = one_check(board, N, M)
    if check is not None:
        print(check)
        exit(0)

start_x, start_y = 2001, 2001
end_x, end_y = -1, -1

for y in range(N):
    for x in range(M):
        if board[y][x] == 1:
            start_x = min(x, start_x)
            start_y = min(y, start_y)
            end_x = max(x, end_x)
            end_y = max(y, end_y)

if start_x == end_x:
    for i in range(2*K - seed):
        print(f'{start_y + seed - K + i + 1} {start_x + 1}')
    exit(0)
if start_y == end_y:
    for i in range(2*K - seed):
        print(f'{start_y + 1} {start_x + seed - K + i + 1}')

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

풀이 과정

서로 다른 정수 N개의 모든 쌍의 차를 구할 때, 서로 다른 차의 개수의 최대값과 최소값을 구하는 문제이다.

모든 쌍의 개수는 NC2 = N(N-1) / 2 이고 NC2개의 모든 쌍의 차가 전부 다른 값을 가질 때 서로 다른 차의 개수가 최대가 될 것 같다. 이런 경우가 존재하는지 생각해보자.

특정 수의 배수로도 만들어보고, 소수들로만도 한번 해보고... 여러 숫자를 넣어가면서 규칙을 찾다보면 1, 2, 4, 8... 과 같은 등비수열에서 모든 쌍의 차가 다른 값을 가짐을 파악할 수 있다. 마침 문제에서 N도 최대 30으로 주었고, 2^30이 int의 최대값을 넘어가지 않으므로 2배씩 커지는 등비수열을 출력해주면 실례가 된다. 서로 다른 차의 개수의 최대값은 N(N-1) / 2, 실례는 공비를 2로 갖는 등비수열을 출력해주면 된다.

서로 다른 차의 개수가 최소가 되는 경우는 언제인가? 여러가지 수를 넣어보면서 규칙을 찾다 보면 1, 2, 3, 4... 나 2, 4, 6, 8... 과 같은 등차수열에서 서로 다른 차의 개수가 N-1개로 가장 적어보인다. 다른 숫자 쌍을 넣어봐도 N-1개 보다 줄어드는 경우는 나타나지 않는다. 따라서 서로 다른 차의 개수의 최소값은 N-1, 실례는 임의의 공차를 갖는 등차수열을 출력하면 문제가 풀릴 것 같다.

실제로 코드를 작성하니 문제가 해결되었다.

소스 코드

import sys

N = int(sys.stdin.readline())
print(N*(N-1) // 2)
number = 1
for _ in range(N):
    print(number, end=' ')
    number *= 2
print()
print(N-1)
number = 1
for _ in range(N):
    print(number, end=' ')
    number += 1

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

풀이 과정

시작점과 도착점, 그리고 각 내비게이션마다 방문해야 하는 중간점 정보를 담고 있을 때, 중간점을 모두 방문하고 도착점에 도착하는 거리가 가장 짧은, 가장 좋은 내비게이션이 무엇인지 구하는 문제이다.

그냥 문제가 시키는대로 구현하면 된다. 각 내비게이션마다 시작점 -> 중간점들 -> 도착점 경로의 맨해튼 거리를 모두 구해주고 그 중 가장 작은 거리를 안내하는 내비게이션의 번호를 출력하면 된다.

소스 코드

import sys


def manhatton(a, b, c, d):
    return abs(a-c) + abs(b-d)


N = int(sys.stdin.readline())
sx, sy, ex, ey = map(int, sys.stdin.readline().split())
answer = []
for _ in range(N):
    distance = 0
    now_x, now_y = sx, sy
    Mi = int(sys.stdin.readline())
    for _ in range(Mi):
        next_x, next_y = map(int, sys.stdin.readline().split())
        distance += manhatton(now_x, now_y, next_x, next_y)
        now_x, now_y = next_x, next_y
    distance += manhatton(now_x, now_y, ex, ey)
    answer.append(distance)

answer_index = 0
min_answer = min(answer)

for index, value in enumerate(answer):
    if value == min_answer:
        min_answer = value
        answer_index = index + 1

print(answer_index)

https://leetcode.com/problems/minimum-distance-between-bst-nodes/

풀이 과정

이진 탐색 트리의 임의의 두 노드의 차의 최소값을 구하는 문제이다.

이진 탐색 트리의 특성상 특정 노드의 왼쪽 서브트리에는 자신보다 작은 노드 값을 가진 노드들만이 존재하고, 오른쪽 서브트리에는 큰 노드 값을 가진 노드들만이 존재한다.

자신보다 작으면서 차이는 가장 적은 노드 값을 찾으려면 어느 노드에 방문해야 할까? 왼쪽 자식 노드로 한번 이동해서, (자신보다 작은 노드 값들 중에서) 가능한 오른쪽으로 쭉 이동하면, (그 중에서 가장 큰 노드 값으로 가면) 원하는 노드 값을 찾을 수 있다.

마찬가지로, 자신보다 크면서 차이는 가장 적은 노드 값을 찾으려면 오른쪽 자식 노드로 한번 이동 후. 가능한 왼쪽 자식 노드로 쭉 이동하면 원하는 노드 값을 찾을 수 있다.

트리의 3가지 순회 방법중, 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문하는 중위 순회를 이용해 순회하고, 현재 노드를 순회하기 전에 방문했던 노드 값을 저장하고 있는 변수를 두면 모든 노드에서 자신보다 작거나, 크면서 차이가 가장 적은 노드 값과 자신의 노드 값과의 차를 구할 수 있고, 그 중 가장 작은 값을 정답으로 반환해주면 된다.

[10, 5, 15, 3, 7, 11, 17]을 노드 값으로 가지고 있는 이진 탐색 트리의 예시 그림이다. 중위 순회의 방문 순서를 같이 표시하였는데, 특정 노드에서 왼쪽 -> 오른쪽 쭉.... 의 노드와 오른쪽 -> 왼쪽 쭉....의 노드 방문 순서가 1씩 나므로, 현재 노드 값 - 이전 방문 노드 값을 모든 노드에서 구해주면 임의의 두 노드의 차 중 가장 작은 값을 확인할 수 있다.

소스 코드

class Solution:
    answer = sys.maxsize
    prev = -sys.maxsize
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        if root.left:
            self.minDiffInBST(root.left)
        self.answer = min(self.answer, root.val - self.prev)
        self.prev = root.val
        if root.right:
            self.minDiffInBST(root.right)
        return self.answer

https://leetcode.com/problems/range-sum-of-bst/

풀이 과정

이진 탐색 트리에서 low <= node.val <= high인 노드의 합을 구하는 문제이다.

이진 탐색 트리의 특성상 어떤 노드의 왼쪽 서브 트리에는 더 작은 노드 값을 가지고 있는 노드들만, 오른쪽 서브 트리에는 더 큰 노드 값을 가지고 있는 노드들만 존재한다.

루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 전위 순회 방법으로 문제를 해결하였다.

현재 순회중인 노드 값이 low 보다 낮다면, 이진 탐색 트리의 특성상 왼쪽 서브 트리에 있는 노드들은 low보다 작은 값을 가질 것이므로, 순회할 필요가 없고, 현재 순회중인 노드 값이 high보다 크다면, 오른쪽 서브 트리에 있는 노드들은 high보다 큰 값을 가질 것이므로 마찬가지로 순회할 필요가 없다.

위와 같은 특성을 이용하면 풀이 시간이 줄어들지만, 그냥 모든 노드를 다 탐색해도 시간 초과가 발생하지는 않는 문제였다.

소스 코드

class Solution:
    sum = 0
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return None
        if low <= root.val <= high:
            self.sum += root.val
            self.rangeSumBST(root.left, low, high)
            self.rangeSumBST(root.right, low, high)
        elif root.val < low:
            self.rangeSumBST(root.right, low, high)
        elif high < root.val:
            self.rangeSumBST(root.left, low, high)
        return self.sum

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

풀이 과정

이진 탐색 트리를 Greater Sum Tree로 바꿔야 한다. Greater Sum Tree의 각 노드 값은, 기존 이진 탐색 트리에서 자신보다 큰 값을 가진 노드 값들의 합이다.

문제의 예시를 보면 파란색 글씨로 써져있는 Greater Sum Tree의 각 노드 값이, 기존 이진 탐색 트리의 각 노드에서 자신보다 더 큰 값을 가진 노드 값들의 합을 값으로 가지고 있음을 확인할 수 있다.

트리의 순회 3가지를 떠올려보자.

1. 전위 순회

루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리

2. 중위 순회

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트

3. 후위 순회

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트

이 문제는 중위 순회 과정을 살짝 바꾸어 오른쪽 서브 트리 -> 루트 -> 왼쪽 서브 트리 순으로 순회하게끔 하고 값을 누적해나가면 해결할 수 있다.

소스 코드

class Solution:
    val = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root:
            self.bstToGst(root.right)
            self.val += root.val
            root.val = self.val
            self.bstToGst(root.left)
        return root

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

풀이 과정

정렬된 배열을 이진 탐색 트리로 변환하는 문제이다.

재귀를 사용해 divide-conquer 방식으로 절반씩 분할해가면서 문제를 해결하였다.

소스 코드

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) // 2
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid+1:])
        return node

https://leetcode.com/problems/minimum-height-trees/

풀이 과정

트리간의 연결 관계가 주어지는데, 어떤 노드를 root로 삼아야 가장 높이가 낮은 트리를 구성할 수 있는지 묻는 문제이다.

남은 노드가 2개 이하가 될 때 까지, 리프 노드를 제거해가면서 문제를 해결하였다.

소스 코드

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 1:
            return [0]
        
        graph = collections.defaultdict(list)
        for s, d in edges:
            graph[s].append(d)
            graph[d].append(s)
            
        leaves = []
        
        for s in graph:
            if len(graph[s]) == 1:
                leaves.append(s)
        
        while n > 2:
            n -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                neigh = graph[leaf].pop()
                graph[neigh].remove(leaf)
                if len(graph[neigh]) == 1:
                    new_leaves.append(neigh)
            leaves = new_leaves
        
        return leaves

https://leetcode.com/problems/balanced-binary-tree/

풀이 과정

주어진 이진 트리가 균형잡힌 이진 트리인지 확인하는 문제이다.

균형잡힌 이진 트리란, 모든 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이가 2보다 작은 이진 트리를 의미한다.

재귀를 활용해 리프 노드를 탐색하고, 리프 노드에서 현재 노드까지의 거리를 기록하게끔 코드를 작성하였다. 현재 노드에서 왼쪽 자식을 통해 탐색 가능한 리프 노드까지와의 거리와, 오른쪽 자식을 통해 탐색 가능한 리프 노드까지의 거리가 1 이상 차이가 나는 노드가 존재하면, 그 트리는 균형잡힌 이진 트리가 아니다.

소스 코드

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(root):
            if not root:
                return 0
            
            left = check(root.left)
            right = check(root.right)
            
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return max(left, right) + 1
        
        return check(root) != -1