IT LAB

난이도 : medium 문제링크 연결 무방향 그래프의 노드가 주어진다 deep copy된 그래프의 노드를 리턴하라 각 노드의 값은 유일하다 1. 접근법 노드를 BFS 탐색하여 새로운 노드를 탐색할 때마다 clone함 2. 의사코드 // Queue에 node 노드 추가 queue.offer(node) // queue가 비어있지 않을때까지 반복 while (!queue.isEmpty()) { // 가장 최근에 들어온 것 뽑음 Node cur = queue.poll(); // cur의 이웃 순회 for (Node neighbor : cur.neighbors) { // 방문하지 않았던 이웃이라면 if (!map.containsKey(neighbor)) { // 큐에 추가 } // 현재 노드에 이웃 추가 } } ..

난이도 : easy 문제링크 두개의 정렬된 링크드리스트가 주어진다 두개의 링크드리스트를 하나의 정렬된 링크드리스트로 병합하라 1. 접근법 정렬되어 있으므로 값을 비교하여 새로운 노드에 순서대로 추가한다 2. 의사코드 while (list1, list2가 null이 아닐때까지) { if (list1.val가 list2.val 보다 크다면) { tmp.next = new ListNode(list1.val); list1 = list1.next; } else { tmp.next = new ListNode(list2.val); list2 = list2.next; } tmp = tmp.next; } if (list1 != null) { tmp.next = list1; } if (list2 != null) { tmp..

난이도 : medium 문제링크 int 배열인 nums가 주어짐 각각의 요소는 maximum jump length를 뜻함 0번째 인덱스부터 시작함 맨 마지막 인덱스에 도착할수 있는지 여부를 리턴하세요 1. 접근법 인덱스 ~ 1 값까지 깊이탐색을 시작한다 한건이라도 첫번째 인덱스에 도착할 수 있다면 true 리턴 2. 의사코드 public boolean canJump(int[] nums) { int start = nums[0]; for (start ~ 1까지 반복) { if (dfs 탐색하여 true를 반환하면) { return true; } } // 아니면 retrun false; return false; } private boolean dfs(int[] nums, int idx) { if (idx가 마..

난이도 : medium 문제링크 int 배열인 prices가 주어진다 i인덱스 값은 i날짜의 상품가격이다 날마다 사거나 팔수 있음 하루에 최대 하나만 보유할 수 있음 구매한 날에 즉시 판매 가능 최대 이익을 리턴하라 1. 접근법 이익을 볼 수 있는 거래가 많을수록 최대 이익을 얻을 수 있다 저점에 사서 고점에 파는 전략을 선택한다 그리디 알고리즘을 활용하여 풀 수 있다 2. 의사코드 public int maxProfit(int[] prices) { int maxProfit = 0; int curIdx = prices.length-1, prevIdx = curIdx-1; // 뒤에서부터 조회 : 판매 날짜에 대한 저점 매수 날을 찾는다 (모든 배열 탐색할 때까지) while (curIdx > 0) { //..

난이도 : easy 문제링크 prices라는 정수형 배열이 주어진다 prices의 요소는 인덱스 i날짜의 재고 가격을 뜻한다 이익이 최대가 되는 날짜를 구하라 1. 접근법 가장 싸게사서 가장 비싸게 팔아야 최대의 이익이 발생함 내림차순일 경우, 0을 리턴함 판매일은 구매일 이후여야 한다 구매가 - 판매가가 최대 이익값 2. 의사코드 for (int i = 1; i prices[i] && i < maxDay) { // buy // min 값 업데이트 // minday는 현재..

난이도 : medium 문제링크 int 배열인 nums가 주어짐 배열을 주어진 k번만큼 오른쪽에서 회전하세요 1. 접근법 k부터 마지막까지 원소들을 미리 저장해둠 0부터 마지막-k까지 원소들을 k부터 마지막까지 할당함 k부터 마지막까지 원소들을 미리 저장해둔 배열에서 꺼내서 할당함 2. 의사코드 public void rotate(int[] nums, int k) { k = k % nums.length; if (k == 0 || nums.length == 1) { return; } int[] tmpArr = new int[nums.length-k]; for (int i = 0; i < nums.length-k; i++) { // 1. tmpArr에 0 ~ 오른쪽에서 k번째까지 저장 } for (int i ..

난이도 : easy 문제링크 int 배열에서, 가장 많이 등장한 숫자를 리턴하라 2/n번 이상 나타나야 한다 1. 접근법 두번째 원소부터 반복하면서 배열의 원소를 순회한다 map을 이용하여 원소별 카운트를 저장한다 카운트를 내림차순으로 정렬하고, 첫번째 원소를 리턴한다 2. 의사코드 for (int i = 0; i < nums.length; i++) { map에 원소별 원소 갯수 put } for (Map.Entry entry : map을 value의 내림차순으로 정렬한 list) { return entry.getKey(); } return 0; 3. 구현 코드 public int majorityElement(int[] nums) { Map map = new HashMap(); for (int i = 0..

난이도 : medium 문제링크 int array인 nums가 주어진다 (non-decreasing order) 중복 요소를 지워라 (in-place) 두번까지 나타난 요소까지만 중복 표기 가능 순서를 유지하라 1. 접근법 in-place 문제 배열을 인덱스로 접근하여 풀기 non-decreasing이며, 두개까지 중복허용이 가능하므로 투포인터를 사용하여 위치를 설정하기 2. 의사코드 int i=0; while (left

난이도 : medium 문제링크 2개의 integer 리스트 nums1, nums2와 숫자k가 주어진다 리스트는 non-decreasing order이다 합이 작은 순서대로 k 개의 두 배열의 원소로 구성된 pair들을 리턴하세요 1. 접근법 합이 작으려면, 작은 숫자부터 뽑아서 pair를 구성해야 함 최소힙 자료구조를 사용하여 pair를 만든다 2. 의사코드 // 좌표의 합을 가지고 오름차순한 우선순위 큐를 생성한다 PriorityQueue pq = new PriorityQueue( (a, b) -> (a[0] + a[1]) - (b[0] + b[1]) ); // pq에 원소들을 모두 넣고 for (int n1 : nums1) { for (int n2 : nums2) { pq.offer(new int[..

난이도 : medium 문제링크 int array인 nums와 int값인 k가 주어진다 nums 배열에서 k번째로 큰 값을 리턴하라 1. 접근법 유일한 값이 아닌, 중복된 값을 포함하여 리턴해야 함 최대 힙을 구현하여, k번째 pop된 값을 리턴하기 2. 의사코드 1. Heap 클래스 구현 public void push(int e) { arr[n++] = e; bubbleUp(n-1); } public void pop() { int top = arr[n-1]; arr[0] = top; n--; bubbleDown(0); return top; } private void bubbleUp(int i) { if (i가 0보다 작거나 같으면) return; int parentIdx = (i-1)/2; if (ar..