그냥 코딩하는 사람의 블로그

문제 설명

You are given an array of k linked-listslists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input:

• lists = [[1,4,5],[1,3,4],[2,6]]

Output:

• [1,1,2,3,4,4,5,6]

Explanation:

• The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2:

Input:

• lists = []

Output:

• []

Example 3:

Input:

• lists = [[]]

Output:

• []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]is sorted inascending order.
• The sum oflists[i].lengthwon't exceed10^4.

풀이 과정

• 문제는 k개의 linked-list가 주어질때, 모든 linked-list를 통합하여 하나의 리스트로 만듬(오름차순으로)

1. 리스트의 모든 요소들을 최소 히프에 넣는다
   • 히프의 특성에 의해 나중에 히프에서 빼줄때 정렬되어서 나올 예정
2. 히프에서 요소를 하나씩 꺼내서, 연결 그래프의 노드로 만들어준 다음 연결 그래프의 맨 마지막 노드의 링크에 넣어준다.
   • linked list 구성하기 위해 루트는 따로 저장해 두고, 맨 마지막을 가리키는 변수 따로 지정
3. 루트 노드를 리턴해주면 된다.

소스 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        answer = []

        for l in lists:
            temp = l
            while temp != None:
                heapq.heappush(heap, temp.val)
                temp = temp.next

        root = ListNode()
        prev = root

        while heap:
            t = heapq.heappop(heap)
            temp = ListNode(val=t, next=None)
            prev.next = temp
            prev = temp

        root = root.next

        return root

풀이 과정

1. 열별로 진행한다.
   • 최저점인 행, 최고점인 행, 최저점인 인원 수, 최고점인 인원 수를 구한다.
2. 평균 계산
   • 최저점이거나 최고점인 행이 현재 진행중인 열과 같고(자기 자신이 낸 점수)
   • 유일한 인원인지 검사 필요 !! ( 최고점/최저점 인원수가 1인지 )
   • 해당 점수는 빼주고, 인원수도 1 줄여준다.
   • 이후, 평균을 계산하고 평균에 따라 학점을 매겨주면 된다.

• 구현 문제는 너무 복잡한거 같다..

소스 코드

def solution(scores):
    answer = ''
    for j in range(len(scores[0])):
        min_idx = 0
        max_idx = 0
        min_count = 1
        max_count = 1
        score_sum = scores[0][j]
        for i in range(1, len(scores)):
            # 최저점인지 검사
            if scores[i][j] <= scores[min_idx][j]:
                # 최저점이면서 동일한 점수가 있다면 인원수 증가
                if scores[i][j] == scores[min_idx][j]:
                    min_idx = i if i == j else min_idx
                    min_count += 1
                else:
                    min_idx = i
                    min_count = 1

            # 최고점인지 검사
            if scores[i][j] >= scores[max_idx][j]:
                # 최고점이면서 동일한 점수가 있다면 인원수 증가
                if scores[i][j] == scores[max_idx][j]:
                    max_idx = i if i == j else max_idx
                    max_count += 1
                else:
                    max_idx = i
                    max_count = 1

            score_sum += scores[i][j]

        # 점수 계산 파트( 자기가 낸 점수가 유일한 최고점, 최저점이라면 빼고 계산 )
        total_student = len(scores)
        if (min_idx == j and min_count == 1) or (max_idx == j and max_count == 1):
            p = min_idx if min_idx == j else max_idx
            total_student -= 1
            score_sum -= scores[p][j]

        avg = score_sum / total_student

        if avg >= 90: answer += 'A'
        elif avg >= 80: answer += 'B'
        elif avg >= 70: answer += 'C'
        elif avg >= 50: answer += 'D'
        else: answer += 'F'

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

• 문자열의 길이가 최대 50글자까지밖에 되지 않으므로..
  • zero ~ nine까지 모든 문자열이 전체 문자열 s에 있는지 검사
  • 있다면, 해당 문자열을 replace 해주면 된다.

소스 코드

