231110 LeetCode 문제 풀이 (그래프, 인접 행렬)

1743. Restore the Array From Adjacent Pairs

https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/?envType=daily-question&envId=2023-11-10

 

1) 문제 설명

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

 

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]

 

2) 제한 사항

• nums.length == n
• adjacentPairs.length == n - 1
• adjacentPairs[i].length == 2
• 2 <= n <= 105
• -105 <= nums[i], ui, vi <= 105
• There exists some nums that has adjacentPairs as its pairs.

 

3) 도전 과제

X

 

4) 풀이

처음 주어진 adjacentPairs를 순회하여 그래프를 만든 후, 해당 그래프를 순회하는 방식으로 접근하려 하였다.

그래프는 hashMap을 통해 구현하였고, 그래프의 각 끝 점을 구하기 위해 set을 사용하였다.

 

풀긴 풀었는데 시간도 오래 걸리고 메모리도 많이 사용한 걸 보니 좋은 접근 방법은 아니었던 것 같다...

 

다른 사람들의 풀이를 보며 어떻게 개선할 지 찾아보자.

 

5) 소스 코드 및 결과

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        // Map에 그래프 정보 보관, Set으로 양 끝 값 확인
        HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>();
        HashSet<Integer> hashSet = new HashSet<>();

        // 그래프 만들기
        for (int[] pair : adjacentPairs) {
            int num1 = pair[0];
            int num2 = pair[1];

            putOrRemove(num1, hashSet);
            putOrRemove(num2, hashSet);

            addOrPut(num1, num2, hashMap);
            addOrPut(num2, num1, hashMap);
        }

        // 배열 만들고 양 끝 값 채우기
        int length = adjacentPairs.length+1;
        int[] result = new int[length];

        Object[] setArray = hashSet.toArray();

        int start = (int) setArray[0];
        int end = (int) setArray[1];

        result[0] = start;
        result[length-1] = end;

        // 배열 채우기
        int count = 1;
        int prev = start;
        ArrayList<Integer> valueList = hashMap.get(start);
        int value = valueList.get(0);

        while(count<length-1){
            result[count] = value;
            ArrayList<Integer> newValueList = hashMap.get(value);
            newValueList.remove(Integer.valueOf(prev));
            int newValue = newValueList.get(0);

            prev = value;
            value = newValue;
            count++;
        }

        return result;
    }

    private void putOrRemove(int num, HashSet<Integer> set){
        if (set.contains(num)) {
            set.remove(num);
        } else {
            set.add(num);
        }
    }

    private void addOrPut(int key, int valueInt, HashMap<Integer, ArrayList<Integer>> map){
        if (map.containsKey(key)) {
            ArrayList<Integer> valueList = map.get(key);
            valueList.add(valueInt);
        } else {
            ArrayList<Integer> valueList = new ArrayList<>();
            valueList.add(valueInt);

            map.put(key, valueList);
        }
    }
}

 

 

6) 다른 사람의 풀이

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int[] pair : adjacentPairs) {
            graph.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
            graph.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);
        }

        List<Integer> result = new ArrayList<>();

        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
            if (entry.getValue().size() == 1) {
                result.add(entry.getKey());
                result.add(entry.getValue().get(0));
                break;
            }
        }

        while (result.size() < adjacentPairs.length + 1) {
            int last = result.get(result.size() - 1);
            int prev = result.get(result.size() - 2);
            List<Integer> candidates = graph.get(last);
            int nextElement = candidates.get(0) != prev ? candidates.get(0) : candidates.get(1);
            result.add(nextElement);
        }

        return result.stream().mapToInt(Integer::intValue).toArray();        
    }
}