mondegreen

[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-Clip03] - 백준 10814 나이 순 정렬 나이를 비교하는 것은 간편했으나 관건은 가입한 순서를 반영하는 것이기에 입력하는 순서인 인덱스를 객체의 속성으로 포함해 클래스로 만들었다. 이렇게 구현하니 하나의 객체의 속성들을 비교하기만 하면 되어서 간편하게 정렬을 구현할 수 있었다. package BaekJoon.sort; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class BJ10814 { public static class MemberInfo { int registerOrder; int age; String name; public MemberInfo(int..

[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(자바의..