def solution(s):
    string_dict = {'zero': 0, 'one': 1, 'two': 2, 'three': 3,
                  'four': 4, 'five': 5, 'six': 6, 'seven': 7,
                  'eight': 8, 'nine': 9}    
    answer = 0
    for string in string_dict.keys():
        if string in s:
            s = s.replace(string, str(string_dict[string]))
    answer = int(s)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

풀이 과정

1. 이전에 나타나지 않은 인원의 경우 딕셔너리에 넣어준다.
   • 딕셔너리에 넣어주면서 parent 설정, 인원수 1명(자기 자신) 설정
2. 입력받은 두명의 그룹을 합친다.
   • 이 때, 두명이 속한 그룹의 인원수도 같이 합쳐주어야 함.
   • 인원수를 따로 구하려고 하면 시간 초과가 나온다.
3. 매 과정마다 그룹 내의 인원수를 출력해준다.

• 처음에는 인원수를 따로 for문으로 구하려고 했는데 시간초과가 나옴..
• 처음 시간초과가 났을 때는 차라리 set을 사용해서 구현하는 것이 더 편할거 같았으나..
  Union-Find로 통과받아보고 싶어서 매달림,,

소스 코드

import sys
input = sys.stdin.readline

total_case = int(input().rstrip())

def find(parent, group, a):
    if parent[a] != a:
        parent[a] = find(parent, group, parent[a])
        group[a] = group[parent[a]]
    return parent[a]

def union(parent, group, a, b):
    p1 = find(parent, group, a)
    p2 = find(parent, group, b)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

for i in range(total_case):
    F = int(input().rstrip())
    member = dict()
    count = 0
    parent = [-1] * 200001
    group = [0] * 200001
    for _ in range(F):
        person1, person2 = input().rstrip().split()

        # 새로운 멤버 추가
        if member.get(person1) == None:
            parent[count] = count
            member[person1] = count
            group[count] = 1
            count += 1
        if member.get(person2) == None:
            parent[count] = count
            member[person2] = count
            group[count] = 1
            count += 1

        # 두 그룹 합침
        par1 = find(parent, group, member[person1])
        par2 = find(parent, group, member[person2])
        if par1 != par2:
            union(parent, group, par1, par2)
            # 그룹 인원수 합침
            temp = group[par1] + group[par2]
            group[par1] = temp
            group[par2] = temp

        # 위 과정에서는 부모의 그룹 인원수만 바뀌므로   
        # find 한번 더 호출해서 자식들의 그룹 멤버 수가 부모의 그룹 인원수가 되도록 조정
        find(parent, group, member[person1])
        find(parent, group, member[person2])

        group_count = group[member[person1]]
        print(group_count)

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서가능한 한 최대의총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한정수상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

풀이 과정

1. 범위를 0 ~ 예산요청의 최댓값으로 잡고 이분 탐색 진행
   • 중간값을 기준으로 예산 배정이 성공적으로 이루어지면 최댓값을 구해야 하므로 예산을 더 늘려보아야 한다. 따라서 저장 후 오른쪽 구간 (중간값+1 ~ )
   • 중간값을 기준으로 예산 배정이 성공적으로 이루어지지 않았다면 예산을 줄여야 하므로 왼쪽 구간 ( ~ 중간값-1)
2. 예산 배정 과정
   • 배정된 예산 > 예산요청 => 예산 요청
   • 배정된 예산 < 예산요청 => 배정된 예산
   • if문 작성에 유의

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
lists = list(map(int, input().rstrip().split()))
M = int(input().rstrip())

left = 0
right = max(lists)
answer = 0
while left <= right:
    mid = (left + right) // 2
    total = M
    succeed = True
    for k in lists:
        if (total < mid and k >= mid) or (
            total < k and k < mid ):
            succeed = False
        if succeed:
            if k < mid: # 현재 값보다 리스트 요소가 작으면 k만큼 빼줌
                total -= k
            else: # 현재 값보다 리스트 요소가 크면 현재 값만큼 빼줌
                total -= mid
        else:
            break

    if succeed:
        answer = mid
        left = mid+1
    else:
        right = mid-1

