알고리즘
백준 JAVA 21314번 민겸수
백준 JAVA 21314번 민겸수
2021.12.28문제 링크: https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 문제 풀이 가장 큰 수의 조건 M이 K를 만날 때까지 상태를 유지하는 것이다. ( ex = MMK -> 500, MMMK->5000 ) M이 연속 될 시 1로 상태 변환한다. ( ex = MMM-> 111, MM-> 11 ) 가장 작은 수의 조건 K는 바로 5로 상태 변환한다. ( ex = MMK -> 105, KK -> 55 ) M은 연속 될 시 제곱의 형태로 변환한다. ( ex = MMMK -> 1005, MMMM-> 1000 ) 위의 조건들을 만족시키는 코드..
백준 JAVA 17413번 단어 뒤집기 2
백준 JAVA 17413번 단어 뒤집기 2
2021.12.27문제 링크: https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 해설 ''로 감싸져 있는 문자들은 뒤집지 않고 ' ' 공백으로 나눠져 있는 문자들을 뒤집는다. ''가 등장할 때까지 StringBuilder에 넣어준다. 공백이 나온다면 바로 StringBuilder에 넣어준다. ' ', ''); i=j; } else if(s.charAt(i)==' '){ sb.append(" "); } else{ int j=i;..
백준 JAVA 16916번 부분 문자열
백준 JAVA 16916번 부분 문자열
2021.12.25문제 링크: https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 비교하는 문자열의 길이가 짧다면 반복문을 중첩시켜 구할 수 있겠지만, 두 문자열의 최대 길이가 100만이므로 시간초과가 날 것이다. 따라서 KMP 알고리즘을 사용해야 한다. 해당 알고리즘은 접두사와 접미사를 활용하여 판별한다. import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int t; sta..
백준 JAVA 9342번 염색체
백준 JAVA 9342번 염색체
2021.12.21문제 링크: https://www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net 문자열의 조건들을 순차적으로 확인하는 문제이다. String.indexOf()와 String.lastIndexOf()를 이용하면 쉽게 해결이 가능하다. indexOf(char) char와 같은 첫 번째 index를 반환하며 lastIndexOf(char) char와 같은 마지막 index를 반환해준다. 해당 조건들을 하나씩 체크해주면 된다. import java.math.BigIn..
백준 JAVA 1992번 네트워크 연결
백준 JAVA 1992번 네트워크 연결
2021.12.20문제 링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 해당 문제는 최소신장트리의 개념에 가중치가 생겨 모든 정점을 연결할 때 최소 비용을 구하는 문제다. 크루스칼 알고리즘 과 프림 알고리즘으로 해결이 가능하다. find() 함수로 정점의 부모를 찾고 union() 함수로 부모가 다를 경우 부모를 같게 해주어 최소신장트리 조건을 만족시켜준다. 이때 PriorityQueue를 사용하여 가중치를 오름차순으로 정렬시켜준 후 작은 가중치 순서로 진행해준다. import java.math.BigInteger; import java.uti..
백준 JAVA 11657번 타임머신
백준 JAVA 11657번 타임머신
2021.12.19문제 링크: https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 음의 가중치가 있으므로 다익스트라 알고리즘으로는 해결할 수 없다. 따라서 벨만포드 알고리즘을 이용한다. 벨마포드 알고리즘을 이용함에 있어서 음의 사이클이 있으면 안되므로 해당 로직을 한 번더 실행하여 음의 사이클이 있는지 체크해준다. import java.util.*; import java.io.*; class node{ i..