IT LAB

난이도 : easy 문제링크 두개의 문자열이 주어진다 : ransomNote, magazine magazine의 문자를 사용해 ransomNote를 생성할 수 있다면 true를 리턴하라 1. 접근법 magazine이 ransomNote의 모든 문자를 포함해야 함 magazine의 문자 별 갯수를 hashtable을 사용하여 관리한다 ransomNote의 문자들을 각각 순회하면서 megazine의 문자에 포함되어 있는지 확인한다 확인될 경우, 해당 문자를 사용하여 ransomNote를 생성하는데 쓴다 Key의 value값을 내린다 3. 구현 코드 class Solution { public boolean canConstruct(String ransomNote, String magazine) { Map map..

난이도 : easy 문제링크 정수형 배열 nums와 정수 k가 주어진다 서로다른 인덱스 i, j의 요소값에 대하여 아래 두개의 조건을 모두 만족하는지 여부에 대해 boolean 값을 리턴하라 nums[i] == nums[j] abs(i-j)

난이도 : medium 문제링크 n*n 의 2차원 정수 배열이 주어짐 배열의 각 원소는 역 좌우교대서법 스타일로 라벨이 되어진다 맨 왼쪽 아래부터 읽혀짐 줄이 바뀔때마다 글씨를 쓰는 방향이 반대가 됨 글자의 모양도 반대가 됨 한번의 턴마다 [curr+1 ~ min(curr+6, n^2)] 의 범위로 움질일 수 있음 셀의 값은 -1 혹은 1~n^2 -1 : 일반 칸. 특정 범위로 이동하기 -1이 아님 : 해당 셀로 이동 (snake or labber) n^2 칸에 도착하면 게임이 종료됨 가장 적게 n^2에 도착하는 턴의 횟수를 리턴하라 이동이 불가능하다면 -1을 리턴하라 1. 접근법 접근법 자체를 떠올리지 못했다 너무 어. 렵. 다. (ㅠㅠ) 6. 회고 감이 전혀 안잡혀 강의를 들었다 class Pair ..

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