문제 링크 https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ 조건 트리가 가지고 있는 노드의 갯수 [0, 2000]. -100 <= Node.val <= 100 입력값 root = Binary Tree의 루트 출력값 없음 = 기존 트리 내용만 pre-order traversal 순서대로 + right child만 가지도록 (flatten) 변환 풀이과정 leaf node 까지 traverse 한 후 left는 없애고 right 에는 이전 node를 넣어주고 prev에는 현재 node를 넣어주면서 밑에서부터 위로 traverse 진행 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/populating-next-right-pointers-in-each-node/ 조건 트리가 가지고 있는 node 갯수 [0, 2^12 - 1]. -1000 <= Node.val <= 1000 입력값 root = perfect Binary Tree의 루트 node의 구조 next pointe는 모두 NULL로 초기화 되어 있음 출력값 root = perfect Binary Tree의 루트 풀이과정 tree를 traverse 하면서 root가 null이거나 root.left 요소가 없는 경우 return root 에서 오른쪽에 node가 있으면 root.left.next에 해당 node를 넣어준다 현재 root 에 next가 있으면 root.right.next에 next의 왼쪽에 있는 node를 넣어주고 next가 없으면 null을 넣어준다 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/same-tree/ 조건 각 트리의 노드 갯수 [0, 100]. -10^4 <= Node.val <= 10^4 입력값 roots of two binary trees p and q 출력값 두 트리가 동일한 트리인가? (참/거짓) 풀이과정 JSON.stringify로 자바스크립트 객체를 문자열로 변환 후 비교 (shallow 비교만 가능함) 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/path-sum-ii/ 조건 트리가 가지고 있는 노드의 갯수 [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 입력값 root = Binary Tree의 루트 targetSum = 각 노드의 값을 합쳤을때 나와야 하는 값 출력값 2차원 배열 = root 에서 leaf 노드 까지의 path 풀이과정 tree를 preorder로 traverse하면서 현재 노드의 값을 배열에 넣고 sum 에 현재 노드의 값을 더한다 sum이 targetSum과 같고 leaf 노드인 경우 result에 결과 넣기 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/binary-tree-inorder-traversal/ 조건 노드의 갯수 [0, 100]. -100 <= Node.val <= 100 입력값 root = Binary Tree의 루트 출력값 inorder traversal 한 값들의 배열 풀이과정 왼쪽 -> 중간 -> 오른쪽 순서로 트리를 돌면됨 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/recover-binary-search-tree/ 조건 노드의 갯수 [2, 1000]. -2^31 <= Node.val <= 2^31 - 1 정확히 두 개의 노드의 값이 바뀌어진 상태 입력값 root = 바이너리 서치 트리 root 출력값 없음 (in place로 바이너리 서치 트리 값만 수정) 풀이과정 inorder traverse를 진행하면서 잘못된 위치의 노드를 first, second에 저장 traverse를 완료 후 first, second의 값을 swap 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/validate-binary-search-tree/ 조건 노드의 갯수 [1, 10^4]. -2^31 <= Node.val <= 2^31 - 1 valid BST 조건 -> 노드의 왼쪽 subtree는 node val 보다 작은 값 -> 노드의 오른쪽 subtree는 node val 보다 큰 값 -> 노드의 왼쪽, 오른쪽 subtree도 바이너리 서치 트리여야함 입력값 root = 바이너리 서치 트리의 루트 출력값 bool = 바이너리 서치 트리인지 참/거짓 값 풀이과정 현재 노드의 값이 min(이전 값 or 왼쪽 subtree의 최대값)과 max (이전 값 or 오른쪽 subtree의 최소값) 사이의 값이 아닌 경우 바이너리 서치 트리가 아님 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/diameter-of-binary-tree/ 조건 The number of nodes in the tree is in the range [1, 10^4]. -100 <= Node.val <= 100 입력값 root = binary tree의 루트 노드 출력값 트리의 diameter = 두 node 사이의 가장 긴 거리 풀이과정 depth 값이 가장 큰 왼쪽, 오른쪽 child의 거리가 가장 큰 것이 diameter이다 dfs 방식으로 왼쪽, 오른쪽 child를 traverse 하면서 가장 큰 depth 값을 가진 왼쪽, 오른쪽 child를 찾는다 가장 큰 depth 값을 가진 왼쪽, 오른쪽 child의 depth를 합한 값이 현재 계산한 diameter 값보다 크다면 diameter 값을 업데이트 한다 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/move-zeroes/ 조건 1 <= nums.length <= 10^4 -2^31 <= nums[i] <= 2^31 - 1 입력값 nums = 그냥 배열 출력값 없음, nums 배열 요소의 위치들만 바꾸면됨 풀이과정 배열을 돌면서 0인 경우 해당 idx의 값을 삭제 후 배열의 맨 뒤에 0 을 넣어준다 delete로 삭제 하면 삭제된 idx의 값이 undefined로 바뀌기 때문에 배열을 돌면서 undefined인 경우 배열 요소를 삭제 해주었다 참고: 처음에 삭제할때 splice로 삭제한 후 나중에 삭제한 0의 갯수만큼 배열에 0을 추가해주는 방법도 있다 참고: 처음에 삭제할때 splice로 삭제하면서 동시에 0을 추가해 한개의 루프로 해결하려고 해봤는데 index값이 줄어 들기 때문에 삭제 후 index를 1 줄여주고 나니 무한루프에 빠졌었다 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/generate-parentheses/ 조건 1 <= n <= 8 입력값 n = 괄호의 pair 갯수 출력값 괄호짝이 맞는 combination을 배열에 넣어 출력 풀이과정 backtracking을 사용해 combination을 만든다 combination의 길이가 2*n인 경우 pair가 꽉 차있기 때문에 result에 결과를 넣어준다 왼쪽 괄호가 아직 n 개 만큼 없는 경우 왼쪽 괄호를 넣어준다 오른쪽 괄호가 아직 왼쪽 괄호의 갯수만큼 없다면 오른쪽 괄호를 넣어준다 이렇게 하면 괄호짝이 맞는 well-formed combination을 완성할 수 있다 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://leetcode.com/problems/first-bad-version/ 조건 1 <= bad <= n <= 2^31 - 1 bad version 이 후 version 들은 모두 bad version임 입력값 isBadVersion = 해당 숫자가 BadVersion인지 확인하는 함수 (true/false return함) - leetcode에서 제공되는 API n = 버전의 갯수 [1,…,n] 로 사용된다고 생각하면됨 출력값 버전 중에서 가장 작은 수를 가진 bad version 값 풀이과정 일반 루프를 사용해봤는데 time limit exceeded 에러 발생 (n의 값이 20억이 넘기 떼문) binary search를 사용해 20억번 확인할 것을 9번으로 줄임 현재 위치의 값이 bad version인 경우 이 후 version 들은 모두 bad version 이기 때문에 찾는 범위를 왼쪽으로 이동 현재 위치의 값이 bad version이 아닌 경우 이 …

문제 링크 https://leetcode.com/problems/rotate-array/ 조건 1 <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1 0 <= k <= 10^5 입력값 nums = 그냥 배열 k = 회전할 횟 수 출력값 없음, nums 배열 요소의 위치들만 바꾸면됨 풀이과정 처음에 nums.length <= 10^5 조건을 보지 않고 2중 루프로 구현해 time limit exceeded 에러가 발생했다 (다음부터는 조건 부분을 먼저 확인하자) 시간을 줄이기 위해 nums 배열을 복사한 후 해당 배열의 요소 값을 가져오는 방법을 사용했다 k를 nums의 길이와 나눈 나머지 값을 사용해 k가 nums.length보다 클때 제자리로 rotate 되는 부분을 제거한다 배열 뒷 요소부터 바꾸는 전략을 취했는데 어차피 복사한 배열에서 값을 가져오는 거라 순서는 상관 없었을듯 하다 아무튼 뒷 요소부터 i-k로 rotate 후 위치될 값…

문제 링크 https://leetcode.com/problems/search-insert-position/ 조건 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums는 오름차순으로 정렬되어 있음 -10^4 <= target <= 10^4 O(log n) 알고리즘 작성 입력값 nums = 오름차 순으로 정렬된 배열 target = 찾는 값 출력값 찾는 값이 있으면 해당 값의 index, 없으면 target이 오름차순으로 정렬했을때 들어가야할 index 위치 값 풀이과정 Binary search를 사용해 target의 index를 찾음 target이 있으면 index return 없는 경우 for 문을 돌면서 target이 들어갈만한 위치를 찾는다 코드 😊 문제 링크 조건 입력값 출력값 풀이과정 코드

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/92343 조건 루트 노드에는 항상 양이 있음 (answer 최소값 1) 늑대의 수가 양의 수보다 같거나 크면 모든 양을 잡아먹음 입력값 info = 각 노드에 양 (0) 이 있는지 늑대 (1) 가 있는지에 대한 정보 (배열) edges = 각 노드들의 연결 관계를 저장하고 있음 (2차원 배열) ([0,1] = 1은 0의 child 노드) 출력값 모을 수 있는 최대 양의 개수 풀이과정 DFS를 사용해 모든 경우의 수를 확인 한다 주어진 노드들의 연결 관계를 2차원 배열을 사용해 그래프 형태로 저장한다 각 노드들을 traverse 하면서 양의 수와 늑대의 수를 더한다 늑대의 수가 양의 수보다 같거나 크면 return 늑대의 수가 양의 수보다 작으면 최대 양의 수를 업데이트 한 후 현재 노드의 child 들을 다음에 확인할 노드 배열에 push 하고 현재 노드를 해당 배열에서 삭제한다…

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/92342 조건 k점 과녁에 한발이라도 더 많은 화살을 맞힌 선수가 k점을 가져감 k점 과녁에 아무도 화살을 맞히지 못하면 어느 누구도 k점을 가져가지 않음 입력값 info = 어피치가 맞힌 과녁 점수의 개수 (index 0 = 10점, … , index 10 = 0점) (배열) n = 라이언이 쏠 수 있는 화살의 개수 출력값 어떤 과녁 점수에 n 발의 화살을 맞춰야 하는지 10점부터 0점 까지 순서대로 배열에 담아 출력 (index 0 = 10점, … , index 10 = 0점) 모든 경우의 수를 확인 한 후에도 라이언과 어피치의 점수차가 같거나 어피치가 높은 경우 [-1] return 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 풀이과정 낮은 점수를 더 맞힌 경우를 찾아야 하기 때문에 index …

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/92341 조건 차량에 입차 내역만 있고 출차 내역이 없으면 23:59에 출차된 것 누적 주차 시간이 기본 시간 이하인 경우 -> 기본 요금 누적 주차 시간이 기본 시간을 초과한 경우 -> (기본요금 + 올림(누적시간 - 기본시간) / 단위시간) x 단위 요금) 입력값 fees = 주차 요금 항목 (배열) records = 자동차 입/출력 내역 (배열) 출력값 자동차 청구 주차 요금 (배열) 차량 번호가 작은 자동차 순서대로 담아야됨 풀이과정 Hashmap을 사용해 각 자동차에 대해 입차시간, 총 주차 시간을 저장 출차 내역이 없는 자동차들의 총 주차 시간을 계산하기 위해 입차, 출차를 동기화 하는 배열 사용 IN인 경우 입차시간을 업데이트 OUT인 경우 출차시간 - 입차시간을 계산해 총 주차 시간을 업데이트 출차 내역이 없는 자동차들의 총 주차 시간을 업데이트 모든 자동차의 총 …

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/92334 조건 한번에 한 유저를 신고 가능 → A유저가 B,C 유저를 동시에 신고할 수 없음 (신고한 내용은 ‘userA userB’ 형태를 가짐) 동일한 유저 신고 횟수는 1회로 처리 → A유저가 B유저를 두번 이상 신고해도 1번 신고한걸로 처리됨 신고 횟수 제한 없음 k번 이상 신고된 유저는 정지 → k가 2이고 A유저가 C유저를 신고했고 B유저도 C유저를 신고하면 C유저는 정지됨 신고된 모든 내용을 취합 후 신고한 유저들에게 정지 사실 이메일 보내짐 자기 자신을 신고할 수 없음 입력값 id_list = 모든 유저 아이디 목록 (배열) report = 유저가 신고한 내용 목록 (배열) 출력값 각 유저가 받은 정지 사실 이메일 갯수 목록 (배열) id_list에 담긴 id 순서대로 담아야됨 풀이과정 key, value 형태로 데이터를 저장하는 HashMap 사용 key에는 유저…