문제 링크 1. 문제 풀이 문자열 $S$ 안에 문자열 $W$ 의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 세는 문제로 $g$ 의 범위가 최대 $3,000$, $S$ 의 길이가 최대 $3,000,000$ 이라서 효율적인 탐색이 필요하다. 슬라이딩 윈도우를 기본으로 현재 윈도우에 대한 카운팅 배열을 적용하면 해결할 수 있다. ...

문제 링크 1. 문제 풀이 주어진 문자열에서 최소 교환 횟수로 $a$ 가 연속이 되게 해야한다. 이때 교환은 두 문자의 위치를 바꾸는 것이다. 문자열의 양 끝은 원형으로 연결되어 있다. 예제 입력 1을 예로 들자면, 주어진 문자열은 아래와 같다. 표시된 두 문자를 교환한다. 표시된 두 문자를 교환한다. ...

문제 링크 1. 문제 풀이 주어진 문자열에 대해 고정된 길이의 임의의 구간이 비밀번호의 조건을 만족하는 경우의 수를 구하는 문제다. 조건은 구간이 각 문자를 특정 개수 이상 포함해야 한다. 문자열과 구간의 최대 길이가 $1,000,000$ 이라는 점에서 $O(N^2)$ 풀이는 시간 초과가 발생하는데 슬라이딩 윈도우를 활용하면 해결할 수 있다...

문제 링크 1. 문제 풀이 주어진 임금으로 만들 수 있는 수열에서 구간의 길이가 $m$ 인 구간 중 구간 합이 가장 큰 경우를 찾는 문제다. 누적 합을 활용해도 해결할 수 있고 슬라이딩 윈도우를 활용해도 해결할 수 있다. 주어진 임금의 합이 정수 타입 범위를 넘어갈 수 있음에 주의해야 한다. 2. 코드 1. 누적 합 [Java] ...

문제 링크 1. 문제 풀이 두 배열을 합친 배열을 정렬한 뒤 출력하는 문제로 두 배열의 크기의 합만큼의 배열에 원소를 옮기고 정렬해도 되고, 각 배열을 정렬 후 투 포인터로 원소를 순서대로 넣어줘도 된다. 투 포인터 방식은 병합 정렬의 병합 과정과 유사하다고 봐도 된다. 2. 코드 1. 정렬 [Java] import java.i...

문제 링크 1. 문제 풀이 두 정수는 콤마로 구분된다. 따라서 콤마를 기준으로 파싱한 후 합을 구하면 된다. 2. 코드 1. 풀이 [Java] StringTokenizer를 활용하여 콤마를 기준으로 파싱했다. 이후 $A + B$ 의 결과물을 StringBuilder에 담았다가 한번에 출력하는 방식으로 최적화했다. import ...

문제 링크 1. 문제 풀이 문자열 $S$ 에 포함된 정수는 콤마로 구분된다. 따라서 정수의 개수는 콤마를 기준으로 파싱을 해도 되고 그냥 콤마의 수 $+1$ 로 구해도 된다. 2. 코드 1. 풀이 [Java] import java.io.*; public class Main { public static void main(...

문제 링크 1. 문제 풀이 삼각형의 종류에 따라 다른 문구를 출력하는 문제로 삼각형이 될 수 없는 조건은 가장 긴 변의 길이가 다른 두 변의 길이보다 크거나 같은 경우인 것만 주의하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main {...

문제 링크 1. 문제 풀이 에라토스테네스의 체에서 탐색한 수들을 카운팅하면 되는 문제로 에라토스테네스의 체 로직 중간에 탐색에 거쳐간 값들을 카운팅하는 방식으로 해결했다. 이때 에라토스테네스의 체는 중복 탐색을 하므로 방문 체크를 통해 방문한 적 없는 값들만 카운팅 해야 한다. 2. 코드 1. 풀이 [Java] import ja...

문제 링크 1. 문제 풀이 주어진 수들을 소인수분해한 결과를 출력하는 문제로 에라토스테네스의 체를 활용해 소수들을 얻고 이 소수들로 $1$ 이 될 때까지 반복적으로 나누면 된다. 2. 코드 1. 풀이 [Java] 소수를 리스트로 얻은 후 각 소수들로 나눌 수 있으면 나누고 몫을 카운팅하는 방식으로 구현했다. 에라토스테네스의 체의...