mondegreen

구하고자 하는 바를 기준으로 로직을 생각하니 금방 구현할 수 있었다. 여기서 구하고자 하는 건 질투심 즉, 가장 사탕을 많은 아이의 사탕 갯수이다. 사탕 갯수 배열을 두번만 돌아도 백억을 넘기 때문에 시간 초과가 발생할 것이고 이분 탐색을 활용해서 풀이한다. left는 [1, 10^9] 구간 중 1이 가장 적은 사탕의 수가 되고 가장 사탕의 수가 많은 종류를 한 아이가 다 받는 경우 즉, 10^9가 right이다. 이를 테스트케이스에 적용하면 색상별 사탕의 수를 입력 받고 해당 배열을 정렬하면 첫번째 원소에는 최소 질투심이 될 수 있는 수, 마지막 원소에는 최대 질투심이 될 수 있는 수가 담겨있다. 이를 통해 이분 탐색을 진행하고 중간 값인 m 값이 질투심이라고 가정했을 때, 반복문을 돌면서 해당 질투심..

[Part1-Chapter07-Clip10] - 백준 2110 공유기 설치 정말 어리석게도 이분탐색으로 공유기를 설치할 집을 찾고 있었다. 사실 이런 접근을 생각하지 못하고 있었다. 그래도 정리해보자면 우리가 구하고자 하는 값은 인접한 공유기가 가질 수 있는 최대 거리! 이 값을 이분 탐색으로 처리한다. left가 되는 가장 작은 값은 한 집에 한 공유기를 설치할 수 있고 연속된 두 집에 모두 공유기가 설치되어 있다면 그 경우 1이 된다. right 값, 즉 인접한 공유기 거리가 최대가 되는 경우는 집 배열을 오름차순으로 정렬했을 때 가장 첫 번째 원소와 가장 마지막 원소의 집에 공유기를 설치하는 경우다. 이렇게 이분 탐색을 진행하는데 임시 공유기 거리인 중간 값을 기준으로 공유기를 설치한다 가정하고 이..

[Part1-Chapter07-Clip09] - 백준 6236 용돈관리 항상 고민하는 부분인데 코드를 간결하게 작성하는 것이 필요하지만 또 한 편으로는 협업을 고려해 구체적으로 작성하다보면 내 코드는 줄줄이 길어지는 경우가 많더라. 아직은 후자를 기준으로 두고 작성하지만 이러다 불필요한 자료구조나 변수 선언으로 메모리 효율이 낮아질 것 같아 고민이다. 아래 코드는 기존의 이분 탐색과 크게 다르지 않다. 다만 금액이 이번에 지출해야 하는 금액보다 적게 남았을 때는 해당 금액을 반환하고 다시 인출한다는데 총 인출할 수 있는 금액이라는 게 정해져 있지 않기 때문에 로직적으로만 생각하면 결국 그냥 잔돈이 기본 인출금액으로 리셋되면 된다. 반대로 금액이 이번에 지출해야 하는 금액보다 많이 남았을 때가 고민되는 지..

[Part1-Chapter07-Clip07] - 백준 2805 나무 자르기 풀고 나니 간단해 보이는데 분기를 짜는데 조금 시간이 걸렸다. 일단 좀 특이한 점은 자르고자 하는 높이를 설정하고 나무가 잘라진 길이를 구할 때 나무를 일단 정렬하고 잘리는 나무들의 시작 인덱스를 이분탐색으로 구했다는 점이다. 기본적으로 자를 높이는 가져가고자 하는 나무 길이의 최솟값이 1이므로 가장 큰 나무의 길이보다 -1한 값을 r로 설정하고 모두 베어버리는 경우가 가장 긴 나무 길이를 가져 가는 것이므로 l 는 0으로 설정했다. 이분 탐색을 통해 가져가고자 하는 길이와 같은 경우, 짧은 경우, 긴 경우를 분기하여 로직을 구현했다. import java.io.*; import java.util.*; public class Ma..

[Part1-Chapter07-Clip06] 매개변수 탐색은 이분 탐색을 이용해 최적값을 탐색하는 기법이다. 연속적인거나 이산적인 값의 집합에서 최적값을 X를 찾고자 할 때 X를 경계로 조건을 만족하는 집합과 답이 될 수 없는 집합을 판정할 수 있을 때 추정 값 A에 대한 판정을 반복해 X를 찾는 방법이다. 이때 판정의 대상이 되는 추정값을 구할 때 이분 탐색을 이용하면 O(logX)의 복잡도의 로직을 짤 수 있다. 보통 ~ 조건을 만족하는 최솟값과 최댓값을 구하라는 문제가 해당된다. 이전에 lowerBound와 upperBound를 찾았던 백준 10816 숫자 카드 2 문제에서 적용했던 것도 이 매개변수 탐색의 일종이라 할 수 있다. - 백준 2417 정수 제곱근 long의 범위에 있는 숫자를 찾으려면..

