판교의 메타몽

문제 링크 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..

map과 unordered_map의 차이 요약 map unordered_map 시간복잡도 O(logN) O(1) 데이터 정렬 레드블랙 트리 (Red-Black Tree) -> 중복허용 X, Key를 기준으로 오름차순 자동정렬 해시테이블 (Hash Table) -> 중복허용 X, 정렬되지 않음 권장하는 사용법 1. 데이터 양이 보다 적을때 권장 2. Key를 이용하여 정렬을 해야할때 권장 대량의 데이터를 저장할때 권장 * 레드블랙트리 : 이진탐색트리의 일종 * 해시테이블 : 키 값을 주소로 사용 map활용 예시 : 사용된 영어 단어들을 1. 빈도순 2. 문자순으로 정렬 예를들어 사용된 단어들이 1. 많이 사용됐을수록, 2. 사전순으로 앞에 올수록 더 앞에 위치하게 정렬을 한다고 가정해보자. map을 사용하..

The link : leetcode.com/problems/subarray-sum-equals-k/Subarray Sum Equals K - LeetCodeLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.leetcode.com 문제에 친절하게도 힌트가 주어져있었고, 힌트 덕분에 풀 수 있었다. 문제 풀이는 다음과 같다. 1. key가 int, value가 int인 맵을 구현한다.2. 맵의 [0] = 1로 저장해둔다. 두 연속된 배열의 차가 0이거나, 배열의 원소가 1개인 값이 k인 경우를 고려해서 넣는 ..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 문제 풀이는 다음과 같다. 1. int형 key와 int형 value로 이루어진 맵을 만든다. 2. 튜플에 담겨진 숫자들을 key에 넣고, value의 값을 하나씩 증가시킨다. 이렇게되면 아래와 같은 로직이 구현된다. (1) 가장 큰 value의 값 = 가장 많이 누적된 값이 튜플의 맨 앞에 오는 원소 (2) ..

The link : leetcode.com/problems/group-anagrams/submissions/Group Anagrams - LeetCodeLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.leetcode.com예전에 이미 풀어본 적이 있었는데, 이때는 해쉬 테이블과 맵의 개념을 몰라서 아는대로 무작정 풀었섰다다시 도전하게 되었을때는 아래와 같은 방법을 고안했다. 1. Unorder_map에 문자열을 저장한다. 이때 Key와 Value는 다음과 같다.Key : 문자열을 오름차순으로 정렬한 값 ..

문제 링크 : www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 풀이는 다음과 같다. 1. 공백을 포함한 문자열을 EOF이전까지 받아준다. 2. map을 통해 동일한 이름의 나무끼리 묶어주고 숫자를 셀 수 있도록 map 함수를 활용한다. 3. 소수점 4자리까지 값이 나올 수 있도록 라이브러리를 활용해준다. 3-(1) 이때 나무의 갯수 int형을 double로 형변환 하는 것을 잊지 않도록 한다. #include #include #include ..