[99클럽 코테 스터디] 24일차 TIL - Find Center of Star Graph

오늘의 학습 키워드

</> 그래프

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int findCenter(int[][] edges) {
        //중복 되지않는 전체 값
        Set<Integer> allValue = new HashSet<>();
        //중복 된 값
        Set<Integer> duplicates = new HashSet<>();

        //배열 전체 돌아보기
        for(int i = 0; i < edges.length; i++){
            //i번째 배열의 값의 수만큼 반복하기
            for(int j = 0; j < edges[i].length; j++){
                int value = edges[i][j];
                // 이미 있는 값이라면 중복 된 값으로 추가
                if(!allValue.add(value)){
                    duplicates.add(value);
                }
            }
        }
        //하나의 값이 들어있으므로 임의의 값 한개를 반환
        return duplicates.iterator().next();
    }
}

오늘의 회고

처음에는 문제를 보면서 어떤 규칙이 있을까에 대해서 많이 고민을 했다. 트리처럼 인접하는 값으로 풀어야 하는건가? 뭐 어떻게 해야하지 생각을 하다가, 그림과 같은 별 그래프에서 Input값을 보다보니 결국 전체 배열에서 전체적으로 중복되는 값들이 있구나 생각하고 2가지의 방법을 생각했다.

첫번째: 모든 배열을 비교해서 같은 값이 있다면 그 값을 int로 반환한다.
두번째: 여러개의 배열을 하나의 배열로 합치고 가장 개수가 많은 값을 반환한다.

이 부분에서 어떻게 비교를 하면 좋을까 생각을 하다가 HashSet이 중복되지 않는 요소를 저장한다는 것이 생각나서 사용하기로 했다.
검색해보니 주로 중복된 값을 제거하거나 존재 여부를 빠르게 확인할 때 사용된다는 말을 보고 맞다고 생각해 더 진행하였다.

일단 중복 값을 걸러내기 위해서 중복이 안된 모든 값을 넣어줄 Set을 하나 만들어주고 중복된 값을 담아줄 하나의 Set을 만들어 더 만들어 주었다.

Set<Integer> allValue = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();

값을 넣을 Set들을 모두 만들어 주었으니 이제 반복 순회하여 Set으로 들어갈 값들을 모두 처리해주었다.

for(int i = 0; i < edges.length; i++){
	for(int j = 0; j < edges[i].length; j++){
		int value = edges[i][j];
    	if(!allValue.add(value)){
    		duplicates.add(value);
        }
    }
}

이렇게 if를 사용하면 Set에 중복된 값이 들어가지 않는 것을 이용해 값이 없다면 duplicates로 추가되게 만들 수 있었다.

마지막으로는 duplicates의 값을 반환하는 부분이 많이 햇갈려 시간을 보냈는데 특정 위치의 값을 가져오는 방법은 없고 임의의 값을 가져오는 방법만 가능하다고 했다.

하지만 duplicates도 Set이기때문에 중복된 값이 한 종류인 이상 값이 하나만 들어 있을 수 밖에 없었다. 그래서 임의의 값에 직접 접근해 반환을 해주었다. iterator는 단일 요소일 경우에 단 하나의 요소를 반환하기 때문에 가능한 것 같다.

return duplicates.iterator().next();

하지만 그렇다면 next는 필요없지 않을까? 라고 생각했지만 반환되는 값이 int가 되지 못해서 오류가 생겼다.
그래서 그 값을 직접 반환하면 해결이 되지 않을까 해서 추가해서 해결하였다.

두번째 풀이

class Solution {
    public int findCenter(int[][] edges) {
        // 첫 번째 엣지의 두 노드
        int firstArray1 = edges[0][0];
        int firstArray2 = edges[0][1];
        
        // 두 번째 엣지의 두 노드
        int secondArray1 = edges[1][0];
        int secondArray2 = edges[1][1];
        
        // 첫 번째 엣지의 노드 중 하나가 두 번째 엣지와 연결된 경우
        if (firstArray1 == secondArray1 || firstArray1 == secondArray2) {
            return firstArray1;
        } else {
            return firstArray2;
        }
    }
}

두번째 풀이 회고

두번째 풀이는 전체를 비교해서 골라내는 것 보다 비교를 해서 중복된 값을 가져올 때 모든 경우에서 중복된 값이 있는거라면 앞에 있는 두 개만 비교를 해도 옮은 답이 나올텐데? 라는 생각에서 시작을 하였다. 그래서 2차원 배열의 2개 배열을 직접 확인해서 맞는 값만을 반환하기로 했다.

우선 첫 번째 배열의 2개의 값을 만든다.

int firstArray1 = edges[0][0];
int firstArray2 = edges[0][1];

똑같이 두 번째 배열의 값도 만들어준다.

int secondArray1 = edges[1][0];
int secondArray2 = edges[1][1];

직접 두 개의 배열의 값을 모두 만들어 주었으니 비교만 하면 되겠다.

if (firstArray1 == secondArray1 || firstArray1 == secondArray2) {
	return firstArray1;
} else {
	return firstArray2;
}

AI 코드리뷰

첫번째 코드

현재 코드의 장점

1. 간단한 로직:

   • 중복된 값을 찾기 위한 기본적인 로직이 간단하고 직관적입니다. HashSet을 사용하여 중복된 값을 효과적으로 추적합니다.