- 백준 2143 두 배열의 합 개인적으로 그간 이분탐색을 작성하며 느꼈던 자괴감을 해소할 수 있었던 문제였다. 처음부터 로직을 먼저 의사코드로 설계한 후에 코드로 작성했다. 부 배열을 만들어내는 과정에서 자꾸만 3중 반복문을 순회하게 되어 분명 시간 초과가 날 것이라고 생각했다. 또한 부배열을 구성하는 원소의 개수를 구분해서 그룹으로 비교하려다 보니 ArrayList[] 라는 자료구조에 담게 되었고 이를 다시 한 배열마다 정렬을 진행했다. 당연히. 시간초과가 날 수밖에 없었다. 한참 돌다가 다른 사람들의 풀이를 보니 해시맵을 이용해 풀던데 도저히 내 코드를 버릴 수가 없었고 코드 최적화를 통해 풀어낼 수 있었다. 수정한 사항은 위에서 말한 두 가지이다. 첫째는 부배열을 추출하는 방식이다. 원소의 개수별..

[Part1-Chapter07-Clip04] - 백준 2470 두 용액 문제에서 주의해야 할 점은 '모든 용액의 특성값은 다르다, 산성 두 개 또는 알칼리성 두 개의 용액으로도 가장 0에 가까운 혼합 용액을 만들 수 있다' 라는 부분이다. 이 두 부분에서 정렬 처리와 음수와 양수를 구분하지 말기를 생각할 수 있었다. 이분 탐색으로 처리하다가 코드 상으로는 문제가 없어보였는데 5%에서 오류가 나서 투포인터 방식으로 다르게 구현했다. 두 값을 더한 값의 절댓값이 이전의 최솟값보다 작다면 갱신하여 두 개의 특성값을 저장했고 여기서 l과 r를 변경시키는 로직을 생각해내기가 어려웠는데 두 값을 더한 값이 0보다 작으면 더 작은 값을 키우고 0보다 크면 더 큰 값을 줄이도록 구현했다. import java.io.B..

[Part1-Chapter07-Clip03] - 백준 2295 세 수의 합 문제를 읽고 제일 먼저 두 수를 고정하고 집합의 원소인 set[k] 에서 나머지 한 수를 이분탐색하는 방식을 고민했다. 하지만 코드를 작성하다 먼길을 가버렸고 한참을 단순히 l과 r의 범위나 m을 추출하는 방식을 고치면 탐색의 범위를 조정할 수 있지 않을까라는 바보 같은 생각을 했다. 코드를 작성하면서 l과 r을 다시 의사코드로 작성해보니 l과 r이 아니라 첫수와 두수를 투 포인터 방식으로 고정하고 나머지 한개의 수를 다시 배열에서 이분탐색했어야 했는데 라는 깨달음과 다시 코드를 의도에 맞게 작성했다. 그런데 테스트 케이스도 모두 맞추는데 이상하게 3%에서 틀리는 것이다.... 결국 다른 코드를 참고해보니 결국 내가 작성한 것은 ..

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); String[] pool = new String[n]; for (int i = 0; i < n; i++) { pool[i] = sc.next(); } // 이분 탐색은 정렬된 배열에서 진행 가능함 Arrays.sort(pool); int cnt = 0; for (int i = 0; i < m; i++) { String thisStr = sc.next(); int l..

[Part1-Chapter05-Clip04] - 백준 17232 생명게임 이전에 푼 구간합 구하기 5의 풀이 과정을 담으면 되는 문제였다. 동일한 문제였지만 *라는 문자로 변경되었다고 누적합을 생각해내지 못해서 강의를 보고 나서야 반영할 수 있었다.. 누적합 배열을 별도로 만들지 않으면 원래 배열에서 변화를 주게되고 그럼 다음 원소를 탐색할 때 변경된 값을 참조하는 큰 문제가 있다. 또한 반복문을 순회하면서 변경사항을 반영하다보면 시간 복잡도가 커지기 때문에 변경되는 부분을 누적합을 먼저 구해주고 한번에 반영하는 것이 시간 초과하지 않는 방법이다. import java.io.*; import java.util.StringTokenizer; public class Main { public static vo..