mondegreen

문제를 읽고 먼저 높은 숫자를 줄여나가야 한다고 판단했다. 이를 구현하기 위해 우선순위 큐를 생각해보았지만 같은 작업량을 가진 여러 개의 작업을 n을 하나씩 줄여가며 처리해야 하니 조금 비효율적이라고 생각했다. 이를 보완하기 위해 해시맵을 떠올렸지만 그 안에서 정렬을 매번 수행하느니 트리맵을 사용하자는 결론에 다다랐다. 트리 맵은 자주 사용하지 않아서 메소드가 익숙하지 않아 이건 찾아가며 로직을 구현했다. 만약 남아있는 근무시간과 동일한 작업량을 가진 작업의 수를 비교했을 때 남아 있는 근무 시간(n)이 더 크거나 같다면 해당 작업량의 키를 삭제하고 하나 작은 작업량을 가진 작업 수에 더해주고 n 역시 그 수만큼 줄여준다. 반대로 n이 더 작다면 n 만큼 값을 줄여주고 하나 작은 작업량의 작업 수에 n..

해시맵까지 잘 구현했는데 정렬하는 부분에서 꼬여버렸다. 아래 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

[Part1-Chapter05-Clip08] - 백준 1931 회의실 배정 10개월과 1개월 전에 풀었던 문제이고 오늘 다시 풀었다. 사실 이 문제는 끝나는 시간을 기준으로 오름차순 정렬하고 해당 시각이 같을 경우 시작 시각을 비교해서 오름차순으로 정렬하면 되는 문제이다. 이건 회의가 빨리 끝나는 경우 먼저 배정을 해주는 것이 최대한 많은 "수"의 회의를 진행할 수 있기 때문에 이 부분만 알고 있으면 풀어낼 수 있다. 다만 여기서 회의실 미 사용 시간을 최소화하는 경우를 찾으라고 했다면 이 문제 풀이만으로는 부족했을 것이고 여차하면 이렇게 이해를 할 수도 있는 문제였다. 먼저 2차원 배열로 시작시간과 끝나는 시간을 담고 해당 배열을 Sort할 때 Comprator를 이용해 정렬 로직을 구현해주었다. 이후..

[Part1-Chapter05-Clip07] - 백준 2910 빈도 정렬 자료구조로 고민이 많았던 문제이다. 일단 시간제한이 1초로 정해져있었고 최대 들어올 수 있는 숫자가 십억이었기 때문에 카운트 배열을 쓸 수는 없다고 생각했다. 이차원 배열 사용하는 것을 고려하려다가 반복문을 여러번 돌면 시간 제한이 걸릴 것 같아 해시맵을 사용하고자 했다. 초반에는 중첩된 해시맵을 사용하려다가 익숙하지 않아 자꾸 꼬이는 바람에 해시맵을 두개로 분리하여 사용했다. 하나는 빈도를 입력하는 해시맵(map)이고 하나는 기존 순서를 입력하는 해시맵(order)이다. 정렬하는 부분에서는 일단 존재하는 키를 집합으로 꺼내서 순서대로 정렬하는 것이었다. 빈도값인 value가 큰 경우 먼저 위치하도록 역순으로 처리했다. 애를 먹었던..

[Part1-Chapter05-Clip06] - 백준 18870 좌표 압축 로직이 머리 속에서 한참 꼬여서 애를 먹었다. 처음에는 카운팅 배열을 쓰고자 했다. 간단하게 풀이가 가능할 것 같았지만 메모리 초과로 사용할 수 없었다. 어쩔 수 없이 다른 자료구조를 고민했다. 이차원 배열을 쓰자니 중복처리하는데 번거로울 것 같았고 해시셋을 쓰자니 순서부여가 어려워 해시맵을 이용해서 처리했다. 이미 키가 존재한다면 넘어가고 순서를 부여하는 인덱스를 별도로 관리했다. import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.Scanner; public class Main { public static voi..

[Part1-Chapter05-Clip02] - 백준 1181 단어정렬 1년 전과 비교해서 나는 어떤 일이 있었던 걸까... 아무리 생각해도 set밖에 생각이 나질 않아 이를 활용해서 아래와 같이 풀었다. 그리고 compareTo가 단기 기억으로만 남고 정작 활용할 때는 잘 떠오르지 않아서 주석처럼 정리했다. 앞에 위치시킨다 이런 표현 대신 순서를 변경한다/안한다로 구분해서 정리하니 헷갈리지 않는다. import java.util.Arrays; import java.util.Comparator; import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scann..

[Part1-Chapter05-Clip01] 정렬이란, 일반적으로 숫자를 오름차순으로 정렬하거나 문자를 사전 순으로 정렬하는 것을 말한다. 더 나아가 데이터 집합을 적합한 순서로 배치하는 것을 말하는데 이름과 나이의 속성을 가진 객체가 있다면 그 안에서 나이가 어린 사람을 먼저 정렬하고 나이가 같은 경우 이름이 빠른 사람을 먼저 정렬하는 예시를 들 수 있겠다. 다양한 정렬 알고리즘과 그 시간 복잡도는 다음과 같다. 삽입 정렬은 그동안 많이 구현해왔고 퀵 정렬의 경우 분할 정복 재귀를 사용하며 면접에서도 많이 질문하는 알고리즘이기도 하다. 병합 정렬과 힙 정렬 구현도 잘 알아두어야 한다. 그리고 기본적으로 언어에서도 정렬을 위한 라브러리를 제공하는데 Util 패키지에서 제공하는 Arrays.sort(자바의..

[Part1-Chapter04-Clip09] - 백준 2817 ALPS식 투표 우선순위 큐나 set을 써야하나라는 고민이 들었던 문제였다. 아직 강의 순으로는 해당 자료구조를 배우지 않아서 최대한 배열을 사용하려고 했고 하지만 시간 복잡도를 고려했을 때 가장 높은 점수 순으로 칩을 부여하기 위해서는 적어도 리스트에 담아 정렬할 수밖에 없다는 생각이 들었다. 참가자들의 수가 250만이지만 스태프 수는 10명으로 제한되어 있고 나누는 값도 최대 14까지 적은 수가 반복문을 여러번 돌아도 시간 초과는 나지 않을 것 같았다. 또 칩을 부여하는 과정에서는 내림차순으로 정렬된 수를 각 스태프의 기본 점수로 나누었을 때 나머지가 0.0이면 칩을 부여하는 방식으로 처리했었는데 왜인지 찾을 수 없는 경우가 있어 모든 점..

[Part1-Chapter03-Clip04] -백준 10989 수 정렬하기 3 위 문제는 시간 제한과 메모리 제한이 비교적 있는 편이라 단순히 삽입 정렬을 할 수는 없었다. 최악의 경우 모든 숫자를 배열에넣고 단순히 sort 매서드를 쓰기에는 메모리 제한에 걸리기 때문에 그렇게 풀 수 는 문제는 아니었고. 정수배열의 경우 인덱스 하나당 4바이트 인데 모든 수를 배열에 넣는다면 4천만 바이트로 메모리 제한에 걸리기 때문에 불가. 주어지는 수의 갯수는 천개 이지만 수의 종류가 최대 10000이기 때문에 카운팅 배열을 활용하고자 했다. 입력을 받으며 해당하는 인덱스에 갯수를 늘려주고 입력되는 수의 최대값을 구해 놓으면 반복문을 돌 때 그 수를 줄일 수 있을 거라고 생각했다. 카운팅 배열에 오름차순으로 값을 넣..