IT LAB

난이도 : 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..

난이도 : medium 문제링크 단어 추가, 찾기의 기능을 가진 자료구조를 구현하라 찾기 : '.' 문자 사용 가능 (와일드카드) word 1 return false } List tmp; for (entry : node.children.entrySet()) { tmp.add(search(entry.getValue(), word.substring(1)); } return !tmp.stream().allMatch(b -> b == false); } return search(node.children.get(word의 첫번째 단어), word.substring(1)); } 3. 구현 코드 class WordDictionary { class Node { private Map children; private boo..

난이도 : medium 문제링크 trie (or prefix tree)는 문자열 데이터셋의 키를 저장하거나 가져오는데 효과적인 트리자료구조 이다 맞춤법 체크나 자동완성 기능의 구현에 사용된다 insert(), search(), startWith() 메서드를 구현하세요 1. 접근법 문자열들은 문자들의 순차적으로 의존하는 데이터 하나의 문자를 노드로 생성함 각 노드는 자식의 정보를 담은 Map 자료구조와 해당 글자까지 단어인지 여부를 가지는 boolean 필드를 가진다 Trie 자료구조는 트리를 순회하는데 사용하기 위한 Node 타입의 root라는 필드를 가지도록 함 insert(String word) 파라미터로 받은 word의 부분문자열이 tree에 이미 존재한다면 tree에서 부분문자열의 마지막 node..

난이도 : easy 문제링크 binary tree의 root 노드가 주어짐 각 레벨의 평균값에 대한 list를 리턴하라 1