판교의 메타몽

문제 링크 The problem link : LeetCode 49. Group Anagrams 문제 요약 문자열 배열 strs가 주어진다. 애너그램으로 재배열했을때 같은 단어들끼리 그룹으로 뭉쳐라. 그룹으로 뭉쳐진 단어들을 반환하라. 이때 순서는 상과없다. 문제 풀이 class Solution { public List groupAnagrams(String[] strs) { HashMap map = new HashMap(); for(int i=0; i

문제 링크 HackerRank : Fraudulent Activity Notifications (Click) 문제 요약 List 타입의 expenditure와 int타입의 d가 아래와 같이 주어진다. expenditure = [10,20,30,40,50] d = 3 중간값의 정의는 해당 글을 참고한다. 예를 들어 위와 같이 d가 3인 경우, n-3, n-2, n-1의 값중 중간값 * 2 이상의 값을 n번째 날이 가질 경우, 고객에게 알림을 보내줘야한다. 10,20,30의 중간값은 20인데, 40의 경우 20*2 이상의 값을 가지므로 알림을 보내야한다. 20,30,40의 중간값은 30인데, 50의 경우 30*2 보다 값이 작으므로 알림을 보낼 필요가 없다. 때문에 위 예시에서 알림을 보내는 개수(정답)는 ..

문제 링크 HackerRank : Sorting : Comparator (Click) 문제 요약 n 사이즈의 선수들의 정보가 담긴 배열이 주어진다. 여기서 두 사람씩 차이를 비교할 compare메서드를 완성하라. 성적(score)은 내림차순으로, 이름(name)은 오름차순으로 정렬해야한다. a > b라면 1을, a = b라면 0, a b.score) return -1; else if(a.score < b.score) ret..

문제 링크 HackerRank : Recursive Digit Sum (Click) 문제 요약 1

문제 링크 HackerRank : Davis&#39; Staircase (Click) 문제 요약 Davis의 집에는 계단이 많은데, Davis는 한번에 계단을 오를때 1칸, 2칸, 또는 3칸을 오를 수 있다. Davis가 n층 높이의 계단을 오를때, 몇 가지의 가지수로 계단을 오를 수 있는지 정답을 구하라. 이때 정답은 10000000007로 나눈 나머지를 출력하라. 문제 풀이 public static int stepPerms(int n) { if(n == 0) return 0; else if(n == 1) return 1; else if(n == 2) return 3; else if(n == 3) return 4; int t1 = 1; int t2 = 2; int t3 = 4; int res = 0; ..

문제 링크 GeeksForGeeks : Union-Find (Click) 문제 요약 아래 2개의 메서드를 완성하라. Union : 2개의 부분집합을 하나로 합치기 isConnected : 2개의 부분 집합이 하나의 부분 집합인지 true or false로 출력하기 문제 풀이 class Solution { public int find(int x, int par[]) { while(x != par[x]) { x = par[x]; } return x; } //Function to merge two nodes a and b. public void union_(int a, int b, int par[], int rank[]) { a = find(a, par); b = find(b, par); if(a==b) re..

문제 링크 The problem link : Geeks For Geeks - Transitive closure of a Graph(클릭) 문제 요약 N*N 배열 graph가 주어집니다. 이 배열은 방향이 있는 그래프를 뜻합니다. graph[i][j]가 의미하는 것은, i 정점에서 j 정점까지 연결되어있는 (= 방향이있는) 간선이 있음을 뜻합니다. 정점 i에서 j까지 (다른 정점을 거쳐서라도) 도달할 수 있는지를 가리키는 그래프를 출력하세요. 핵심 요약 문제 조건을 보면 예상 시간복잡도와 공간복잡도를 이렇게 언급했다. Expected Time Complexity: O(N^3) // 시간복잡도 Expected Auxiliary Space: O(N^2) // 공간복잡도시간 복잡도를 보면 힌트가 나오는데, 이 ..

문제 링크 The problem link : LeetCode 841. Keys and Rooms 문제 요약 0번째부터 n-1까지 라벨이 붙여진 방이 있습니다. 0번째 문을 제외한 나머지 문은 잠겨있습니다. 방에 들어갔을때, 해당 방에 존재하는 key를 사용할 수 있게됩니다. 이렇게되면 key를 사용해 해당 방에 들어갈 수 있습니다. 당신의 목적은 0번째부터 n-1까지의 모든 방을 들어가는 겁니다. 가능할 경우 true를, 그렇지 않을 경우 false를 출력하세요. 예시 입력값 : rooms = [[1,3],[3,0,1],[2],[0]] 출력값 : false 해설 : 2번째 방(=[2])에 들어갈 수 없기 때문에 false입니다. 조건 - n == rooms.length - 2

문제 링크 The problem link : LeetCode 1971. Find if Path Exists in Graph 문제 요약 노드의 개수 n, 간선들이 연결되어있는지 알려주는 배열 edges, 출발지 source, 목적지 destination이 주어집니다. 해당 그래프에서 source와 destination이 연결되어있는지 확인하고, 연결되어있을 경우 true를 반환하세요. Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2: - 0 → 1 → 2 - 0 → 2 문제 풀이 class Soluti..

문제 링크 The problem link : Count Triplets 문제 요약 배열의 사이즈 n(1 left.getOrDefault(num/r, 0L)의 뜻은, num의 바로 이전 공비의 배수가 있는지 판단하는 식입니다. (5) 그렇게 탐색이 끝난 현재의 숫자(=num)은 left에 저장해줍니다. 시간 복잡도 O(n)입니다.