판교의 메타몽

문제 링크 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)입니다.

문제 링크 The problem link : Frequency Queries 문제 요약 2차원 쿼리가 주어집니다. 이때 쿼리가 가진 값의 의미는 다음과 같습니다. 1 x : x를 저장 2 y : y값이 저장되어있을 경우, 제거 3 z : 빈도수(=누적된 개수)가 z인 값이 있을 경우, 1을 출력하고 그렇지 않을 경우 0을 출력 예시 코드는 다음과 같습니다. Operation Array Output (1,1) [1] (2,2) [1] (3,2) 0 (1,1) [1,1] (1,1) [1,1,1] (2,1) [1,1] (3,2) 1 문제 풀이 핵심 코드는 다음과 같습니다. static List freqQuery(List queries) { HashMap hm = new HashMap(); // 0 List a..

문제 링크 The problem link : Sherlock and Anagrams 문제 요약 n개의 문자열이 주어졌을때, 각 문자열마다 애너그램을 통해 서로 같은 문자열을 만들 수 있는 쌍의 개수를 찾으세요. (* 애너그램 : 재배열을 했을때 다른 뜻의 문자를 만듦) 애너그램의 예시는 다음과 같습니다. s = mom [m,m] [mo,om] -> 2개의 정답 문제 풀이 핵심 코드는 다음과 같습니다. public static void add(HashMap hm, String s){ // 3 char a[] = s.toCharArray(); Arrays.sort(a); // (1) ns = new String(a); hm.putIfAbsent(ns,0); // (2) hm.put(s, hm.get(ns)+..

문제 링크 The problem link : Jewels and Stones - LeetCode 문제 요약 보석의 종류가 담겨진 String 타입의 변수, jewels가 있습니다. 돌의 종류 가 담겨진 String 타입의 변수 stones가 있습니다. 가지고 있는 돌의 종류 중, 총 몇개의 보석 종류가 있는지 확인하세요. 문제 풀이 class Solution { public int numJewelsInStones(String jewels, String stones) { String[] jTemp = jewels.split(""); String[] sTemp = stones.split(""); int ans = 0; for(int i=0; i

Largest Rectangle | HackerRank Given n buildings, find the largest rectangular area possible by joining consecutive K buildings. www.hackerrank.com 문제 요약 건물의 갯수와 각 건물의 높이가 주어집니다. 일렬로 나열된 건물에서 안정적인 사각형 지대를 찾으려고 합니다. 사각형의 값은 아래 공식으로 구합니다. k * min(h[i], h[i+1], ... , h[i+k-1]) 쉽게 말해 가장 큰 넓이를 가진 사각형이 안정적인 사각형 지대가 됩니다. 핵심 요약 위 문제는 stack, queue의 유형으로 분리되어있지만, 단순 Brute Force를 통해서도 접근이 가능합니다. 핵심을 요약하면 다..

Queues: A Tale of Two Stacks | HackerRank Create a queue data structure using two stacks. www.hackerrank.com 문제 요약 2개의 Stack을 이용해서 Queue와 동일한 로직을 만들어 보세요. input 값으로 다음과 같이 입력이 가능합니다 q : 쿼리의 갯수 (최초에 1회 입력) 1 x : x를 큐에 저장 2 : 큐의 맨 앞 (가장 오래된 값)을 제거 3 : 큐의 맨 앞 (가장 오래된 값)을 출력 핵심 요약 해당 LeetCode의 문제와 흡사한 문제 유형입니다. 필요한 기능은 크게 다음 3가지로, 각각을 2개의 Stack을 이용해 구현합니다. enqueue : 큐에 값을 저장 dequeue : 큐의 첫 번째 값을 제거 ..

24392번: 영재의 징검다리 첫 줄에 N과 M(1 ≤ N, M ≤ 1,000)이 공백으로 구분되어 주어지고, 그 뒤에는 N줄에 걸쳐 다리의 정보가 주어진다. 강화유리의 경우 1, 일반 유리의 경우 0으로 주어진다. www.acmicpc.net 문제 요약 1. 첫 줄에 N과 M, 영재가 건널 수 있는 다리 정보 N*M (1 h >> w; for(int i=0; i arr[i][j]; } } int main() { input(); for(int i=0; i=0; i--){ for(int j=0; j

문제 링크 : https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 문제 요약 핵심 포인트 백 트래킹을 활용해서 풀면 됩니다. 이때 부메랑을 만들 수 있는 4가지 모양을 판별하는 것이 중요합니다. 부메랑의 모양은 일반적인 회전 모형처럼 for문을 돌려서 판별할 경우 갔던 경로를 되돌리는 과정의 구현이 번거로울 수 있으므로, for문을 사용하지 않고 각각 별개로 구현하는 것을 권장합니다. 문제 풀이 전체 코드입니다. #include ..

문제 링크 : https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 문제 요약 1. 6개의 팀이 서로 한 번씩 경기를 진행합니다. 승부의 결과는 승리 / 무승부 / 패배 3가지 입니다. 2. 4개의 테스트 케이스가 주어졌을때, (테스트 케이스 1줄 당 18개의 숫자가 입력됨) 해당 테스트 케이스가 가능한 경우인지 확인하세요. 3. 주어진 4개의 테스트에 대하여 가능한 경우 1을, 불가능한 경우 0을 공백을 한칸씩 띄고 출력하세요. 핵심 포인트 불가능한 ..