[알고리즘] 동명이인 찾기
2 min readApr 5, 2020
- 리스트에서 동명이인을 찾아 집합으로 반환
- 배열의 각 요소를 서로 비교하여 같은 값이 발견될 경우 집합에 추가한다.
- 처음 제목만 보고 알고리즘을 짜기 시작했을 때 리스트를 반환했다. 집합은 중복값이 들어가지 않는 반면 리스트는 중복값도 들어간다. 그렇기 때문에 결과가 되는 리스트에 값을 추가할 때 값이 중복되어 들어가지 않는지도 확인하는 작업이 필요했다. 이것을 리스트로 반환하게 되면 중복값은 들어가지 않기때문에 더 효율이 높다. 또한 반복문을 중첩하여 사용하는데 첫번째 반복의 인덱스가 지나간 값도 중복으로 비교를 했다. 그럴필요가 없는 작업이다. 첫번째 반복의 인덱스 이후의 값을 두번째 반복의 시작으로 그것만 비교를 하면된다. 또한 같은 맥락에서 마지막값은 마지막값의 뒤에 비교할 값이 없고, 앞의 값들과는 비교가 끝났기 때문에 비교하지 않아도 된다.
- 처음 짠 알고리즘은 다음과 같다.
- python
def find_samething(a): s = [] n = len(a) for i in range(0, n-1): for j in range(1, n): if a[i] == a[j]: if i != j: if a[i] not in s: s.append(a[i]) return sdef find_samething_2(a): s = [] n = len(a) for i in range(0, n): print(a[i]) print(a.count(a[i])) if a.count(a[i]) > 1: if a[i] not in s: s.append(a[i]) return s- rust
fn find_samething(a: Vec<&str>) -> Vec<&str> { let mut s = vec![]; let n = a.len(); for i in 0..n-1 { for j in 1..n { if i != j { if a[i] == a[j] { if !s.contains(&a[i]) { s.push(a[i]); }; }; }; }; }; return s; }- 개선된 알고리즘은 다음과 같다.
- python
def find_samething_3(a): s = set() n = len(a) for i in range(0, n-1): for j in range(i+1, n): if a[i] == a[j]: s.add(a[i]) return s- rust
fn find_samething_2(a: Vec<&str>) -> Vec<&str> { let mut s = vec![]; let n = a.len(); for i in 0..n-1 { for j in i+1..n { if i != j { if a[i] == a[j] { if !s.contains(&a[i]) { s.push(a[i]); }; }; }; }; }; return s; }- 집합을 사용하는 것, i+1 을 사용하는것에서 재미를 느꼈다. 자료를 어떤 도구를 사용하여 저장할 것인지. 그리고 해당 자료는 어떻게 선별하여 사용할 것인지 생각하며 알고리즘을 짜야겠다.
