[TIL] 2024/11/08

오늘은 리크루팅 데이🎉 였다. 오전에 늦게 일어나서 오후까지 리쿠르팅 데이 행사에 참여하였고, 저녁 먹기 전까지 리트코드를 풀었다.

 

https://leetcode.com/problems/clone-graph/description/

 

이 문제가 특히 어려워서 헤매다가 결국 솔루션을 보았다.

    public Node cloneGraph(Node node) {
        if(node == null) {
            return null;
        }
        Map<Node, Node> mp = new HashMap<>(); // origin, copy
        int val = node.val;
        mp.put(node, new Node(val, new ArrayList<>()));
        Queue<Node> q = new LinkedList<>();
        q.add(node); 
        while(!q.isEmpty()) {
            Node now = q.remove();
            for(Node next : now.neighbors) {
                if(!mp.containsKey(next)) {  // not enrolled
                    mp.put(next, new Node(next.val, new ArrayList<>()));
                    q.add(next);
                }
                mp.get(now).neighbors.add(mp.get(next));
            }
        }
        return mp.get(node);
    }

 

맵을 활용한 BFS로 푸는 방식을 떠올리지 못하였다.

 

https://leetcode.com/problems/insert-interval/

겹치지 않는 간격을 구하는 문제이다.

interval을 merge하는 조건 식을 세우는 것이 어려워서 헤맸다. 일단 새로 추가된 interval을 배열에 넣고 다음 요소들을 res 에 반영할 때마다 추가하거나 값만 변경하는 방식으로 하여 해결할 수 있다.

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval); 
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> res;
        res.push_back(intervals[0]);
        
        for(int i = 1; i < intervals.size(); i++) {
            if(res.back()[1] >= intervals[i][0]) { // can merge intervals[i]
                res.back()[1] = max(res.back()[1], intervals[i][1]); // (1, 5)  +  (2, 3) // (1, 5)  + (2, 7)
            } else {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }

 

 

저녁에는 OAuth와 인증에 대해서 공부하였다.

마침 OAuth 관련한 좋은 책이 우테코에 있어서 읽으면서 공부하였다. 

인증 흐름을 잘 설명하는 연습을 했다.