mondegreen

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

- 백준 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..