[정리] Top 100 Liked Questions - Easy (1)

1. Merge Two Binary Trees

 

- problem

: 두 개의 Tree가 들어올 때 merge하기

 

- input

: 각 Tree의 root-node

 

- strategy

: Tree 문제 -> recursion을 생각하자

: mergeTrees라는 주어진 작성 함수가 재귀의 대상이다

: Tree를 리턴할때는 root node를 리턴한다

: Tree의 Node는 value가 반드시 존재하고, left와 right를 정의해주어야 한다.

: sum node values up as the new value -> 새로 만드는 node의 value는 두개의 input node value의 합

: the NOT null node will be used as the node of the new tree-> 한쪽이 null일때는 null이 아닌 노드가 합

 

- solution

1) 경계값 제거: 한쪽 트리가 null이라면, null이 아닌 tree를 리턴해주기

2) 새로운 Node 정의: 두 Node의 value를 합쳐 새로운 Node 생성

3) 새로운 Node에 대한 left node 설정: left도 새로 node를 merge하는 것. 따라서 두 input node의 left node들끼리 재귀를 돌린다.

4) 새로운 Node에 대한 left node 설정: 두 input node의 right node들끼리 재귀를 돌린다.

5) 새로운 Node 리턴

 

-my answer

 

 

2. Maximum Depth of Binary Tree

 

- problem

: 트리가 주어졌을 때 최대 깊이 구하기

: 트리의 최대 깊이는 한개의 노드로부터 다른 노드까지의 거리가 최대인 거리를 말한다

 

- input

: root node 한개

 

- strategy

: Tree 문제 -> recursion을 생각하자

: maxDepth라는 주어진 작성 함수가 재귀의 대상이다

: 카데인 알고리즘을 생각해보자

 

- solution

1) 경계값 제외: root가 null이라면 최대길이는 0

2) root노드의 최대 깊이는 maxDepth(root)로 구한다.

3) 2에 대해 maxDepth(root)는 maxDepth(root.left)+1, maxDepth(root.right)+1 중 더 큰 값이 될 것이다 -> 재귀의 포인트

 

-my answer

 

3. Invert Binary Tree

 

- problem

: 주어진 트리를 대칭시켜라

 

- input

: root node 한개

 

- strategy

: Tree 문제 -> recursion을 생각하자

: invertTree라는 주어진 작성 함수가 재귀의 대상이다

 

- solution

1) 경계값 제외: root가 null이라면 invert해도 null

2) root노드의 left와 right를 맞바꾼다

3) root.left와 root.right를 기준으로 자식 노드들을 맞바꾼 값은 invertTree(root.left), invertTree(root.right)다.->재귀의 포인트

4) 최종적으로 root를 리턴한다.

 

-my answer

 

4. Single Number

 

- problem

: 짝수 갯수인 원소가 아닌 single number를 리턴해달라.

: single number는 홀수개 또는 1개만 있는 숫자다.

 

- input

: 배열

 

- strategy

: 2,4,6,8... 모두 짝수다 -> 모든 원소에 대한 정보를 일일이 index 배열에 관리할 수 없다

: 객체를 만들어 key-value를 이용하자

: Loop를 돌면서 key를 원소로 두고 한번 들르면 value를 true, 다시 들르면 false로 만들자

 

- solution

1) 기준 객체를 만들자

2) input 배열 Loop하면서 한번 들르면 index 객체 해당 key의 원소를 true, 다시 들르면 false로 만들자 -> if문을 이용하자

3) 이제 기준 객체를 Loop하면서 value가 true인 원소를 리턴한다 -> 이때 key,value를 모두 찍으면 돌려면 for ~ in...object.entries( ) 을 사용하자

 

-my answer

 

 

5. Reverse Linked List 

- problem

: Linked List를 뒤집어라

 

- input

: Linked List의 head node

 

- strategy

: Linked List는 Loop를 돌 때 index가 필요하다! 

: null-> 1(시작) -> 2 -> 3 -> 4-> 5 List가 5 -> 4 -> 3 -> 2 -> 1 -> null(끝)로 생각하자

: previous와 current 노드를 설정하자

 

- solution

1) current와 previous 기준을 만들자

2) Loop를 돌면서 next를 반대방향으로 바꾼다

3) 다 돌았으면(current가 없는 시점) previous를 리턴해준다

 

-my answer

 

6. Majority Element

 

- problem

: 과반수가 넘는 원소를 찾아라

: majority element는 배열에서 과반수가 넘는 갯수인 원소이다

 

- input

: 배열

 

- strategy

: 배열의 index로 카운팅을 이용하자

 

- solution

1) Loop를 돌면서 카운팅하고, 그것이 input 배열의 반을 넘으면 리턴한다

 

-my answer

 

7. Move Zero

- problem

: 원소가 0인 애는 맨 오른쪽으로 밀기

 

- input

: 배열

 

- strategy

: 배열의 맨 오른쪽으로 밀기 -> push

: 배열에서 제거하기 ->splice(0,1)

: 배열을 흐뜨리지 않고 Loop하고 싶다면 뒤부터 돌아라(조건이 괜찮다면)

 

- solution

1) Loop를 돌면서 카운팅하고, 그것이 0이면 splice해서 push 밀어넣는다

 

-my answer

 

8. Find All Numbers Disappeared in an Array

- problem

: 배열이 주어질 때, 1부터 배열의 크기까지 연속된 숫자 중 빠진 원소를 찾아라 

 

- input

: 배열

 

- strategy

: 집중을 잘하면 됨

: index배열을 만들어 연속된 수가 나올때마다 원소의 index 자리에 표시하고, 해당 원소를 리턴

 

- solution

1) 크기가 nums의 길이인 index 배열 생성

2) nums를 Loop로 돌면서 원소를 배열의 index로 취급해, 해당 배열이 없다면 표기해주기

3) 리턴할 배열을 하나 더 만듦

4) count를 만들어 리턴할 배열의 index를 기록

5) count를 올려가며 index 배열에 해당하는 원소가 없다면 '해당 원소의 index'를 push

(사실 4,5는 for문을 쓴다면 없어도 됨)

 

-my answer