print(answer)    

문제 설명

문제

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다.

출력

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

풀이 과정

• 문제지 분류에는 Union-Find로 나와 있는데, BFS로 푸는게 더 쉬울거 같아서 BFS로 풀이함.

1. 현재 기준 방문하지 않았으면서 비용이 가장 짧은 학생을 선택한 후, 연결된 모든 학생들을 BFS로 탐색
   • BFS로 탐색하면서 방문 처리 모두 해두어야 함.
2. 진행하다가 비용의 합계가 k보다 크다면 "Oh no" 출력
3. 모든 학생들이 방문 처리 되었다면 비용의 합계 출력

소스 코드

import sys
from collections import deque

input = sys.stdin.readline
N, M, k = map(int, input().rstrip().split())

costs = [0] + list(map(int, input().rstrip().split()))
visited = [False] * len(costs)

graph = [[] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

def get_min_cost(costs, visited):
    cost = int(10e9)
    idx = -1
    for i in range(1, len(costs)):
        if not visited[i] and cost > costs[i]:
            cost = costs[i]
            idx = i

    return (cost, idx)
total = 0
while True:
    cost, idx = get_min_cost(costs, visited)
    if idx == -1:
        print(total)
        sys.exit(0)

    total += cost

    if total > k:
        print("Oh no")
        sys.exit(0)

    queue = deque([idx])
    visited[idx] = True
    while queue:
        node = queue.popleft()
        for g in graph[node]:
            if not visited[g]:
                queue.append(g)
                visited[g] = True

문제 설명

문제

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

[그림]

자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.

Tn= 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1+ T2
• 5 = T1+ T1+ T2
• 6 = T2+ T2or 6 = T3
• 10 = T1+ T2+ T3or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

풀이 과정

1. 미리 삼각수를 1000까지 구해둔다. (입력 범위가 3~1000)이므로
2. 삼각수의 개수가 많지 않으므로 3중 반복문으로 모든 경우의 수를 구해준다.
   • i + j + k가 입력받은 값인지 검사
   • 그나마 조금이라도 효율성 높이기 위해 i, j, k 각각이 입력받은 값보다 크면 continue
3. i + j + k가 입력받은 값이 된다면 1, 되지 않는다면 0 출력

소스 코드

import sys

start = 1
add = 2
Triangle = []
while True:
    Triangle.append(start)
    start += add
    add += 1
    if start >= 1000:
        break

def check(a, Triangle):
    for i in Triangle:
        if i >= a: continue
        for j in Triangle:
            if j >= a: continue
            for k in Triangle:
                if k >= a: continue
                if i + j + k == a:
                    return True

    return False


count = int(sys.stdin.readline().rstrip())
for i in range(count):
    n = int(sys.stdin.readline().rstrip())
    if check(n, Triangle):
        print(1)
    else:
        print(0)

문제 설명

문제

올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

한 학기에 들을 수 있는 과목 수에는 제한이 없다.
모든 과목은 매 학기 항상 개설된다.
모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.

입력

첫 번째 줄에 과목의 수 N(1≤N≤1000)과 선수 조건의 수 M(0≤M≤500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A<B인 입력만 주어진다. (1≤A<B≤N)

출력

1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.

풀이 과정

1. 위상 정렬 알고리즘 사용
   • 진입 차수가 0인 노드들을 방문한다.
   • 진입 차수가 0인 노드에 연결된 간선을 제거해준다.
   • 간선 제거로 인해 진입차수가 0이 되는 노드들을 다음에 방문한다.
2. 위 알고리즘 과정이 선수과목과 같음.
   • 자바1 -> 자바2를 들어야 한다고 가정
   • 자바1의 진입 차수는 0이고, 자바2의 진입 차수는 1이므로 자바1 먼저 방문하고, 자바2를 방문하여야 함.
3. 큐에 노드 뿐만 아니라 학기도 같이 저장하여 준 다음, 방문 시 각 과목의 학기를 따로 저장

풀이 과정

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)
semester = [0] * (N+1)
queue = deque()


for _ in range(M):
    src, dest = map(int, input().rstrip().split())
    graph[src].append(dest)
    indegree[dest] += 1

# 초기 진입차수가 0인 노드 등록 
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append([i, 1])

while queue:
    cur, sem = queue.popleft()
    semester[cur] = sem
    for n in graph[cur]:
        indegree[n] -= 1
        # 진입차수가 0이 되면 들을수 있는 과목이므로 넣어준다.
        if indegree[n] == 0:
            queue.append([n, sem+1])

print(*semester[1:])

풀이 과정

1. 위 그림을 보면 바깥쪽 삼각형을 채우고, 안쪽 삼각형을 채우는 구조로 볼 수 있다.
2. 삼각형을 채울 때는, 맨 위 시작점을 기준 3가지 과정을 거친다.
   1. 아래로 이동
   2. 우측으로 이동
   3. 왼쪽 위 대각선으로 이동
3. 시작점을 조정해 가면서 2번 과정을 거치면 된다.
   • 시작점의 경우 (0, 0), (2, 1), ... (2n, n)
4. 종료 조건은 모든 삼각형을 채운 경우이다.

소스 코드

def solution(n):
    lists = [[0] * i for i in range(1, n+1)]
    idx = 1
    i = 0
    while True:
        x = 2 * i
        y = i
        i += 1

        # 아래 내려가는 부분
        while x < n and lists[x][y] == 0:
            lists[x][y] = idx
            x += 1
            idx += 1
        x -= 1

        # 오른쪽 진행
        y += 1
        while y < x+1 and lists[x][y] == 0:
            lists[x][y] = idx
            y += 1
            idx += 1
        y -= 1

        # 대각선 왼쪽 위 진행
        x -= 1; y -= 1
        while lists[x][y] == 0:
            lists[x][y] = idx
            x -= 1
            y -= 1
            idx += 1

        # 전체 체크
        end = True
        for l in lists:
            for e in l:
                if e == 0:
                    end = False
                    break
            if not end:
                break

        if end:
            break

    answer = []

    # 정답 저장
    for l in lists:
        for e in l:
            answer.append(e)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

Given therootof a binary tree,determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keysless thanthe node's key.
• The right subtree of a node contains only nodes with keysgreater thanthe node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3] Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

