Java

문제 접근 방식 세그먼트 트리를 사용해서 풀 수 있는 문제라는데 아직 배우지 않아서 세그먼트 트리에 대해서 간단하게 검색해 보니 재귀를 사용한 방식이라 스택으로도 풀 수 있는 문제라서 스택을 사용해서 풀어봤다. 눈으로는 이해가 쉽고 넓이가 바뀌는 구간을 찾아서 계산을 해주면 해결된다는 사실도 머리로는 쉽게 이해가 가능하지만 구현하려니 막상 머리가 안 돌아갔다... 우선, 간단하게만 생각해 보면 직사각형의 넓이는 다음 막대그래프의 높이가 낮아질수록 최대로 가능한 넓이가 작아질 것이고 다음 막대그래프의 높이가 같거나 높아야 최대로 가능한 넓이가 유지되거나 커진다. 정리하면 각각의 높이가 4 5 5인 막대그래프가 연속해서 존재하면 가능한 최대 높이는 가장 낮은 높이인 4와 연속된 그래프의 개수 3을 곱한 12..

문제 접근 방식 문제를 본 순간 떠올릴 수 있는 가장 쉬운 풀이는 배열을 하나하나 다 비교해 보는 것인데 두 배열의 최대 크기가 20000이기 때문에 최악의 시간 복잡도가 20000^2라 해당 문제를 풀 수가 없다. 투 포인터를 사용하여 효율적으로 풀 수 있지만 아직 배우지 않았기 때문에 정렬만 사용해서 풀어보기로 했다. 우선 두 배열을 모두 오름차순으로 기본 정렬한 후에 먹히는 배열을 순회하면서 먹는 배열을 매번 순회해 준다. 이때 먹히는 배열의 값이 먹는 배열의 값보다 작아지는 시점부터는 뒤에 오는 배열의 값들은 확인할 필요가 없기 때문에 남은 배열의 크기만큼 카운트를 추가해 주면 된다. 이렇게 풀면 시간은 오래 걸려도 통과는 되긴 하지만 나중에 이분탐색을 배운 후에 다시 풀이를 추가하도록 하겠다. ..

문제 접근 방식 숫자의 등장 횟수가 가장 많은 순서대로 정렬해야 하고 같은 경우에는 처음 입력된 순서대로 유지해야 한다. 입력 순서를 유지하기 위해 LinkedHashMap을 사용해서 풀었는데 생각해보니 입력의 범위가 모두 int형이라 배열을 사용해도 되는 문제다. 순서와 숫자의 카운트만 신경 써서 정렬해주면 되는 문제라 구현 자체는 어렵지 않았다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); Stri..

문제 접근 방식 입력받은 문자열들 중에서 중복을 제외하고 문자열의 길이가 같지 않다면 짧은 것을 우선 정렬하고 같다면 사전순으로 정렬해줘야 한다. 입력받은 배열을 위의 정렬 기준으로 정렬한 후에 중복이 아닌 경우만 출력해 주거나 Set을 이용해 애초에 중복을 허용하지 않고 저장하여 정렬한 후에 출력해 주는 방법이 있는데 Set을 사용해서 풀었다. HashSet을 이용해서 중복 없이 입력받은 후에 정렬을 해주거나 TreeSet을 이용해서 순서를 유지해 가며 입력을 받을 수 있다. 첫 번째 코드가 HashSet을 이용한 방법이고 두 번째 코드가 TreeSet을 이용한 방법이다. 풀이 public class Main { public static void main(String[] args) throws IOEx..

문제 접근 방식 이 문제는 입력을 왜 이렇게 불편하게 주는지는 모르겠다... 입력 받은 수들을 모두 뒤집은 후에 오름차순으로 정렬해야 하는데 입력 자체를 스트링으로 받기 때문에 스트링 빌더의 리버스 메서드를 사용하여 돌려준 후에 long 타입으로 변환해줬다. 그 후에 정렬은 직접 구현해서 하거나 sort 메서드를 사용하면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer ..

문제 접근 방식 정렬한 후에 반복문으로 카드 수를 일일이 체크하는 것이 더 빠르지만 Comparator 사용에 익숙해질 겸 한 번의 정렬만으로 해결해 봤다. 맵을 사용 해서 카드의 수를 키로 하고 값을 해당 카드가 등장할 때마다 1씩 증가시켜 줬다. 맵은 배열처럼 하나의 객체와 타입으로만 이루어진 것이 아니기 때문에 맵을 정렬하기 위해선 entrySet 메서드를 사용하여 셋이나 리스트로 바꿔줘야 한다. List entries = new ArrayList(cards.entrySet()); entries.sort( (o1, o2) -> { int ov = o1.getValue(); int tv = o2.getValue(); long ok = o1.getKey(); long tk = o2.getKey(); i..

문제 접근 방식 정렬 문제 해결을 위한 Comparator / Comparable 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또 da9dac.tistory.com 세 가지의 정렬 기준대로 시리얼 번호를 정렬해야 하는데 자바에서는 Comparator를 사용하여 정렬 메서드의 정렬 기준을 커스텀할 수 있다. (블로그에 Comparator와 Comparable에 대해 정리해 둔 글이 있으니 참고하길 바란다.) 우선 첫 번째 정렬 기준은 문자열의 길이라 짧은 것이 가장 최우선이고 길이가 같다면 시리얼 번호의 각 자릿수의 합이 낮은 것 합도 같은 경우에는 ..

1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 위의 문제의 경우에는 세 가지의 정렬 기준으로 주어진 입력을 정렬해야 하는데 반복문을 돌면서 총 3번의 정렬을 수행할 수도 있겠지만 Comparator와 Comparable을 이용해 커스텀 정렬 기준으로 정렬을 할 수도 있다. 자바에서 제공하는 두 인터페이스들은 객체를 비교할 수 있는 상태로 만들기 위해 사용하는데 숫자나 문자 같은 경우는 기본적으로 손쉽게 비교가 가능했지만 객체는 서로 다른 특성을 가지고 있기 때문에 어떤 것으로 비교해야 할지 정해진 기준..