2. 중복된 값 찾기:

   • 중복된 값이 하나만 존재한다고 가정할 경우, duplicates.iterator().next()를 사용하여 중복된 값을 빠르게 반환할 수 있습니다.

3. 효율적인 Set 사용:

   • HashSet을 사용하여 중복 여부를 확인하고, 삽입 및 검색이 평균적으로 O(1) 시간 복잡도를 갖기 때문에 효율적입니다.

현재 코드의 단점

1. 중복된 값이 하나만 있다고 가정:

   • 현재 코드에서는 중복된 값이 하나만 존재한다고 가정하고 있습니다. 실제 문제에서는 여러 중복된 값이 있을 수 있습니다.

2. 중복된 값이 없을 경우:

   • 중복된 값이 없는 경우, 즉 duplicates가 비어 있는 경우 duplicates.iterator().next()를 호출하면 NoSuchElementException이 발생할 수 있습니다. 코드가 예외 상황을 처리하지 않습니다.

3. 메모리 사용:

   • HashSet을 두 개 사용하여 메모리를 두 배로 사용합니다. allValue와 duplicates 각각이 메모리를 차지합니다.

시간 복잡도

• 시간 복잡도:
  • HashSet에 값을 추가하거나 확인하는 작업은 평균적으로 O(1) 시간 복잡도를 가집니다.
  • 전체 배열을 순회하는 데는 O(N) 시간이 소요됩니다. 여기서 N은 edges의 총 요소 수입니다. 따라서, 전체 시간 복잡도는 O(N)입니다.

개선 제안

1. 중복된 값이 하나만 있다고 가정하지 않기:

   • 중복된 값이 여러 개 있을 수 있다는 것을 고려하여, duplicates가 비어 있거나 여러 값을 포함할 수 있는 경우를 처리해야 합니다.

2. 중복된 값이 없는 경우 처리:

   • 중복된 값이 없을 경우를 처리하기 위해, duplicates가 비어 있는지 확인하고 적절한 기본값을 반환하는 로직을 추가해야 합니다.

3. 메모리 사용 최적화:

   • 메모리 사용을 줄이기 위해 하나의 HashSet만 사용하고, 값이 중복되는 순간 해당 값을 직접 반환하는 방법을 고려할 수 있습니다.

4. 성능 개선:

   • 더 효율적인 접근 방식을 사용할 수 있으며, 중복된 값이 단 하나만 있을 경우, 데이터 구조나 알고리즘을 개선하여 성능을 더 향상시킬 수 있습니다.

두번째 코드

개선된 버전의 장점

1. 효율성:
   • 코드가 간결하고 빠릅니다. 단순히 두 개의 엣지를 비교하여 중심 노드를 결정하므로, 불필요한 반복이나 복잡한 데이터 구조를 사용하지 않습니다.
2. 시간 복잡도:
   • 코드가 항상 일정한 시간에 실행되며, 상수 시간 복잡도를 가집니다. 따라서 매우 빠릅니다.
3. 간결성:
   • 코드가 간결하고 이해하기 쉬우며, 불필요한 계산을 제거하여 명확하게 문제를 해결합니다.

개선된 버전의 단점

1. 제약 조건:
   • 이 코드는 특정 조건에서만 유효합니다. 특히, 입력 엣지가 항상 문제의 제약 조건을 만족한다고 가정하고 있습니다. 주어진 문제에서 엣지가 n개의 노드가 연결된 그래프를 구성하는 경우, 첫 번째와 두 번째 엣지를 비교하여 해결하는 접근 방법입니다.
2. 확장성 부족:
   • 이 방법은 그래프가 n개의 엣지를 가지는 일반적인 경우에는 적용되지 않습니다. 즉, 그래프가 복잡해지거나 엣지가 추가될 경우, 이 코드는 제대로 작동하지 않을 수 있습니다.
3. 입력 가정:
   • 입력 데이터가 항상 유효하며, 문제에서 정의한 조건을 충족한다고 가정하고 있습니다. 예를 들어, 엣지가 정확히 2개일 때만 작동하며, 더 많은 엣지가 있는 경우에는 잘못된 결과를 반환할 수 있습니다.

시간 복잡도

• 시간 복잡도: O(1)
  • 이 알고리즘은 항상 두 개의 엣지만 비교하므로, 입력의 크기에 관계없이 상수 시간에 실행됩니다.

내 생각에 단점의 경우 오늘 문제에서는 제약 조건 자체가 edges[i].length == 2이기 때문에 문제는 없다고 생각이 된다.

개선된 코드 제안

오늘 개선된 코드는 두 번째로 사용했던 풀이 방법과 같은 방법을 알려줘서 생략하였다. 나름 내 풀이가 맞게 잘 된거 같다고 생각돼서 뿌듯하기도 했다.

---

내일 공부할 것 :

• 자료구조와 알고리즘
  • 트리: 이진 트리, 이진 탐색 트리, AVL 트리 등.
  • 그래프 이론: 그래프의 기본 개념, DFS, BFS, 최단 경로 알고리즘 (Dijkstra, Bellman-Ford).

문제

https://leetcode.com/problems/find-center-of-star-graph/