분류 전체보기
백준 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 17609번 회문
백준 JAVA 17609번 회문
2021.12.24문제 링크: https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제를 접할 때 회문이 아닐 경우에 for문을 중첩해서 한 글자씩 빼낸 후 확인을 했을 경우 시간초과가 나왔다. (해당 코드 첨부) import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int t; static boolean check; public static void main(String [] ar..
백준 JAVA 11722번 가장 긴 감소하는 부분 수열
백준 JAVA 11722번 가장 긴 감소하는 부분 수열
2021.12.23문제 링크: https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 해당 문제를 처음에는 DFS로 시도했지만 시간초과로 실패했다. 그래서 DP로 다시 풀어 보았다. import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int [] arr; static int t; ..
백준 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..