본문 바로가기
728x90

java129

[백준] 1786번 : 찾기(JAVA) https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 풀이 기존 KMP알고리즘에서 달라진 부분은 같은 부분이 나올때 count를 세주고 위치를 저장해서 마지막에 출력해주는 부분입니다. ArrayList를 통하여 위치를 저장해주고 count를 선언하여 ++해줍니다(전역) 여기서 StringBuilder를 써주냐 안써주냐의 차이로 시간이 2500ms 가량이 차이납니다(확실 x) 소스코드 import java.io.BufferedReader; imp.. 2021. 8. 26.
[백준] 16916번 : 부분 문자열(JAVA) https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 풀이 KMP와 문자열문제입니다.(KMP를 안다면 바로 풀 수 있는 문제) 먼저 getpi()함수를 통하여 맞추고자 하는 글자의 중복위치를 체크해줍니다. KMP()함수를 통하여 처음 문자열과 두번째 문자열을 1글자씩 비교합니다. 비교하면서 같을 경우 위치(j)를 증가시켜주고 j가 0보다 크고 서로 다를경우 맞는 위치까지 내려가기 위해 while문으로 j를 줄여줍니다. for문이 끝날때까지 없다면 0, j가 두번째 문자열의 길.. 2021. 8. 26.
[백준] 1003번 : 피보나치 함수(JAVA) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 특정숫자가 될때까지의 0의 갯수, 1의 갯수를 구하는 문제입니다. 2차원 dp배열로 푸시면됩니다. 0의 갯수배열, 1의 갯수배열을 만들고 피보나치dp처럼 구하시면 됩니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ Bu.. 2021. 8. 23.
[백준] 11660번 : 구간 합 구하기 5(JAVA) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 1,1구간부터 합을 구한 후 풀면 됩니다. 1,1일 경우 0,1 + 1,0 - 0,0 + 1,1 이 1,1까지의 합이 됩니다. 차이를 구하는 방식도 2,2 1,1일 경우 2,2 - 2,0 - 0,2 + 0,0이 됩니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import ja.. 2021. 8. 23.
728x90

티스토리툴바