정현우 / 4기 2주차 / 3문제

[cookingTorch]

문제명 : 이차원 배열과 연산

시간 복잡도 : O(N^2 logN K) , 공간 복잡도 : O(N^2)

1. 풀이 과정

 - 88 ms
 - 구현
 - 숫자별 등장 횟수 class Count (num, cnt)
 - 배열 순회하면서 0이 아니면 해당 숫자의 cnt++
 - 처음 방문하는 숫자인 경우 Count 객체 temp 배열에 삽입
 - temp 정렬
 - temp에서 Count 하나씩, 최대 50개 꺼내면서
 - 배열 A에 num, cnt 삽입, cnt와 방문여부 초기화
 - 나머지 공간 0으로 초기화
 - 숫자가 들어있는 길이 = temp 크기 * 2
 - 열의 개수 = 행 최대 길이, 행의 개수 = 열 최대 길이

---

문제명 : 비밀 모임

시간 복잡도 : O(N^3) , 공간 복잡도 : O(N^2)

1. 풀이 과정

 - 200 ms
 - 플로이드-워셜
 - 모든 노드 간 최단 거리 생성 (플로이드-워셜)
 - 각 노드들로부터 친구가 존재하는 노드들까지의
 -   거리합이 최소인 노드

---

문제명 : 가장 가까운 공통 조상

시간 복잡도 : O(N) , 공간 복잡도 : O(N)

1. 풀이 과정

 - 168 ms
 - 트리
 - 첫 번째 노드에서 부모를 따라가면서 루트까지 방문 처리
 - 두 번째 노드에서 부모를 따라가다 방문 처리된 노드를 만나면
 -   해당 노드가 두 노드의 LCA

---