1. 문제 설명문제 링크2. 접근 방식(1) HashSet에 나오는 모든 부분 문자열을 저장한다. (2) map1 , map2는 HashMap으로서 각 문자열의 문자가 key, 그 문자가 나오는 개수가 value이다. (3) hashSet에 저장되어 있는 문자를 하나씩 꺼낸다. 해당 문자의 개수를 map1과 map2에서 꺼내서, 합집합과 교집합을 계산한다.합집합: 둘 중 더 개수가 많은 쪽의 개수를 더한다.교집합: 둘 중 하나라도 값이 존재하지 않으면 넘어간다. 둘 다 해당 값을 가지고 있다면 개수가 더 적은 쪽의 개수를 더한다.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(String str1, St..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: 이분 그래프이분 그래프에 대해서 알지 못하면 풀 수 없는 문제였다. 나는 몰라서, 먼저 이분 그래프를 공부한 뒤에 다시 문제를 접했다. 먼저 이분 그래프에 대한 설명부터 적으려고 하는데, 이에 대해서 아시는 분들은 목차에서 (3) 풀이 방식 부터 보시길 바란다.(1) 이분 그래프란 무엇인가요?그래프의 정점들을 2개의 부분집합으로 분할 했을 때, 정점이같은 부분집합 내의 정점과는 간선을 가지지 않는다.무조건 반대편 부분집합이랑만 간선을 가진다.가 성립하면, 해당 그래프를 이분 그래프라고 한다. 말로 하니까 어려운데, 그림으로 그려보겠다.다음과 같이 생긴 그래프가 있다. 해당 그래프는 이분 그래프이다. 이분 그래프 임을 증명하는 2개의 부분집합으로 나누..

1. 문제 설명문제 링크2. 접근 방식해당 문제는 문제에서 하라는 대로만 하면 된다.(1) 받은 숫자를 N진법으로 변환한다.문제를 풀던 당시에는 Integer.toString(n, radix) 라는 문법을 알지 못했다. 해당 문법은 n을 2번째 인자인 radix진법으로 변환해서 String으로 반환한다. Integer.toString(n,2)이면 n을 2진법으로 반환해서 String 값으로 반환하는 것이다.이 문법을 몰라서, 직접 반환했다.반환 방법은 다음과 같다.바꾸려는 수를 n, 진법을 radix라고 할 때, n%radix == 0 이 될 때까지 n을 radix로 나눈다.이때 나머지 값을 저장하고 있는다.드디어 n%radix == 0 이 되면 지금까지 나왔던 나머지들을 역순으로 줄 세운다.자세한 변환..

1. 문제 설명문제 설명2. 접근 방식KEY WORD: BFS2차원 배열에 값을 담는다.번호 별로 의미가 있다. (0 = 벽, 1 = 미방문한 아파트 단지, 2 = 방문한 단지)(1) 2차원 배열을 순회하다가 값 == 1인 것을 만나면, 해당 값을 시작으로 BFS를 돌린다. 현재 값의 사방을 탐색한다. 사방의 값 중 1인 값이 있으면 큐에 넣고, 해당 위치의 값을 2로 바꾼다. 큐가 빌 때 까지 (더 이상 사방 탐색을 해도 값 = 1이 안 나올 때 까지) 반복한다.(2) 1번은 첫 조회에서 만난 아파트의 아파트 단지 전체를 한번에 보는 것이다. 따라서 1번의 반복 횟수가 곧 아파트의 개수이다.(3) 아파트 단지를 단지내 아파트의 개수에 따라 오름차순으로 정렬한다. 3. 코드 분석import java.i..

1. 문제 설명문제 설명2. 접근 방식KEY WORD : BACK-TRACKING(0) 사전 세팅1차원 배열(arr)을 n의 크기만큼 만들고 배열의 index = 행 , 배열의 value = 열로 생각한다.예를 들어 배열이 다음과 같을 때, 그림으로 나타내면 이렇게 된다.index(행)0123value(열)1302(1) 만약에 arr[i] = j 라고 한다면 2차원 배열 [i] [j] 에 퀸을 두겠다는 소리이다. 이게 가능한지 체크한다. 체크하는 방법은0 ~ i-1 까지의 배열 값을 이용해, 이전에 놔둔 퀸의 공격 경로와 겹치는지 확인하면 된다. 확인법은 다음과 같다.(1-1) 좌하단 확인대각선이 일치하는 값들은 모두 행+열의 합이 같다. 이를 이용한다. 우리의 경우는 index가 행이고 value가 열..

불규칙적인 생활을 하니, 설명할 수 없는 불안감이 몰려온다. 다시 마음을 잡고 해봐야겠다. 그 후...아무것도 못했다...핑계를 대자면 여름 휴가를 갔긴 한데... 핑계 대지 말자....

1. 문제 설명문제 설명2. 접근 방식KEY WORD: 브루트 포스(1) 문자열로 받은 숫자를 한 자릿수가 되게 나누어서 배열에 저장한다.(2) 전체 숫자가 n개라면 그 중 k개를 뽑아서 나열한다. (순열, k = 1 ~ n )(3) 나열된 k개의 수를 합쳐서 하나의 숫자로 만들고, 소수 판별한다. (소수 판별법 이용)(4) 소수 판별이 확정되면 해당 수가 이전에 나왔는지, hashSet으로 체크한다. 없으면, 소수의 개수를 +1 올린다.  ※추신※(1)나는 한자리 수를 합치는 것을 원래의 수 * 10 + 새로 들어온 한 자리 수로 그때 그때 바로 했다.(2)소수 판별법을 모른다면, 정리 잘 한 사람 링크를 보고 오기 바란다. 해당 링크에서는 왜 n의 제곱근까지만 나눠서 확인하면 되는지 나와있다.(3)소..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: 이분 탐색무엇을 기준 으로 이분탐색을 해야할까?이분 탐색 문제를 풀 때, 제일 어려운 부분이다. 어려운 문제일수록 무엇을 기준으로 이분 탐색을 해야할지 감이 서지 않는다. 나 또한 그랬다. 그래서 다른 사람의 풀이 아이디어까지 봤다. 분명 1년 전에 같은 문제를 백준으로 풀었는데, 안 떠올라서 좀 좌절 했다 ㅜ(1) 기준 : M 시간 당 각 심사대에서 처리하는 사람의 수내 기준에서 어려웠던 점은 규칙 - 심사대가 비더라도, 사람은 다른 심사대가 빌 때까지 기다렸다가 들어갈 수 있다. 였다. 이 자율성 때문에, 문제의 유형을 생각하지 못한 것 같다. 하지만 기억해야할 점은, 무엇을 이분 탐색 해야할지 모르겠을 때는, 반환하는 답을 기준으로 탐색할 것이..

1. 문제 설명문제 링크2. 접근 방식이건 뭐 Priority Queue 쓸 줄 아냐고 묻는 문제였다.PQ를 만든다. (default로 오름차순 정렬이니 건들일 것이 없다.)문제에서 제공하는 Order에 따른다. (0이면 출력, 나머지면 저장)3. 코드 분석import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PriorityQueue pq = new PriorityQueue(); ..

1. 문제 설명문제 설명2. 접근 방식KEY WORD: Sliding Window, 나머지 연산아이디어를 떠올리기가 어려워서 다른 사람의 풀이 블로그에서 아이디어 부분까지만 봤다.나는 a와 b를 일일히 교환하는데만 집중하고 있었는데, 완전히 잘못된 접근 방식이었다. 그러한 방식으로 풀었을 때, 최소값을 어떻게 찾을 수 있을지 감이 안온다. 문제를 푸는 방식은 다음과 같다. 문자열 내의 a의 개수를 세고, 그 개수를 용량으로 하는 Sliding window를 만든다.문자열의 처음부터, 1번에서 센 슬라이딩 윈도우의 용량만큼 a와 b의 개수를 센다. b의 개수 == 교환이 일어나는 횟수 이다. 현재 a의 개수만큼씩 배열을 확인하고 있고, 거기서 b의 개수를 전부 a로 돌린다면, 연속된 a와 연속된 b가 ..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: GREEDY문제 설명 그대로 Queue 두 개를 만든다.총합이 큰 쪽의 queue.peek()을 poll 해서 다른 쪽 큐에 추가한다.2번 종료 후 두 큐의 총합이 같은지 검사한다.만약 같으면, 2번을 행한 횟수를 출력한다. 만약 두 큐의 총 길이 + 1 만큼 해도 두 큐의 합이 같지 않으면 -1을 출력하고 종료 한다.두 큐의 총 길이 + 1 만큼 반복해야 하는 이유는 뒤에서 설명.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(int[] queue1, int[] queue2) { ArrayDeque a = new ArrayDeque()..

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. 이분 탐색 (binary-search)란 무엇인가요?이분 탐색(binary-search)이란, 정렬된 상태의 일련의 데이터 중 현 기점에서 답 후보가 될 수 없는 절반을 삭제해가며 답을 찾아내는 탐색 알고리즘 이다. 다음과 같이 정렬된 10개의 정수가 배열 형태로 주어져 있다고 하자. 우리는 여기서 23이란 수를 찾고자 한다.(1) 먼저 목표값과 비교할 기준을 구해야 한다. 기준은 항상 값을 구해야 하는 구간의 중앙값이다. (짝수면은 중앙의 두 개의 값 중 앞 쪽 값이다.)(2) 16을 23과 비교해보니, 작다. 이 말은 즉 '16의 앞쪽 원소들도 목표 값보다 작다.' 는 말이 된다. 왜냐하면 이미 오름차순으로 정렬된 상태에서 탐색을 시작했기 때문이다. 따라서 16과 그 앞 쪽의 수들은 전부 날린다..

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를 구할..

1. 문제 링크문제 링크2. 접근 방식백준에서 풀었던 오른쪽에서 큰 수와 같은 문제인데, 문제를 푸는 아이디어가 생각이 안나서, 저번에 풀었던 것 좀 봤다.해당 문제는 Stack 자료구조를 이용하여 풀어야 한다.나는 먼저 Node라는 Class를 만들었다. Node의 구조는 다음과 같다.class Node { int i; // 원래 index int v; // 값 public Node (int i, int v){ this.i = i; this.v = v; }}해당 Node를 자료형으로 가진 Stack을 만든다. 그리고 답을 저장하는 배열ans을 하나 더 만든다.배열은 index = 원래 값의 위치, value = 해당 index 값의 뒷큰수가 무엇인지 ..