log 2022-03-05

오늘 배운 것

---

• sport
  • leetcode - 3_sum
    • 내 풀이

sport

leetcode - 3_sum

https://leetcode.com/problems/3sum/submissions/

내 풀이

• 잘못 고려해서 틀림 1
• 같은개수의 수가 많을 때 시간초과 2

다른 사람 풀이를 보면 항상 내가 생각한 것 보다 그냥 low하고 심플하게 푼 경우가 많은 듯하다.

rust solution

    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        // 3000C3은 범위를 넘어가므로 불가능.
        // 일단 아마 인덱싱을 이용하는 트릭은 반드시 필요할 듯 한데..
        // 두 수를 선택하면, 나머지 한 수는 있는지 없는지 인덱스로 찾기만 하면 되긴 한다.
        // 다만 그렇게 할 경우 중복을 어떻게 체크할 것인지가 문제다.
        // [-1, -1, 2]는 [-1, 2, -1]과 같은 것으로 처리.

        // 반대로 어떤 합을 만들 수 하나를 결정하면, 나머지 두 수로 그 합을 만든다고 생각할 수도 있다.
        // 그 경우 중복 처리에 좀 더 유리할 지도 모르겠다.
        // 그렇지만 결국 반대로 선택하는 경우를 어떻게 제외할 지 모르겠다.
        // 0을 선택하고 만드려면 0 세개,
        // 어떤 양수 하나를 선택하면, 0이 되려면 음수 두 개 or 음수 하나, 양수 하나를 선택해야 한다.
        // 일단 두 수를 선택해서 그 합을 계산해서, 그에 맞는 같은 값이 있는지 체크한다면?
        // 에라 모르겠다. 일단 그렇게 해 보자.

        // 역시 몇개 남았는지 추적 없이는 의미가 없다.
        // 수동으로 재귀로 선택 하면서, 개수 관리하면서, 만들어야 할 합에 해당하는 수가 남아있다면 성공
        // 그래도 이 방법이 될 거라고 생각은 드는 게, 3000C3이 아닌, 3000C2로 줄이기 때문에 충분히 가능은 하다.
        // 구현이 귀찮을 뿐..

        use std::collections::HashMap;
        use std::collections::HashSet;

        let mut sums: Vec<i32> = vec![];

        let mut map1: HashMap<i32, i32> = HashMap::from([]);
        let mut set1: HashSet<i32> =
            HashSet::from(nums.clone().into_iter().collect::<HashSet<i32>>());

        let mut ans: HashSet<Vec<i32>> = HashSet::new();
        let mut cnt = 0;

        for item in &nums {
            let vv = map1.entry(*item).or_insert(0);
            if *vv <= 2 {
                *vv += 1;
            }
        }

        // dbg!(&map1);

        let zeros = *map1.entry(0).or_insert(0);

        if zeros >= 3 {
            ans.insert(vec![0, 0, 0]);
        }

        for item1 in &set1 {
            *map1.get_mut(item1).unwrap() -= 1;

            for item2 in &set1 {
                if item2 < item1 {
                    continue;
                }

                // 값이 없으면 continue
                // 값이 있으면, 0보다 크면 1 빼고 진행,
                // 값이 있는데 0이면 continue

                let item2_cnt = map1.get_mut(&item2).unwrap();
                if *item2_cnt > 0 {
                    *item2_cnt -= 1;
                } else {
                    continue;
                };

                let target = -item1 + -item2;
                match map1.get(&target) {
                    Some(vv) => {
                        if *vv > 0 && target >= *item2 {
                            cnt += 1;
                            ans.insert(Vec::from([*item1, *item2, target]));
                        }
                    }
                    None => {
                        *map1.get_mut(item2).unwrap() += 1;
                        continue;
                    }
                };

                *map1.get_mut(item2).unwrap() += 1;
            }

            *map1.get_mut(item1).unwrap() += 1;
        }

        // dbg!(cnt);

        // dbg!(&ans);

        ans.into_iter().collect()
    }
    

---