자료 구조37 [백준] 1655: 가운데를 말해요 - JAVA https://www.acmicpc.net/problem/1655 풀이숫자를 입력할 때마다 말했던 숫자들 중 중간값을 말해야한다. PriorityQueue 2개를 사용해 left, right로 저장하고 left의 peek이 항상 중간값이 되도록 구현했다. 따라서, left는 내림차순으로 저장 및 출력했다. left가 비어있거나 left의 peek보다 말한 숫자가 작으면 left에 넣었다. 그렇지 않은 경우는 right에 넣는다. left 크기와 right 크기의 차이가 1보다 크면 left에서 빼서 right에 넣어주고, right의 크기가 더 크면 right에서 빼서 left에 넣어주었다. 즉, left의 크기와 right의 크기의 차이가 0, 1이 되도록 유지했다. 그렇게해서 left의 peek값이 .. 2024. 5. 13. [백준] 2812: 크게 만들기 - JAVA https://www.acmicpc.net/problem/2812 풀이스택을 이용하는 그리디 문제였다. N 자리 숫자에서 숫자 K 개를 지웠을 때의 최댓값을 구해야 한다. 숫자를 입력받으면서 stack에 하나씩 넣는다. 뺄 수 있는 개수(K)가 남아있고 stack의 끝값이 자신보다 작으면 그 값을 빼고 넣는다. 다만 N이 987654321과 같이 주어지면 stack에 들어가기만 하고 빠지는 숫자는 없다. 따라서 stack의 사이즈 - K 만큼 출력해 주어야 한다. 출력할 때 앞에서부터 빼기 위해서 stack 대신 deque을 이용했다. 메모리: 36464KB시간: 380ms언어: Java 11import java.io.*;import java.util.*;public class Main { pub.. 2024. 5. 13. [백준] 2143: 두 배열의 합 - JAVA https://www.acmicpc.net/problem/2143 풀이배열 2개가 주어지고 배열들의 부 배열들을 합하여 T를 만들는 경우의 수를 찾는 문제이다. 두 가지 방법으로 풀 수 있는 문제였다. 첫 번째로 생각한 방법은 Map을 사용해 containsKey를 이용하는 방법이었다. 배열 A의 부 배열들의 합을 map에 저장해 놓는다. 배열 B의 부 배열의 합을 구하면서 T에서 뺀 값이 A의 map에 있다면 map의 value 만큼 카운트하여 더해준다. 이 방법으로 제출하고 다른 풀이들을 보니 이분 탐색으로 푸는 방법도 있었다. List에 부 배열들을 저장하고 이분 탐색을 위해 정렬한다. ListA에서 값을 꺼내면서 T - 꺼낸 값을 찾을 값으로 하여 ListB에서 이분탐색을 통해 찾는다. 개수가 여.. 2024. 5. 12. [백준] 20303: 할로윈의 양아치 - JAVA https://www.acmicpc.net/problem/20303 풀이dp와 분리집합을 이용하는 문제. 사탕을 최대로 뺏어야 하는 문제였다. 친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다. 한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다. 각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다. 따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다. 저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다. 메모리: 875636KB시간: 1152ms언어: Java 11import java.io.*;import java.util.*;pub.. 2024. 5. 12. [백준] 1717: 집합의 표현 - JAVA https://www.acmicpc.net/problem/1717 풀이자료구조, 서로소집합 문제. 집합들이 있고, 합집합연산과 서로 같은 집합인지 확인하는 연산이 있다. 배열을 집합의 개수만큼 만들고 자신의 번호로 초기화 한다. 자신의 그룹을 찾는 함수, 그룹을 합치는 함수, 같은 그룹인지 확인하는 함수 3가지를 구현해야 한다. 자신의 그룹을 찾는 findGroup 함수에서는 배열의 값을 findGroup의 결과값으로 갱신하면서 어떤 그룹에 속해있는지 찾는다. 그룹을 합치는 grouping 함수에서는 findGroup을 한 결과들을 이용해 두 집합을 하나의 그룹으로 묶어준다. 같은 그룹인지 확인하는 check 함수에서는 마찬가지로 findGroup을 한 결과가 서로 같은지 여부를 판단한다. 메모리: 5.. 2024. 5. 12. [백준] 6198: 옥상 정원 꾸미기 - JAVA https://www.acmicpc.net/problem/6198 풀이그리디스러운 문제였다. 알고리즘 분류는 자료 구조, 스택. 자기보다 오른쪽에 있는 빌딩을 보는데 높이가 자기보다 낮은 빌딩을 볼 수 있다. 중간에 같거나 높은 빌딩을 만나면 그 다음부터 빌딩은 보지 못한다. 나는 현재 빌딩의 높이를 기준으로 이 빌딩을 볼 수 있는 왼쪽 빌딩들의 개수를 카운트했다. stack에 빌딩의 높이를 담으면서 진행하며 현재 빌딩보다 낮은 빌딩을 스택에서 빼줬다. stack의 사이즈를 답에 더해주고 현재 빌딩을 stack에 넣어주면 끝. 메모리: 24236KB시간: 324ms언어: Java 11import java.io.*;import java.util.*;public class Main { public s.. 2024. 5. 12. [백준] 2800: 괄호 제거 - JAVA https://www.acmicpc.net/problem/2800 풀이브루트포스 문제. 괄호의 쌍을 매칭하여 출력하거나 출력 안 하거나 하면 되는 문제였다. 서로의 짝을 매칭 시킬 방법으로 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 제일 위에 있는 괄호와 짝을 맺는다. 서로의 짝의 번호를 배열에 저장했다. 짝을 모두 저장한 후 dfs 탐색을 통해 해당 괄호를 boolean 배열에 true, false로 체크하여 출력할지 안 할지를 저장했다. 중복 식을 제거하기 위해, 사전 순으로 정렬하기 위해 TreeSet을 이용했다. 메모리: 24900KB시간: 280ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12. 이전 1 2 3 4 다음