자료 구조37 [백준] 15809: 전국시대 - JAVA https://www.acmicpc.net/problem/15809 풀이각 국가에 군대가 있고, 국가들은 동맹, 전쟁을 통해 군대에 변화가 생긴다. 동맹을 맺으면 두 국가를 연합하여 하나의 국가로 만든다. 군대의 수는 합쳐진다. 전쟁을 하면 두 국가가 전쟁을 하여 군대의 수가 적은 국가는 속국이되고, 군대의 수는 소모된다. 두 국가가 같은 집합에 속하는지 확인하기 위해 서로소 집합을 이용했다. ``` findSet(int x)``` 메소드를 통해 해당 국가의 루트 국가를 찾는다. ``` union(int p, int q)``` 두 국가 p와 q를 동맹으로 묶는다. 군대의 수가 많은 국가를 루트로 설정하고 군대의 수를 합쳤다. ``` battle(int p, int q)``` 두 국가 p와 q가 전쟁을 벌.. 2024. 6. 11. [백준] 2015: 수들의 합 4 - JAVA https://www.acmicpc.net/problem/2015 풀이주어진 수열에서 부분 수열의 합이 k가 되는 경우를 찾는 문제이다. 누적합과 맵을 이용해 해결했다. ```sum[i]```에서 k를 뺀 값이 이전에 등장한 적이 있는지를 확인한다. 현재 누적합이 ```sum[i]```라고 할 때, ```sum[i]-k```가 이전에 등장한 적 있다면 그 구간의 합이 k라는 것을 의미한다. 메모리: 33452KB시간: 348ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br =.. 2024. 6. 10. [백준] 23843: 콘센트 - JAVA https://www.acmicpc.net/problem/23843 풀이충전기 m개로 n개의 전자기기를 충전해야한다. 전자기기마다 충전이 완료되는데 필요한 시간이 달라서 충전기에 전자기기를 적절하게 배치해야한다. 충전기가 비어있다면 충전에 걸리는 시간이 가장 긴 기기를 배치하는 게 적절했다. 따라서 우선순위큐를 이용해 시간이 오래걸리는 순으로 뽑아서 충전기에 넣었다. 충전기에 넣으면서 걸리는 시간을 정답에 갱신하면된다. 메모리: 15476KB시간: 180ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Charger { PriorityQueue chargers; Priority.. 2024. 5. 22. [백준] 3078: 좋은 친구 - JAVA https://www.acmicpc.net/problem/3078 풀이학생의 이름이 등수 순으로 주어진다. 등수가 k를 넘지 않으면서 이름의 길이가 같으면 좋은 친구이다. 좋은 친구의 쌍을 구해야 한다. 처음에는 단순히 큐를 사용하면 되는 문제인 것 같았다. 하지만 메모리초과... 어떻게 푸는지 방법을 찾아보았다. 이름의 길이가 2~20이므로 길이 20의 큐 배열을 선언한다. 입력받은 문자열의 길이를 len이라고 한다면, 큐 배열의 len 인덱스에 들어있는 값이 해당 번호와 자신의 번호의 차가 k보다 크다면 poll 해준다. poll 해준 뒤 남아있는 개수를 정답에 더해준다. 그 후 같은 인덱스에 자신의 등수를 넣어주면 된다. 메모리: 47332KB시간: 368ms언어: Java 11import jav.. 2024. 5. 19. [백준] 16562: 친구비 - JAVA https://www.acmicpc.net/problem/16562 풀이k원의 예산으로 모든 사람과 친구가 되는 방법을 구해야 한다. 친구마다 각각 원하는 친구비가 주어지고, 해당 학생과 어떤 학생이 친구인지 주어진다. 다만, 친구의 친구는 친구이기 때문에 이를 이용해 최소한의 비용으로 친구가 되어야 한다. 따라서 주어진 친구들의 관계를 이용해 그룹을 지었다. 각 그룹에 한 번 씩만 친구비를 전달하면 모든 친구와 친구가 될 수 있다. union 메서드를 이용해 그룹을 지어주었다. 이떄 그룹의 대표 번호는 친구비가 가장 적은 사람으로 저장해주었다. 그룹을 모두 지은 뒤, 친구비를 더해 계산해주었다. 메모리: 18320KB시간: 220ms언어: Java 11import java.io.*;import jav.. 2024. 5. 19. [백준] 16724: 피리 부는 사나이 - JAVA https://www.acmicpc.net/problem/16724 풀이N * M 지도에 U, D, L, R이 주어진다. 각 칸에서 어느 방향으로 한 칸 이동할 수 있는지를 나타낸다. 각 칸에서 이동시키기 편하게 하기 위해 U, D, L, R을 0, 1, 2, 3으로 치환하여 저장했다. 방문처리가 안된 칸에서부터 dfs를 시작하여 이동할 수 있는 칸을 지날때 union메서드를 통해 같은 그룹으로 묶어주었다. 최종적으로 그룹의 수를 구하면 답이 된다. 메모리: 72688KB시간: 560ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] vector = { { -1, 0 }, { 1, 0 }, { 0, .. 2024. 5. 19. [백준] 24391: 귀찮은 해강이 - JAVA https://www.acmicpc.net/problem/24391 풀이건물을 돌아다닐 때, 서로 연결되어있는 건물은 밖으로 안나가고 이동할 수 있다. 몇 번 밖으로 나와야하는지 구해야한다. 서로 연결된 건물들을 union메서드를 이용해 한 parent로 묶었다. 그렇게해서 i번 건물과 i-1번 건물이 parent가 다르다면 answer을 1증가시켰다. 메모리: 52100KB시간: 456ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[] parent; public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 5. 19. [프로그래머스] 주사위 고르기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이n개의 주사위를 2명이 나눠가진다. 주사위에 쓰인 수의 구성은 모두 다르다. 나눠 가진 주사위들의 합을 구해 점수가 큰 쪽이 승리하는데, A가 승리할 확률이 높도록 주사위를 나눠야 하는 문제이다. 먼저 주사위를 어떻게 나눌지 완탐했다. getDice()메소드를 만들어 비트마스킹을 이용해 어떤 주사위를 A가 선택할지 정해주었다. 선택이 완료되면 calculateWinRate()메소드를 통해 승률을.. 2024. 5. 19. [백준] 7578: 공장 - JAVA https://www.acmicpc.net/problem/7578 풀이A열과 B열에 같은 숫자들을 연결할 때, 케이블들이 서로 교차하는 부분의 개수를 세는 문제이다. A열: 1 2 3 4 5 B열: 2 4 1 3 5 위와 같이 주어졌을 때, B열에서 A열로 줄을 쏴주었다. B열의 2에서 A열의 2로 줄을 쐈을 때, A열의 2보다 오른쪽에 이미 연결된 점이 있다면 그 점이 교차하는 점이다. B열은 앞에서부터 순서대로 보는데, A열의 연결된 점 오른쪽으로 연결된 점이 있다는 것은 B열의 앞쪽 점과 연결되어 있다는 것이므로 교차한다는 것이다. A열의 인덱스를 저장해주었고, B열의 점이 A열의 어떤 인덱스와 연결되는지 저장했다. 세그먼트 트리를 이용해 A열의 인덱스부터 N까지 구간합을 구해 교차점이 몇개인지 구.. 2024. 5. 18. [백준] 10868: 최솟값 - JAVA https://www.acmicpc.net/problem/10868 풀이N개의 정수 배열의 a~b구간에서의 최솟값을 찾아야 한다. 세그먼트트리를 만들어 구간별로 최소값을 갖는 배열의 인덱스를 저장했다. a~b구간에서 최솟값의 인덱스를 찾아 배열의 값을 출력하면 된다. 인덱스를 저장하지 않고 최솟값 자체를 세그먼트트리에 저장하는 것도 좋다. 메모리: 48788KB시간: 600ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class SegmentTree { int[] tree; int treeSize; public SegmentTree(int arrSize) { .. 2024. 5. 18. 이전 1 2 3 4 다음