mondegreen

문제 분석을 진행하면서 배열을 만들까 고민했었다. 논리값 배열을 만들고 지나간 여부를 true / false로 처리하려고 했는데 생각해보니 이 문제는 좌표가 아니라 선분(길, 양 끝의 좌표 세트)을 확인해야 하는 문제였다. 따라서 배열을 사용하지 않고 두 개의 좌표를 필드로 가지고 있는 클래스를 생성해서 그 클래스를 타입으로 하는 해시 셋으로 처리하고자 했다. 하지만 여기서 간과한 것은 내가 클래스의 필드와 생성자만 만들고 set에서 contains로 같다고 확인할 수 있도록 equals 매서드를 만들지 않았기 때문에 각각의 클래스가 new 생성자로 생성된다면 각기 다른 주소값을 가지게 되어 equals로 판별할 수가 없게된다. 그래서 생각한 것은 Set의 타입을 String으로 설정하는 것이다 Stri..

해시맵까지 잘 구현했는데 정렬하는 부분에서 꼬여버렸다. 아래 return문은 스트림 형식으로 추출해서 정렬하고 배열로 반환하는 방식이다. import java.util.*; class Solution { public int[] solution(int N, int[] stages) { int gamer = stages.length; int [] cnt = new int [N+1]; for(int i : stages){ if(i

언제 배웠는지도 기억이 가물가물한 행렬의 곱셈이 어떤 방식으로 처리되는지 이해가 안되서 찾아보고 푼 문제이다. 구현의 핵심은 아래 주석이 달려있는 부분이다. class Solution { public int[][] solution(int[][] arr1, int[][] arr2) { int [][] answer = new int[arr1.length][arr2[0].length]; for(int i = 0; i < answer.length; i++){ for(int j = 0; j < answer[i].length; j++){ for(int k = 0; k < arr2.length; k++){ // 이 반복문이 중요한데 행렬의 곱셈에서 결과 행렬의 크기는 [첫번째 행렬의 행][두번째 행렬의 열] 이다. ..

처음에 큐를 써가면서 앞에서 뽑고 뒤로 넣어야 하나라는 고민을 했다. 하지만 시간이 더 걸릴 것 같아서 배열을 활용한 방법을 고민했고 모드 연산을 통해 반복문을 돌지 않고도 각 수포자의 답안을 비교할 수 있겠다는 것을 깨달았다. 그 뒤의 구현은 복잡하지 않았다. 다만 list를 어떻게 array로 변환할까 고민했고 두 가지 방식을 사용했다. 리스트에서 배열로 복사하는 방법과 스트림으로 변환해서 배열로 만드는 법. 시간은 전자가 훨씬 빠른 것 같다. import java.util.*; class Solution { public int[] solution(int[] answers) { int [] st1 = {1,2,3,4,5}; int [] st2 = {2,1,2,3,2,4,2,5}; int [] st3 ..

문제를 분석하고 입력값과 연산 횟수를 고려해 의사코드를 작성하고 시간 복잡도를 고민한 다음 코드를 작성했다. 활용한 것은 TreeSet인데 이 Set은 선언할 때부터 오름차순으로 정렬해주고 first()와 pollFirst() 같은 메서드를 활용해 가장 작은 값을 확인하거나 꺼내주는 기능을 한다. 따라서 별도로 배열 정렬할 필요가 없다. 여기서 잠깐 놓친 것은 pollFirst() 매서드를 사용함으로써 set의 크기가 동적으로 변하는데 변수로 저장해두지 않고 반복문의 길이를 size()로 설정했던 것이다. 실수를 깨닫고 변수로 받아 정적으로 활용했다. import java.util.*; class Solution { public int[] solution(int[] numbers) { TreeSet se..

[Part2-Chapter01-Clip03] - 백준 2230 수 고르기 left가 되는 인덱스를 기준으로 반복문을 돌면서 그 안에서 while 문으로 right를 맨 마지막 인덱스로부터 줄여보려고 했다. 하지만 left가 바뀔 때마다 right를 새로이 맨 마지막 인덱스로 갱신했기 때문에 결국 n^2이 되어 시간 초과가 발생했다. 음 그러면 right는 이전 left가 옮겨 놓은 그 위치 그대로 탐색해보자고 했지만 값을 못 찾는 문제가 발생했다. 이번 left와 right를 각각 확인해봐야 하는데 이미 right를 당겨와 버려서 그 뒤의 값들와 left를 비교하지 못하는 문제였다. 다시 생각해보니 방향이 틀렸다는 것을 깨달았다. 마주보는 방향으로 이동하는 것이 아니라 한 방향에서 시작하면서 m보다 작으..

[Part1-Chapter08-Clip01] - 백준 2003 수들의 합2 투 포인터란 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정 값을 찾는 알고리즘을 말한다. 포인터를 사용하는 방식은 다음과 같이 다양할 수 있다. 1) 같은 배열에서 동일한 방향으로 이동하는 투포인터 (이 경우 2003 문제이다.) 2) 같은 배열에서 마주보는 방향으로 이동하는 투포인터 3) 서로 다른 배열에서 이동하는 투포인터. 이때 두 포인터 중 경우에 따라 하나 또는 모두가 끝에 도달할 때까지 반복한다. 아래는 부분합 배열을 구현하여 풀이한 것이다. l과 r을 시작 원소와 끝 원소의 인덱스로 지정하고 해당 구간의 부분합이 m과 비교하여 큰지 작은지 같은지에 따라 포인터를 움직임으로써 경..

[Part1-Chapter09-Clip01] Array: 동일한 타입의 여러 원소를 선형 집합으로 관리하는 정적인 데이터 구조를 말한다. 생성과 동시에 크기를 지정해야 하며 이는 고정되어 늘릴 수 없다. 메모리에 물리적 순서가 고정되어 있어 인덱스로 접근이 가능하다. 인덱스로 접근이 가능하므로 조회 및 변경은 속도가 빠르지만 맨 앞에 있거나 중간에 있는 원소의 삭제나 삽입은 해당 인덱스 뒤의 연속된 원소를 한 인덱스씩 뒤로 미루거나 앞으로 당겨야 하므로 이 경우 속도가 느리다. List: 동일한 타입의 여러 원소를 선형 집합으로 관리하는 동적인 데이터 구조를 말한다. 원소가 추가/삭제 됨에 따라 크기 변경이 가능하다. 구현체는 ArrayList, LinkedList, Vector로 각 특성이 다른데 Ar..

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

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