IT LAB

난이도 : easy 문제링크 두개의 문자열이 주어진다 : pattern, s s가 pattern 문자열의 패턴을 따르는지 확인하라 ex) pattern = "abba", s = "dog cat cat dog" => true ex) pattern = "abba", s = "dog cat cat fish" => false 1. 접근법 해시테이블 생성 pattern 문자에 대응되는 s 문자열 s 문자열에 대응되는 pattern 문자 한 문자씩 순회하면서, 특정 pattern 문자에 대응되는 s 문자열이 해시테이블에서 가지고있는 값과 동등한지 확인 s 문자열에 대응되는 pattern 문자가 해시테이블에서 가지고있는 값과 동등한지 확인 3. 구현 코드 public boolean wordPattern(String ..

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