728x90 Algorithm/Codility3 [Codility] Clone Graph 문제 분석 1. 딥카피를 해야 된다. 2. 리턴 값이 Node 인걸로 보아 인접 한 노드를 추가 해줘야 한다. 3. 주어진 대로 복사를 해야 되기 때문에 DFS 를 사용한다. 구현 import java.util.*; class Solution { public Node cloneGraph(Node node) { if (node == null) return null; // 깊이 탐색을 위한 노드 스택 선언 // 스택 -> DFS, 큐 -> BFS Stack nodeStack = new Stack(); // 새로 생성한 노드를 저장하기 위한 맵 Map map = new HashMap(); // 처음 시작되는 노드를 넣어준다. nodeStack.push(node); // 처음 노드를 반환 값으로 쓴다. Node.. 2023. 1. 22. [Codility] Product of Array Except Self 문제 분석 자기 자신을 제외한 값들의 곱을 구하는 것이다. O(n) 으로 구현을 해야 된다 나눗셈 연산을 쓰지 말하야 한다. 해당 인덱스를 기준으로 왼쪽 을 곱한 값, 오른 쪽 값을 곱한 값을 저장한다. 왼쪽 오른쪽 값을 계산한다. 이렇게 하는 이유는 O(n) 으로 풀어야 하기 떄문이다. 구현 class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int []leftNums = new int[n]; int []rightNums = new int[n]; int []answer = new int[n]; leftNums[0] = 1; for(int i = 1; i < n; i++) { leftNums[i] = nums.. 2022. 12. 17. [Codility] BinaryGap 문제 분석 이진 수에서 1로 둘어쌓인 0 의 최대 길이를 찾는 거다. 10001001 -> 4 값이 나와야 한다. 1001000001 -> 5 값이 나와야 한다. 첫번째 1 을 찾고 두번째 1을 찾을때 계산된 값과 맥스값을 비교하면 끝 구현 // you can also use imports, for example: // import java.util.*; // you can write to stdout for debugging purposes, e.g. // System.out.println("this is a debug message"); // you can also use imports, for example: import java.util.*; // you can write to stdout for.. 2022. 10. 29. 이전 1 다음 728x90 반응형
