기록방

👉 문제링크 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 🔸 문제 분석 🔸 입력된 문자열 S에서 P 길이의 부분 문자열을 만들었을때, 입력된 DNA 문자열 최소 개수를 충족하는 경우의 수를 출력한다. 슬라이딩 윈도우 알고리즘을 이용해서 P길이의 부분 문자열을 문자열 S의 시작점부터 오른쪽으로 밀어간다. 윈도우에서 벗어나는 인덱스는 현재 상태에서 빼기 윈도우에 새로 들어오는 인덱스는 현재 상테에 더하기 조건에 충족 하는지 확인해서 카운트 🔸 코드 🔸 import java.io.Buffe..

👉 문제링크 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 🔸 문제 분석 🔸 문자열 A와 B가 주어지고, A를 최대한 B에 비슷하게 앞 뒤로 문자를 추가한다. 문자가 다른 인덱스의 수를 출력한다. A는 B보다 길이가 작거나 같다. 문자열 B에서 문자열 A를 겹쳤을때 가장 많이 겹치는 부분을 찾는다. 문자열 A의 길이에서 겹친 부분의 수를 뺀 값이 가장 클 때를 찾아 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io..

👉 문제링크 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나 www.acmicpc.net 🔸 문제 분석 🔸 세 점의 좌표가 주어지면, 만들 수 있는 평행사변형 중 가장 큰 너비에서 가장 작은 너비를 뺀 값을 출력한다. 세 점으로 그릴 수 있는 평행사변형은 3가지가 나오는데, 그 중 2가지는 같을 수 있다. 평행사변형을 만들 수 없는 경우는 세 점이 한 직선위에 존재할 때이다. 두 점의 기울기 (x증가량/y증가량)을 확인해서, 기울기가 같으면(한 선분 위에 존재하면) -1.0 을 출력한다. 그릴 수 있는 평..

👉 문제링크 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 🔸 문제 분석 🔸 l개의 배열 S의 원소를 포함하지 않고, n은 포함하는 범위( [a,b] )의 경우의 수를 출력한다. 배열 원소를 n과 하나씩 비교해서 범위를 찾는다. 원소가 n보다 작고 기존의 a보다 크거나 같으면, a에 저장한다. 원소가 n보다 크고 기존의 b보다 작거나 같으면, b에 저장한다. 만약 원소가 n과 같다면, 범위가 생길 수 없으므로 0을 출력하고 종료한다. a부터 b중에 n을 포함하는 범위의 수를 세고 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import..

👉 문제링크 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 🔸 문제 분석 🔸 입력 된 n x m크기의 수 배열에서 정사각형을 그렸을때 꼭지점이 같은 수인 경우에서 가장 큰 정사각형의 너비를 출력한다. 정사각형 한 변의 길이를 늘려가며 배열을 탐색해야 한다. 배열의 최대 크기는 50 x 50이므로 시간복잡도가 O(n^3)이라고 해도 50^3 = 125,000으로 시간은 여유있다. 1자리 문자들이 공백없이 입력되므로, 구문해서 저장해야한다. 배열을 순회하며 정사각형의 네 꼭지점의 값이 같은 경우의 수 중에 너비..