자료구조

[BOJ/JAVA] 23559번: 밥

23559번: 밥https://www.acmicpc.net/problem/23559키워드제주대 학생회관 식당에는 두 개의 메뉴가 있다.코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.NNN일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다.준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.준원이는 NNN일간 학식에 총 XXX원 이하를 써야 한다.고른 메뉴의 맛의 합을 최대화 해주자!구현일단 무조건 더 맛있는 메뉴를 고른다.이후 금액에 맞게끔 1,000원 짜리 메뉴로 바꾸었을 때 차이가 가장 적은 메뉴부터 교체해 나간다. boolean is5000[][i] 번째 고른 메뉴가 5000원 짜리 메뉴인가?더 맛..

[BOJ/JAVA] 20551번: 마스터 배지훈의 후계자

20551번: Sort 마스터 배지훈의 후계자https://www.acmicpc.net/problem/20551키워드먼저 제자들에게 N개의 원소를 가진 배열A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다.그 다음 M개의 질문을 한다.제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력단, D가 B에 존재하지 않는 경우에는 -1를 출력구현정렬 후 탐색이 이루어지므로, 입력값을 정렬할 필요가 있다.중요한 것은 가장 먼저 등장한 위치를 출력이므로 이분탐색으로 찾더라도 가장 앞에 있는 원소를 찾아야 한다. 템플릿low, high 모두 범위 안에 들어오도록 한다.반복문의 속행 조건은 low≤high (항상 high가 low 이상이여야 한다.)해당 숫자를 찾은 경우가장 앞에 있는 원..

[BOJ/JAVA] 1351번: 무한 수열

1351번: 무한 수열https://www.acmicpc.net/problem/1351키워드무한 수열 A는 다음과 같다.A_0 = 1A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.0 ≤ N ≤ 10^122 ≤ P, Q ≤ 10^9구현중요한 것은 N, P, Q의 범위가 매우 크다는 것이다.배열로 만들기에는 너무 크기 때문에, Map을 이용하여 필요한 데이터만 저장하도록 하자.int 대신 long 자료형을 이용하자statch HashMap cacheA_i에서 i일 때 A_i의 값을 저장한다.statc long dp(long index)index가 0인 경우1을 반환한다.캐시값이 존재하는 경우캐시값을 반환한다.A[index] = A_[i..

[BOJ/JAVA] 1822번: 차집합

키워드집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램구현집합 연산 중 차집합 연산을 이용하여 구현한다.A.removeAll(B)A집합에는 속하지만, B집합에는 속하지 않게 A를 바꾼다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Set; import java.util.StringTokenizer; import java.util.TreeSet; public class java_1822 { static Set aSet, bSet; public static void main(String[] args) throws IOExcepti..

[BOJ/JAVA] 9935번: 문자열 폭발

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Stack; public class java_9935 { public ..

[BOJ/JAVA] 5052번: 전화번호 목록

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.HashMap; public class java_5052 { ..

[BOJ/JAVA] 4195번: 친구 네트워크

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.HashMap; import java.util.StringTokenizer..

[BOJ/JAVA] 5021번: 왕위 계승

https://www.acmicpc.net/problem/5021 5021번: 왕위 계승 유토피아의 왕이 사망했다. 왕은 자손을 남기지 않고 사망했기 때문에, 왕위를 계승할 사람을 지목하지 않았다. 왕실 귀족은 왕위를 주장하기 시작했다. 유토피아의 법에는 왕의 계승자가 없는 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.HashMap; import java.uti..