1. 문제 설명문제 링크2. 접근 방식KEY WORD: Sorting, HashMap음악 객체를 만든다. ( 멤버 변수: 자신의 고유번호, 장르, 플레이 횟수 )입력 값들을 전부 음악 객체로 바꿔서 ArrayList에 추가한다.HashMap을 만든다. Key = 장르 , value = 장르에 해당하는 곡들의 플레이 총합2번에서 만든 ArrayList를 정렬한다. 정렬 기준은 문제 그대로다. -> Comparator를 단순화한 Lamda 식을 이용해 구현답변용 ansList를 만들고, 답변에 장르별로 몇 번 들어갔는지를 나타내는 genreAddedCount라는 HashMap도 하나 더 만든다.genreAddedCount는 Key = 장르, value = 장르 별로 답변 List에 나온 횟수 이다. .get..

1. 문제 설명문제 링크2. 접근 방식부분 문자열은 크기 1부터 N/2까지만 생각하면 된다. (N = 문자열의 길이)왜냐하면, 부분 문자열의 크기가 절반 이상이면 반복이 불가하므로, 세는 의미가 없다. 1번에서 정한 문자열 크기만큼 처음부터 자른다. 이 행위는 0 ~ N - i 까지만 반복한다. 부분문자열을 구하는 substring(startIndex, endIndex)에서 endIndex가 배열의 범위를 넘어가면 예외가 발생한다. 우리는 substring(startIndex, startIndex+i)만큼 항상 할 것이므로, endIndex가 배열의 범위를 넘어서지 않도록 반복의 범위를 위와 같이 정한다.최초 자른 부분 문자열은 중복 체크가 불가하므로 이전 문자열(이하 prev)에 저장한다.이전 문자열과..

1. 문제 설명문제 설명2. 접근 방식KEY WORD: 구간합 & 투 포인터데이터 크기가 10^5 이라서 시간복잡도가 O(n^2) 이상이면 안된다. 따라서 한번의 조회안에 모든 것을 끝내야 한다. 그러기 위해서 누적합을 사용하여 문제를 풀었다. 진행 방식은 다음과 같다.입력을 누적합 배열(sum) 형태로 만든다. (다만 진짜 누적합의 시작은 sum[1] 부터 시작하고, sum[0]=0 으로 비워둔다.)left, right 포인터를 만들고 다음과 같이 움직인다.(1) sum[right] - sum[left] (2) sum[right] - sum[left] == M 이면 (right-left) 길이 기록 후에, right를 움직인다.(3) sum[right] - sum[left] > M 이면 (right -..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: Brute forcekey=String, value=Integer인 map에 문자로 표현한 숫자 =int형 숫자로 1~9까지 모든 숫자를 저장한다.포인터를 하나 사용하여 해당 포인터가 가르키는 값을 word 란 StringBuilder에 저장한다.(1) word의 길이가 3이상이면 map에 해당 값을 key로 가지는 값이 있나 계속 확인(2) 있으면 해당 수를 숫자로 바꾸어 답변이 되는 ans에 저장하고 word를 비운다.(3) 없으면 포인터를 한 칸 이동하여 word를 또 채운다.(4) 만약 숫자라면 ans에 값 저장하고 바로 건너 뛰기.3. 코드 분석import java.io.*;import java.util.*;class Solution { ..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: BINARY_SEARCH이번 문제의 주어진 배열의 크기는 10^5이다. 주어진 시간 제한이 2초이므로, 2억 번의 연산 횟수 내에 문제를 풀어야 한다. 만약 해당 문제를 브루트 포스로 접근해, 모든 2차원 배열을 돌겠다고 생각하면, 연산 횟수가 10^5의 제곱인 10 억번이 되어 문제를 풀지 못한다.해당 문제는 이분 탐색(binary_search)을 이용해 풀 수 있다. 고난도 이분 탐색 문제가 늘 그렇듯, 도대체 뭐에 대해서 이분 탐색을 해야하는지 감 잡기가 힘들다. 그래서 거기서 부터 시작 하겠다.(1) 무엇에 대해서 이분 탐색을 해야 하는가?먼저 문제에서 주어진 B[]이란 배열에 대해서 알아볼 필요가 있겠다. B[k] = x 이것이 무엇을 뜻하..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: GREEDY Algorithm광물을 캐는 비용을 최소화 하기 위해서는, 돌 곡괭이로 캤을 때, 비용이 제일 많이 드는 구간이 앞에 오도록, 광물 리스트를 정렬하고, 구간들을 순회하며, 그때 그때 최선의 곡괭이로 일처리를 해야한다.그 의미에서 Greedy Algorithm을 써야 하는 것이다.광물의 크기가 50밖에 안됨으로 시간복잡도 관련해서 걱정할 것은 없을 것 같다. 그렇다면 해야할 일은,광물 List를 5개씩 자른다. 그것이 일의 단위이기 때문이다.(근데 광물이 5의 배수로 안 맞아 떨어질 수 있다. 그러면 맨 마지막은 3개나 4개가 하나의 묶음이 될 수도 있음으로 이를 주의해서 Loop를 짠다.)나눠진 광물 묶음을 돌 곡괭이로 작업했을 때 피로..

1. 문제 설명문제 링크2. 접근 방식key word: Priority QueueN*N개의 수 중 N 번째 큰 수를 구하는 것이다.그래서 나는 오름 차순 PriorityQueue를 만들어서 해당 queue의 size를 N개로 유지한다. 방법은 다음과 같다.맨 마지막 행의 값 N개를 PQ에 담는다. (맨 마지막 행은 각 열 별로 최고값 이다.)배열을 한 행씩 올라가서 값들을 Priority Queue의 peek()값과 비교한다.(1) peek() 현 조회 중인 값: peek()을 poll() 해서 버리고, 현 조회중인 값을 PQ에 넣는다.(2) peek() >= 현 조회 중인 값: PQ를 N개로 유지하는 이유는 N번째 큰수를 찾기 위해서 이다. 현재도 PQ 안의 최소값보다 작으므로 N번째 큰 수가 되기 만..

1. 문제 설명문제링크2. 접근 방식keyword: GCD(최대 공약수) 구하는 법 - 유클리드 호제법ArrayA와 ArrayB의 최대 공약수를 구한다. 최대 공약수를 구하는 방법은 다음과 같다. 맨 처음 값과 두 번째 값 간의 최대 공약수를 구한다. (유클리드 호제법 이용)1번에서 나온 GCD와 세 번째 값간의 최대 공약수를 구한다.(왜 이렇게 구해도 되는거야? - 1번에서 나온 GCD는 이미 1 번째 값과 2 번째 값에서의 최대 공약수 이다.만약 해당 GCD로 3 번값이 바로 나누어진다면, GCD가 1,2번과 같은 것이므로, 그대로 가도 된다.만약 GCD가 더 작아진다면, 해당 값이 현재까지 3가지 값에서 통하는 GCD 인 것이다.이런 식으로 GCD를 갱신해 나가면, 모든 값에서 통하는 GCD를 구할..