[알고리즘_기초] 2. 동명이인 구하기,중복값 찾기 (Python,Java)

동명이인 구하기, 같은 값 찾기 ,중복 값 찾기 ...등등 같은 말입니다.

입력 예시는 "Tom", "Jerry", "Mike", "Tom" 입니다! 

분석은 코드 아래에 있습니다!

<Find_Same_name.py>

def find_Same_Name(names):
    result = set()
    n = len(names)
    for i in range(0,n-1):
        for j in range(i+1,n):
            if names[i] == names[j]:
                result.add(names[i])
    return result

names = ["Tom","Jerry","Mike","Tom"]

print(find_Same_Name(names))

 

<Find_Same_name.java>

public class Find_same_name2 {
    public static void main(String[] args) {
        String[] names = {"Tom", "Jerry", "Mike", "Tom"};
        find_same_name(names);
    }

    private static void find_same_name(String[] names) {
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < names.length - 1; i++) {
            for (int j = i+1; j < names.length; j++) {
                if (names[i] == names[j]) {
                    result.add(names[i]);
                }
            }
        }
        System.out.println(result);
    }
}

 

[알고리즘 분석]

경우의 수 구 하는 방식과 아주 유사합니다.

ex) 사람 A,B,C,D가 있다. 두명씩 짝이 될 경우의 수를 구하시오.

(A,B) (A,C), (A,D), (B,C),(B,D), (C,D)  ==>총6가지

A 다음에 위치한 B와 짝이 될 수 있고 

B 다음인 C와 짝이 될 수 있고.. 

C 다음인 D와 짝이 될 수 있습니다. 이렇게 A, B, C를 기준으로 짝을 짓게 되면 D는 이미 누구와 짝이 되었으므로 D를 기준 짝을 안찾아도 됩니다.

중복 값 찾는것도 이와 같이

첫번째 "Tom" 과  두번째  "Jerry" 와 비교를 하여 같으면 동명이인 배열에 추가하고 그렇지 않으면 다음 사람으로 넘어갑니다.

  i                j 

  0   Tom   → 1  Jerry 

                → 2 Mike

                → 3 Tom   동명이인 배열에 추가!

    1  Jerry  → Mike

              → Tom

     2 Mike → Tom

 

 자바 코드는 다양하지만 제일 코드가 간결한것으로 선택했습니다