IT LAB

난이도 : easy 문제링크 두개의 문자열이 주어진다 : s, t s와 t가 isomorphic 한지 체크하라 isomorphic은 다르게 표현되지만 같은 구조를 가지고 있을 때 사용한다 s의 문자가 t의 문자로 replace될 수 있으면 isomorphic하다 할 수 있다 ex) s="egg", t="add" => true ex) s="foo", t="bar" => false ex) s="paper", t="title" => true 1. 접근법 해시테이블 생성 s문자에 대응되는 t문자 t문자에 대응되는 s문자 한 문자씩 순회하면서, 특정 s문자에 대응되는 t문자가 해시테이블에서 가지고있는 값과 동등한지 확인 특정 t문자에 대응되는 s문자가 해시테이블에서 가지고있는 값과 동등한지 확인 3. 구현 코드 ..

난이도 : easy 문제링크 두개의 문자열이 주어진다 : s, t t가 s의 anagram이라면 true를 리턴하라 anagram은 또 다른 단어의 재구성을 통해 원본 단어를 똑같이 만들 수 있는 단어를 뜻한다 반드시 모든 문자를 한번씩 사용하여 구성해야 한다 ex) s = "anagram", t= = "nagaram" => true ex) s = "ab", t= = "a" => false (s의 문자 b를 사용하지 않았음) 1. 접근법 단어별 갯수를 관리하는 자료구조인 해시테이블을 이용한다 3. 구현 코드 class Solution { public boolean isAnagram(String s, String t) { Map map = new HashMap(); for (char c : s.toChar..

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