• The number of nodes in the tree is in the range[1, 104].
• -231<= Node.val <= 231- 1

풀이 과정

1. 처음엔 부모 노드 기준으로 왼쪽, 오른쪽 노드의 값을 검사하는 방식으로만 진행
   • 트리의 깊이가 깊어지면 틀림.
   • 루트 노드 기준으로 .. 왼쪽 서브 트리의 모든 값은 루트 노드보다 작아야 되고, 오른쪽 서브 트리의 모든 값은 루트 노드보다 커야 함.
2. 따라서, 범위를 기준으로 Validate 진행
   • 초기 범위를 -2의 32승 ~ 2의 32승으로 두고
   • 현재 노드의 값이 범위 내에 들어있는지 검사(들어있지 않다면 False)
   • 현재 노드의 값이 범위 내에 들어있으면 자식 노드들 방문
     • 방문할 때, 범위 조절해주어야 함. 현재 범위가 (a ~ b)라면
     • 왼쪽 방문할 때는 (a ~ 현재 노드의 값)
     • 오른쪽 방문할 때는 (현재 노드의 값 ~ b)
3. 모든 노드들에 대해 조건 만족하는 경우 이진 트리이므로 True, 아니면 False 리턴

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        flag = False
        def validate(root, fr, to):
            if root == None:
                return True

            if fr < root.val and root.val < to:
                return validate(root.left, fr, root.val) and validate(root.right, root.val, to)
            else:
                return False

        return validate(root, -2**32, 2**32)