기록방

👉 문제링크 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..

👉 문제링크 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자리 문자들이 공백없이 입력되므로, 구문해서 저장해야한다. 배열을 순회하며 정사각형의 네 꼭지점의 값이 같은 경우의 수 중에 너비..

👉 문제링크 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 n개의 숫자의 합으로 m을 만들 수 있는 경우의 수를 출력한다. m은 3억이므로 int형으로 충분하다. n개의 수의 합이 m이 되는지 매번 더해서 확인하면 시간초과가 날 것이다. 따라서 미리 누적 합 리스트 sum를 만들어 둔다. 인덱스 i부터 인덱스 j 까지의 합은 sum[j] - sum[i] 로 구할 수 있다. sum[0]은 0이다. sum[j] - sum[i] > m이면, 계속 커지는 ..

👉 문제링크 1411번: 비슷한 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복 www.acmicpc.net 🔸 문제 분석 🔸 n개의 문자열에서 서로 비슷한 쌍의 수를 출력한다. 비슷하다는 의미는 문자열의 문자가 같은 방식으로만 변환 된 상태이다. 다른 두 문자가 하나의 문자로 중복되어 변환되지 못한다. 시간복잡도를 계산해보자 n개의 문자열이 갖을 수 있는 모든 쌍을 계산하므로 선택정렬과 같다. O(n^2) 그 안에서 문자열을 하나씩 검사해야한다. O(m) 따라서 시간 복잡도는 O(n^2 * m) 계산하면 100*100*50 == 500,000(5..