PS
-
java 프로그래머스 2018 카카오 블라인드 1차 셔틀버스 풀이 | Map, Queue 활용PS 2024. 5. 31. 14:52
https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr # 문제 풀이 전 생각했던 것들1. 매개변수로 주어지는 시간들이 문자열로 주어지기 때문에 :을 기준으로 split하고 모두 분(minute)으로 변환하는 메소드가 필요하다고 생각했다. 그리고 반환형이 다시 시간형이기 때문에 분으로 환산한 시간을 00:00 형식으로 변환하는 메소드도 만들어줘야겠다고 생각했다. 2. 셔틀의 최대 개수가 10개고, 셔틀 별 정원의 수가 45명이니 사이즈가 작다고 생각했다..
-
leetcode top interview 150 | Clone Graph | BFSPS 2023. 9. 15. 09:24
Question 주어진 그래프를 클론한 그래프를 리턴. 그래프는 무방향으로 연결되어있고 노드마다 value와 주변 인접 노드들을 List에 넣어 가지고 있다. 인접노드들을 노드의 순서대로 담아 리턴해야한다. Accepted Codeimport java.util.*; class Solution { public Node cloneGraph(Node node) { if(node == null) return null; Queue queue = new LinkedList(); queue.add(node); Map map = new HashMap(); map.put(node, new Node(node.val, new ArrayList())); while(!queue.isEmpty()){ Node visit = qu..
-
leetcode top interview 150 | Kth Largest Element in an Array | PriorityQueuePS 2023. 9. 12. 09:52
Question 정수배열이 주어질때 k번째로 큰 수를 리턴 Accepted Code - Sorting import java.util.*; class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); int answer = 0; int idx = nums.length - 1; while(k-- > 0){ answer = nums[idx--]; } return answer; } } 정렬을 한번 수행하고 k를 감소시켜가며 배열의 끝에 있는 값을 저장한다. 시간복잡도는 Arrays.sort()로 O(n log n)이 소요된다. Arrays.sort는 이전엔 퀵소트 방식을 사용했지만 Java 7이상부터는 병합정렬과 선택정렬을 ..
-
leetcode top interview 150 | Binary Tree Right Side View | DFSPS 2023. 9. 6. 17:17
Question 트리구조로 된 노드들이 주어지고 트리를 오른쪽에서 봤을때 가장 오른쪽에 있는 노드의 value를 트리의 위부터 아래까지 순서대로 리스트에 넣어서 반환한다 Accepted Code /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * }..
-
leetcode top interview 150 | Find Peak Element | Binary SearchPS 2023. 9. 5. 09:45
Question 양 옆의 수보다 큰 경우를 peak이라 한다. 주어진 정수배열에서 peak을 찾고 해당 인덱스를 반환하라. 만약 여러개의 peak이 존재하면 어떤 인덱스를 반환해도 된다. 배열 밖의 요소들은 가장 작은 수로 인지해라. 알고리즘의 시간복잡도는 O(logN)으로 작성해라. Accepted Code class Solution { public int findPeakElement(int[] nums) { int start = 0; int end = nums.length - 1; while(start
-
leetcode top interview 150 | Min Stack | ArrayListPS 2023. 9. 1. 09:58
Question Stack의 push, pop, top, getMin 메소드를 디자인하기 각각의 메소드는 O(1)의 복잡도로 수행되어야한다. MinStack()스택 개체를 초기화합니다. void push(int val)요소를 val스택에 푸시합니다. void pop()스택 맨 위에 있는 요소를 제거합니다. int top()스택의 최상위 요소를 가져옵니다. int getMin()스택에서 최소 요소를 검색합니다. Accepted Code - ArrayList로 Stack 구조 만들기 import java.util.LinkedList; class MinStack { List stack; List minStack; public MinStack() { stack = new ArrayList(); minStack ..
-
leetcode top interview 150 | Valid Anagram | HashMapPS 2023. 9. 1. 09:43
Question 문자열 t가 문자열 s의 애너그램이면 true, 아니면 false를 리턴한다. Accepted Code - HashMap import java.util.*; class Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; Map map = new HashMap(); for(char c : s.toCharArray()){ map.put(c, map.getOrDefault(c, 0) + 1); } for(char c : t.toCharArray()){ if(map.containsKey(c) && map.get(c) > 0) map.put(c, map.get(c) - ..
-
leetcode top interview 150 | Ransom Note | HashMapPS 2023. 9. 1. 09:29
Question ransomNote 문자열이 magazine에 있는 문자로만 구성되어있으면 true, 아니면 false 리턴 magazine에 있는 각각의 문자는 ransomNote에서 한번만 사용할 수 있다. Accepted Code import java.util.*; class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] alpha = new int[26]; for(char c : magazine.toCharArray()){ alpha[c - 'a']++; } for(char c : ransomNote.toCharArray()){ int idx = c - 'a'; if(alpha[idx] > 0) ..