[Leetcode] Weekly Contest 312

contest : https://leetcode.com/contest/weekly-contest-312/

---

1. Sort the People (Easy, 3)

문제 : https://leetcode.com/contest/weekly-contest-312/problems/sort-the-people/

heights 배열로 {heights[index], index}를 요소를 가지는 배열을 만든 뒤 높이내림차순 정렬.

정렬된 배열을 앞에서부터  탐색하면서 names[index]를 정답에 차례대로 세팅

시간복잡도는 O(NlogN)

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/2418.%20Sort%20the%20People.cpp

---

2. Longest Subarray With Maximum Bitwise AND (Medium, 4)

문제 : https://leetcode.com/contest/weekly-contest-312/problems/longest-subarray-with-maximum-bitwise-and/

subarray의 모든요소들의 AND 연산한 결과의 최대값을 가지는 subarray의 최대길이를 구하라는데.

말을 어렵게 적어놨지 결국엔 가장 큰 요소값만을 가지는 subarray 중 가장 긴 길이를 구하는 문제다.

어떤 숫자 num을 어떠한 값과 AND 연산했을 때의 최대값은 num이 될 수 밖에 없기 때문이다. (AND 연산은 값을 같거나 작게 만든다.)

따라서 배열에서의 최대 요소 값을 구한뒤 해당 값만을 가지는 subarray들 중 최장길이를 구하면 된다.

시간복잡도는 O(N).

AND 연산결과가 값을 같거나 작게밖에 못 만든다. 라는 사고로 이어지기 까지 오래걸렸다.

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/2419.%20Longest%20Subarray%20With%20Maximum%20Bitwise%20AND.cpp

---

3. Find All Good Indices (Medium, 5)

문제 : https://leetcode.com/contest/weekly-contest-312/problems/find-all-good-indices/

앞에서부터 탐색하면서 nums[i-1] >= nums[i] 를 만족하는 연속 길이를 nonInc 배열에 저장하고

뒤에서부터 탐색하면서 nums[i] <= nums[i+1]을 만족하는 연속 길이를 nonDec 배열에 저장한다.

만약 인덱스 i 의  nonInc[i-1]가 k 보다 작거나 크고  nonDec[i+1]이 k보다 크거나 같다면 i는 정답이 될 수 있다.

ex) nums = [2, 1, 1, 1, 3, 4, 1], k = 2

index	0	1	2	3	4	5	6
nums[index]	2	1	1	1	3	4	1
nonInc[index]	1	2	3	4	1	1	2
nonDec[index]	1	5	4	3	2	1	1
정답가능?	X	X	O	O	X	X	X

시간복잡도는 O(N)

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/2420.%20Find%20All%20Good%20Indices.cpp

---

4. Number of Good Paths (Hard, 6)

문제 : https://leetcode.com/contest/weekly-contest-312/problems/number-of-good-paths/

 

결론만 말하자면 문제는 제한시간내에 못풀었다.

생각한 아이디어만 끄적여본다.

 

1 <= n <= 3 * 10^4

0 <= vals[i] <= 10^5

완탐은 택도 없을 것 같은 제한사항이다.

 

조건 두 가지.

1. 시작 노드와 종료 노드의 vals는 동일하다.

2. 중간에 방문하는 노드들은 시작 노드의 값보다 항상 작거나 같다.

 

조건 2번 때문에 가장 큰 노드들을 시작, 종료 노드로 하는 정답 가능 경로의 수를 구한뒤.

이번에 사용한 노드는 이후에 탐색하는 경로에 포함될 수 없으므로 연결된 간선을 다 제거한다.

[그림 1]

[그림 2]

[그림 3]

그러면 마지막엔 [그림 3]처럼 되고 0번 노드와 3번 노드는 서로 다른 그룹안에 있으므로 이동할 경로가 없어서 정답에 포함될 수 없다.

이런 그룹핑, 집합 하면 DSU (Union-Find) 가 생각나는데 그룹하나로 묶었다가.. 제거를 어떻게 하지..? 에서 막혔다.

거꾸로 생각해보면 되려나

 

여기서 타임아웃.

좀 더 생각해보고.. 모르겠으면 토론글 정주행 해야겠다.

 

+ 22.09.26

Union-Find로 풀었다.

아이디어는 완성된 트리부터 큰 노드의 간선들을 끊어나가는 건데

이걸 반대로 작은 숫자의 노드들의 간선부터 연결해나간다.

연결된 정점들을 하나의 집합으로 묶은 뒤, 같은 집합에 있는 노드들을 연결할 수 있는 경우의 수를 정답에 더한다.

시간복잡도는 O(NlogN).

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/2421.%20Number%20of%20Good%20Paths.cpp