본문 바로가기

분류 전체보기242

[백준] 13334: 철로 - JAVA https://www.acmicpc.net/problem/13334 풀이n명의 사람에 대해 2개씩 점의 위치가 주어지고, d길이의 선을 위치했을 때 2개의 점이 모두 선 안에 있는 사람의 최댓값을 구하는 문제이다. 입력을 받으면서 우선순위큐에 저장했다. 우선순위큐의 정렬 조건은 오른쪽 점을 오름차순으로, 오른쪽 점이 같을 경우 왼쪽 점을 오름차순으로 했다. 또 다른 우선순위큐을 만들어 개수를 세는 용도로 사용했다. 첫번째 우선순위큐를 pq라 하고, 두번째 우선순위큐를 count라고 했다. pq에서 값을 빼서 count에 넣는다. 이때 선분 d의 오른쪽 점을 pq에서 뺀 값의 오른쪽 점으로 하고, 이 선분에 왼쪽 점이 속해있지 않는 값들을 count에서 뺀다. 그 후 최댓값을 count의 size와 비교하.. 2024. 5. 16.
[자바] equals() & hashCode() 재정의 알고리즘을 풀던 중 Node라는 class를 만들어 set에 넣어 contains 메서드를 이용해 비교하려고했다. 객체를 비교하기 위해서는 클래스에 equals와 hashCode 메서드를 재정의해야했다. static class Node { int a; int b; public Node(int a, int b) { this.a = a; this.b = b; }}public static void main(String[] args) throws IOException { Node left = new Node(1, 2); Node right = new Node(1, 2); System.out.println(Objects.equals(left, righ.. 2024. 5. 16.
[백준] 1525: 퍼즐 - JAVA https://www.acmicpc.net/problem/1525 풀이3x3 표의 퍼즐을 맞추는데 최소 이동 횟수를 구하는 문제였다. 빈칸은 0으로 주어지고 0의 상하좌우에 있는 숫자를 0위치로 이동시킨다. 0을 기준으로 상하좌우를 탐색하여 숫자를 바꿔주고, 그렇게 만들어진 배치를 방문처리하였다. 이때 방문처리를 String으로 하였는데, 메모리제한때문이었다. 숫자들을 이어붙여 String으로 만들었고, String의 indexOf 메서드를 이용하여 위치를 찾아 좌표를 구했다. Map에 String과 이동횟수를 저장하며 방문처리를 해줬고, "123456780"이 된다면 퍼즐의 완성이므로 Map에서 이동횟수를 꺼내어 출력했다.  메모리: 122456KB시간: 1048ms언어: Java 11import ja.. 2024. 5. 15.
[백준] 14867: 물통 - JAVA https://www.acmicpc.net/problem/14867 풀이용량이 정해진 물통을 주어진 용량으로 맞춰야 한다. 할 수 있는 동작은 정해져있는데 1. 물통 x에 물을 가득 채운다. 2. 물통 x의 물을 모두 버린다. 3. 물통 x의 물을 물통 y에 붓는다. 위의 세가지를 통해 용량을 맞출 때 최소 작업 수를 구해야 한다. 두 개의 물통을 0, 0상태에서 시작하여 bfs탐색을 통해 정해진 양을 맞추면 return했다. 이때 방문처리를 하기 위해 class를 만들어 set으로 체크하였다. set의 contains 메서드를 이용할 때 객체의 경우 비교하기 위해서는 class에 equals와 hashcode를 오버라이드해야 했다. 이 점만 알고 있다면 크게 어려운 것 없는 문제였다.  메모리: 146.. 2024. 5. 14.
[백준] 3020: 개똥벌레 - JAVA https://www.acmicpc.net/problem/3020 풀이석순과 종유석이 번갈아 나오는 동굴을 장애물을 파괴하면서 지나가야한다. 높이별로 만나는 장애물의 개수를 세어 최솟값을 찾는 문제이다. 처음에 누적합으로 문제를 풀었고, 이분 탐색으로 푸는 방법이 있다고하여 찾아보았다. - 이분 탐색   이분 탐색으로 풀기 위해서는 석순과 종유석을 따로 배열에 담아준다.   bottom배열에 석순을, top배열에 종유석을 담았다.   이분탐색을 위해 배열을 정렬한 뒤 1부터 H까지 높이을 key로 하여 이분탐색을 진행한다.   석순과 종유석을 각각 진행하여 해당 key값(key값보다 크거나 같은 첫번째 인덱스)을 찾아 arr.length - rigth을 반환하면 해당 구간의 장애물의 개수를 구할 수 있다.. 2024. 5. 14.
[백준] 9081: 단어 맞추기 - JAVA https://www.acmicpc.net/problem/9081 풀이C++에 있는 next permutation 함수를 구현하는 문제이다. 어떤 문자가 주어지면 그 문자의 알파벳들로 만들 수 있는 문자들 중 처음 주어진 문자의 다음에 올 문자를 찾는 문제였다. 조합으로 모든 경우를 만들어 set에 넣는 방식으로 구현하였는데 메모리초과로 실패했다. next permutaion이란 방법을 찾아 구현해보았다.1. 뒤에서부터 탐색하여 증가하지 않는 첫번째 인덱스를 찾는다.2. 다시 뒤에서부터 탐색하여 찾은 인덱스의 값보다 처음으로 큰 값이 나오는 인덱스를 찾는다.3. 두 인덱스의 값을 바꾸고 인덱스 뒤 부분을 정렬하여 붙인다.따라서, 주어진 단어를 int배열로 만들어 구현했다. 뒤에서부터 탐색해 값이 감소하는.. 2024. 5. 14.
[백준] 2250: 트리의 높이와 너비 - JAVA https://www.acmicpc.net/problem/2250 풀이트리를 격자모양의 틀에 넣을 때 트리의 깊이별로 너비를 구했을 때 최댓값을 찾는 문제. 입력받으면서 트리를 저장하는데, 부모, 왼쪽 자식, 오른쪽 자식을 저장한다. 입력받아서 저장한 후 부모가 -1로 되있는 것이 루트 노드이다. 루트노드부터 중위순회(왼쪽 - 루트 - 오른쪽)하여 탐색하면 열 번호를 1부터 순서대로 부여할 수 있다. 중위순회할 때 트리의 깊이(level)도 함께 넘겨 각 깊이별로 열 번호의 최대와 최소를 저장한다. 중위순회를 마친 후 깊이별로 너비의 최댓값을 구한다.  메모리: 21176KB시간: 256ms언어: Java 11import java.io.*;import java.util.*;public class Main.. 2024. 5. 14.
[백준] 3025: 돌 던지기 - JAVA https://www.acmicpc.net/problem/3025 풀이주어진 조건에 맞게 위에서부터 돌을 떨어뜨려 최종 상태를 출력하는 문제였다. 단순한 구현으로 하나씩 진행하며 문제를 풀었을 때는 시간초과가 발생했다. 시간초과를 해결하기위해 메모이제이션을 해야했다. 처음 돌을 놓는 열 별로 stack을 만들어 돌이 이동하는 경로를 저장했다. 새로운 돌을 던질 때 stack에 경로가 들어있다면 마지막에서부터 진행하면 된다.1. 돌의 아랫칸이 벽으로 막혀있거나 가장 아랫줄이라면, 돌은 그 자리에 그대로 멈춰 있는다.2. 돌의 아랫칸이 비어있다면, 돌은 아랫칸으로 이동한다.3. 돌의 아랫칸에 돌이 있다면, 돌은 다음과 같이 미끄러진다. 1. 만약 돌의 왼쪽 칸과 왼쪽-아래 칸이 비어있다면, 돌은 왼쪽으.. 2024. 5. 14.
[백준] 1300: K번째 수 - JAVA https://www.acmicpc.net/problem/1300 풀이이차원배열의 각 칸에 i X j 의 숫자들이 들어있다. 이들을 일차원배열에 넣어 정렬했을 때 k번째 숫자를 구해야한다. 풀이 방법이 떠오르지 않아 다른 블로그들의 도움을 받았다. 이차원배열의 각 행들이 구구단으로 이루어져 있다. 구구단을 쭉 나열해보면 다음과 같다.1단: {1, 2, 3, 4, 5, 6, 7, 8, 9}2단: {2, 4, 6, 8, 10, 12, 14, 16, 18}...8단: {8, 16, 24, 32, 40, 48, 56, 64, 72}9단: {9, 18, 27, 36, 45, 54, 63, 72, 81}이 나열된 숫자에서 예를들어 7보다 작거나 같은 숫자가 몇개인지 구하려면 1단에서는 7 / 1 = 7 으로 7개가.. 2024. 5. 14.
[백준] 25307: 시루의 백화점 구경 - JAVA https://www.acmicpc.net/problem/25307 풀이이차원배열에 기둥이 있는 칸, 의자가 있는 칸, 마네킹이 있는 칸, 시작 위치를 입력받는다. 시작 위치에서 의자가 있는 칸까지 거리를 묻는 문제였다. 다만, 기둥이 있는 칸은 지나갈 수 없고, 마네킹과의 거리가 K 이하인 칸들은 지나갈 수 없다. 마네킹이 있는 칸을 입력받을 때 List에 저장해 bfs탐색을 통해 마네킹으로부터 거리가 K 이하인 칸들을 기둥이 있는 칸과 같게 만들었다. 이렇게 0으로된 칸은 모두 지나갈 수 있는 칸이 된다. 시작위치부터 bfs탐색을 통해 의자의 위치가 나오면 거리를 반환하고, 의자에 도달할 수 없으면(bfs의 while문이 끝나면) -1을 반환했다.  메모리: 395276KB시간: 1204ms언어: J.. 2024. 5. 14.

티스토리툴바