import java.io.*;
import static java.lang.Integer.parseInt;
public class Main {
static final int LEN = 41;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = parseInt(br.readLine());
int m = parseInt(br.readLine());
int[] vip = new int[m]; // 고정석 저장
int[] dp = new int[LEN]; // dp 초기화 41개 좌석
for (int i = 0; i < m; i++) vip[i] = parseInt(br.readLine()); // vip 입력 받기
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; // n번까지 설정
int answer = 1; // n == 1일 때 answer는 1
int preIdx = 0; // 곱셉을 위한 이전 위치
for (int idx : vip) {
answer *= dp[idx - preIdx - 1]; // 인덱스 - 이전 인덱스 - 1을 함으로써 연속된 좌석을 길이 구하기
preIdx = idx; // 인덱스를 업데이트하여 dp 길이
}
answer *= dp[n - preIdx]; // 마지막 고정석으로부터 연속된 좌석 dp
System.out.println(answer);
}
}
고정석을 설정하고나면, 고정석 이전 혹은 사이, 이후에 있는 좌석들은 각각 새로운 길이의 좌석이라고 볼 수 있습니다.
즉, 인접한 3개, 인접한 1개, 인접한 3개의 좌석의 dp를 구한 후 세 개는 모두 동시에 발생하므로 곱하여 값을 구할 수 있습니다.
이러한 원리를 구현한 코드가 아래의 코드입니다.
int answer = 1; // n == 1일 때 answer는 1
int preIdx = 0; // 곱셉을 위한 이전 위치
for (int idx : vip) {
answer *= dp[idx - preIdx - 1]; // 인덱스 - 이전 인덱스 - 1을 함으로써 연속된 좌석을 길이 구하기
preIdx = idx; // 인덱스를 업데이트하여 dp 길이
}
answer *= dp[n - preIdx]; // 마지막 고정석으로부터 연속된 좌석 dp
import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;
public class Main {
static int n;
static int answer;
static int[][] fromTo;
static int [][] dp;
static int INF = 987654321;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = parseInt(br.readLine());
fromTo = new int[n][n];
dp = new int[1 << n][n]; // 디피 설정
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) fromTo[i][j] = parseInt(st.nextToken());
}
answer = tsp(1, 0); // 방문, 위치
System.out.println(answer);
}
static int tsp(int visited, int loc) {
if (visited == (1 << n) - 1) {
if (fromTo[loc][0] > 0) return fromTo[loc][0]; // 값이 유효함
return INF; // 간선이 없어서 최대값으로 설정
}
if (dp[visited][loc] > 0) return dp[visited][loc]; // 현재 방문한 상태가 최신 상태로 업데이트 된 경우
dp[visited][loc] = INF; // 아직 방문하지 않았음을 의미함
for (int dest = 0; dest < n; dest++) {
if (isValid(visited, loc, dest))
dp[visited][loc] = Math.min(dp[visited][loc],
tsp(visited | (1 << dest), dest) + fromTo[loc][dest]);
}
return dp[visited][loc];
}
// 비트마스크의 & 연산으로 아직 방문하지 않은 경우 == 같은 위치에 1이 존재하지 않는 경우 == 0 && 방문 하려는 곳의 간선이 존재
static boolean isValid(int visited, int loc, int dest) {
return (visited & (1 << dest)) == 0 && fromTo[loc][dest] > 0;
}
}
2. TSP (Traveling Salesman Problem)
TSP는 외판원 문제로 외판원이 각 독시를 정확히 한 번씩 방문하고, 처음 출발한 도시로 돌아오는 가장 짧은 경로는 무엇인지 구하는 문제입니다. 이 문제는 NP-완전 문재로 모든 가능한 경우를 탐색하여 최적 해를 구할 수 있습니다.
3. DP와 비트마스킹
DP와 비트마스킹으로 TSP 문제를 해결할 수 있습니다. DP를 사용할 경우 시간 복잡도는 O(N^2 * 2^N)으로 해결할 수 있습니다.
N^2: 모든 도시 간의 거리를 계산하는데 필요한 시간을 나타냅니다. 각 도시에서 다른 모든 도시로 이동하는 비용을 확인하는 단계입니다.
2^N: 각 도시의 방문 상태를 고려해야 합니다. 비트마스킹을 사용하므로 2^N으로 (ex 010100) 형태로 각 방문 상태를 설정할 수 있습니다.
이러한 방법을 토대로 브루트 포스 방법으로 탐색할 경우 가지는 N! 보다 빠른 속도로 탐색을 수행할 수 있습니다.
N개의 노드가 있을 때, 방문 상태를 1 << N의 비트로 관리하면 방문 상태를 유지할 수 있습니다.
0010의 경우 2번 인덱스 노드는 방문한 상태를 의미하고, 0011은 2, 3번 노드를 방문한 상태를 의미합니다.
visited | (1 << n); // n을 방문 처리
visited & (1 << n); // n이 방문을 했는지 안했다면 0
자바에서 비트의 OR은 '|' 로 계산할 수 있습니다.
0010 | 0100 = 0110 을 구할 수 있습니다.
AND 연산은 '&'로 구할 수 있습니다. 같은 위치에 1이 있어야 1이 인정됩니다.
0010 & 0100 = 0000
이를 토대로 visited | (1 << n)을 해석하면,
현재 방문한 상태의 visited 값과 or 연산을 진행하는데, 대상은 1 << n입니다.
1 << n은 1에서 n개까지를 오른쪽으로 시프트 시키는 것을 의미합니다. 즉,
1 << 3 = 1000(2)를 의미하는 것입니다.
만약 visited = 10000(2) 였다면, visited | (1 << n)은 11000(2)의 값을 가질 수 있습니다.
AND연산은 방문을 이미 했는지를 판단해야 하므로 같은 위치에 1이 있는지를 판단하게 됩니다. 만약 0이라면 같은 자리에 1이 없다는 것을 의미하므로 방문하지 않았음을 의미합니다.
한 가지 의문점은 왜 굳이 비트마스킹으로 visited를 설정하는가입니다
이는 비트열로 visited를 수정하고 바꾸는 과정을 수행하므로 따로 boolean 배열을 설정하지 않더라도 문제를 해결할 수 있습니다.
또한 비트는 다른 연산보다 더 빠르게 연산이 가능하므로 효율적으로 계산을 수행할 수 있습니다.
4. 풀이 중점 사항
이를 토대로 코드를 살펴보면 다음과 같습니다.
TSP 문제를 해결하기 위해 DP와 비트마스킹을 활용합니다. 0, 0의 정점에서 시작하여 각 정점까지 이동이 가능한지 파악하고 방문하지 않았다면 방문합니다. 방문한 노드에서 현재 모두 방문해서 마지막 다시 시작점으로 이동해야 하는지, 혹은 이전에 이미 값을 업데이트했는지 등을 파악합니다. 이러한 재귀를 마치게 되면, 최종적으로 가장 짧은 순회 길이를 구할 수 있습니다.
1열 2열 3열
1행 0 1 2
2행 1 0 1
3행 0 0 0
이 상태에서 예를 들어 (0, 0)으로 시작을 하면, (0,1)을 거치게 됩니다.
(1, 3) 열을 거치게 되고 (3, 1) 열을 거쳐서 값을 리턴하는 방식으로 재귀형태로 진행이 됩니다.
static int tsp(int visited, int loc) {
if (visited == (1 << n) - 1) {
if (fromTo[loc][0] > 0) return fromTo[loc][0]; // 값이 유효함
return INF; // 간선이 없어서 최대값으로 설정
}
if (dp[visited][loc] > 0) return dp[visited][loc]; // 현재 방문한 상태가 최신 상태로 업데이트 된 경우
dp[visited][loc] = INF; // 아직 방문하지 않았음을 의미함
for (int dest = 0; dest < n; dest++) {
if (isValid(visited, loc, dest))
dp[visited][loc] = Math.min(dp[visited][loc],
tsp(visited | (1 << dest), dest) + fromTo[loc][dest]);
}
return dp[visited][loc];
}
// 비트마스크의 & 연산으로 아직 방문하지 않은 경우 == 같은 위치에 1이 존재하지 않는 경우 == 0 && 방문 하려는 곳의 간선이 존재
static boolean isValid(int visited, int loc, int dest) {
return (visited & (1 << dest)) == 0 && fromTo[loc][dest] > 0;
}
저는 55%에서 에러가 발생하여 참고한 블로그를 토대로 코드를 작성했었습니다.
중요한 포인트는 저는 시작할 때, 모두 INF값으로 설정하여, 간선이 없는 경우에도 INF 처리가 되어 에러가 발생했습니다.
참고했던 블로그 소스들에서는 시작을 모두 0으로 초기화하고, 간선이 존재하지 않으면 INF를 리턴합니다.
이렇게 되면, 자연스럽게 Math.min()의 우선순위에서 밀려서 선택이 되지 않고, 방문하지 않았고 간선이 존재하는 경우 INF로 초기화하고 loc위치에서 이동하려는 dest로 다시 tsp 재귀를 진행하면 간선이 존재하는 경우는 INF보다 작으므로 선택될 수 있는 환경이 되었습니다.
answer = tsp(1, 0); // 방문, 위치
처음 문제를 해결할 때, 왜 0번 인덱스로 순회를 시작하면 되는가에 대한 의문이 있었습니다.
순회라는 개념은 사이클이 된다는 것을 의미합니다.
만약, 최단 거리를 유지할 수 있는 순회 경로가
0 -> 1 -> 2 -> 3 -> 0이라면,
1-> 2 -> 3 -> 0 -> 1과 동일합니다.
즉 어디서 시작하던 0 -> 1을 가야 하고, 1 -> 2를 가야하고 , 2 -> 3, 3 -> 0을 가는 것은 동일합니다.
만약 최단 거리를 유지할 수 있는 순회 경로가
1 -> 2 -> 0 -> 3 -> 1 이더라도
0 -> 3 -> 1 -> 2 -> 0 은 순서만 다를 뿐 실제 사이클은 동일합니다.
따라서, 이 원리를 토대로 0번 인덱스에서 시작하면 최적의 값을 구할 수 있습니다.
외판원 문제와 같은 비트마스크 연산은 항상 헷갈리는데 나올 때마다 정리해 놓으면 도움이 되는 것 같습니다. 이상으로
import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = parseInt(br.readLine());
int[] map = new int[n];
for (int row = 0; row < n; row++) map[row] = parseInt(br.readLine());
int lis = getLISByBinarySearch(map); // 이진 탐색으로 LIS 길이 찾기
System.out.println(n - lis); // 총 길이에서 LIS 개수를 빼면 이동가능한 길이가 나옴
}
static int getLISByBinarySearch(int[] arr) { // 이진 탐색
List<Integer> dp = new ArrayList<>(); // dp 저장
for (int num : arr) {
if (dp.isEmpty() || num > dp.get(dp.size() - 1)) dp.add(num); // 처음이거나 마지막 숫자보다 크면 업데이트
else {
int left = 0, right = dp.size() - 1;
while (left < right) { // 이진 탐색
int mid = left + (right - left) / 2;
if (dp.get(mid) < num) left = mid + 1;
else right = mid;
}
dp.set(right, num); // 위치에 값 업데이트
}
}
return dp.size();
}
}
2. 풀이 중점 사항
이 문제는 정렬되지 않은 숫자가 있을 때, 각 위치를 이동하여 최소 숫자로 정렬하는 문제입니다.
순열 1, 5, 2, 9 가 주어져 있다고 예를 들겠습니다.
이 경우 2를 5 앞에 놓게 되면 1 2 5 9로 정렬을 할 수 있습니다.
1, 5, 2, 3, 7, 6이 주어졌다고 가정하겠습니다.
3의 뒤에 5을 이동시키고, 7을 6 뒤에 이동시키면 2번 안에 이동을 마칠 수 있습니다.
이는 최장 증가 부분 수열을 찾은 후, 최장 증가 부분 수열 내부로 각각 원소들을 이동시키면 되는 것입니다.
1 2 3 6 이 최장 증가 부분 수열이므로
5 7 을 위치시키면 문제를 해결할 수 있습니다.
즉 정답은 총 개수 - 최장증가 부분 수열 개수를 빼면 해결 할 수 있습니다.
3. LIS 이진탐색으로 해결하기
이진 탐색은 O(logN)으로 LIS를 구할 수 있습니다. 이러한 기능이 가능한 이유는 만약 주어진 숫자가 마지막 인덱스보다 크다면 바로 추가하고, 만약 아니라면 최대로 큰 값을 찾아서 계속 업데이트하되, 그 찾는 과정을 이진 탐색으로 수행하기 때문입니다.
이 과정에서 중요한 점이, 이진 탐색으로 수행할 때, 그 값을 add 하는 것이 아니라 set으로 업데이트하는 것입니다.
즉 최장 증가 부분 수열이 5개라면 6개로 만드는 것이 아니라 중간에 값만 바꾸는 것이기 때문에 최장 증가 부분수열의 크기는 변하지 않고, 탐색한 위치의 값만 수정되게 되는 것입니다.
static int getLISByBinarySearch(int[] arr) { // 이진 탐색
List<Integer> dp = new ArrayList<>(); // dp 저장
for (int num : arr) {
if (dp.isEmpty() || num > dp.get(dp.size() - 1)) dp.add(num); // 처음이거나 마지막 숫자보다 크면 업데이트
else {
int left = 0, right = dp.size() - 1;
while (left < right) { // 이진 탐색
int mid = left + (right - left) / 2;
if (dp.get(mid) < num) left = mid + 1;
else right = mid;
}
dp.set(right, num); // 위치에 값 업데이트
}
}
return dp.size();
}
먼저 DP를 리스트로 설정합니다.
2, 5, 3, 7 숫자가 주어졌다면 하나씩 배열에 담긴 숫자를 탐색합니다.
2는 dp가 비어있으므로 dp에 추가합니다.
5는 dp의 마지막 값인 2보다 크므로 dp에 추가합니다.
3은 5의 마지막 값보다 작으므로 이진 탐색을 수행합니다.
left = 0, right = 1이고 mid = 0 + 1 / 2 = 0 이므로, left = mid + 1입니다.
left < right의 조건을 위배하므로 right를 업데이트하는데 right가 1이므로 5의 값을 대체합니다.
7은 dp의 마지막 값인 3보다 크므로 7을 추가로 넣습니다.
즉, 이진 탐색을 수행하며, 최장 부분 수열을 만족하며 값을 바꿔 끼는 것을 확인할 수 있습니다.
이를 통해 최장 증가 부분 수열의 크기를 구할 수 있습니다.
4. 최장 증가 부분 수열 전체를 이진 탐색으로 구하기
최장 증가 부분 수열을 위의 코드로 구하고 출력하게 된다면, 개수는 동일하지만 올바른 값이 출력되지 않습니다.
왜냐하면 이진 탐색으로 중간에 값을 set 하기 때문에 마지막 값이 변경되지 않는다면 중간의 값을 바꾸는 것이기 때문입니다.
따라서, 온전한 최장 증가 부분 수열을 구하려면 하단의 코드를 작성해야 합니다.
static List<Integer> lisOfBinarySearchList(int[] nums) {
List<Integer> dp = new ArrayList<>();
int[] idxs = new int[nums.length]; // 인덱스 저장할 배열
int[] preIdxs = new int[nums.length]; // 이전 인덱스를 저장할 tmp 배열
for (int i = 0; i < nums.length; i++) {
if (dp.isEmpty() || nums[i] > dp.get(dp.size() - 1)) { // 리스트가 비어있거나 현재 리스트의 마지막 값보다 더 큰 경우
if (!dp.isEmpty()) preIdxs[i] = idxs[dp.size() - 1]; // dp의 마지막 값을 임시 배열에 저장
dp.add(nums[i]); // 값 추가하기
idxs[dp.size() - 1] = i; // 인덱스를 저장할 색인 배열에 인덱스 업데이트
} else { // 이진 검색 시작
int left = 0, right = dp.size() - 1; // 초기화 양 끝
while (left < right) {
int mid = left + (right - left) / 2; // 중앙을 설정할 mid
if (dp.get(mid) < nums[i]) { // 중간에 위치한 값보다 큰 경우 오른쪽 이진 검색
left = mid + 1; // left를 증가시켜서 위치를 옮김
} else {
right = mid; // right를 미드로 설정하여 왼쪽 이진 탐색
}
}
dp.set(right, nums[i]); // 중앙에 값을 대체함
idxs[right] = i; // 대체한 인덱스 설정
if (right > 0) preIdxs[i] = idxs[right - 1];
}
}
List<Integer> lis = new ArrayList<>();
int idx = idxs[dp.size() - 1];
while (lis.size() < dp.size()) {
lis.add(nums[idx]);
idx = preIdxs[idx];
}
Collections.reverse(lis);
return lis;
}
아래의 예시와 함께 설명하면 다음과 같습니다.
수열 2, 5, 3, 7이 주어져 있습니다.
arr은 배열 2, 5, 3, 7
dp는 이진 탐색으로 업데이트한 최장 증가수열을 저장할 dp
preIdxs는 Idx의 이전 인덱스 저장
Idxs는 최장 증가 부분 수열의 실제 값을 저장하기 위한 인덱스
먼저 인덱스 0을 순회하면, dp가 비어있으므로 2를 저장합니다.
preIdxs[0] = idxs[0] (0)
idxs[0] = 0
인덱스 1인 경우 arr[1] = 5가 2보다 크므로 5를 저장합니다.
preIdxs[1] = 0
idxs[1] = 1
이것이 의미하는 바는, 가장 큰 최장 증가 부분 수열의 길이는 2입니다.
idx[dp.size() - 1]이 의미하는 바는 이 가장 긴 수열의 실제 값 (arr의 위치)를 저장한 인덱스입니다.
즉 arr[1]을 찾을 수 있습니다.
preIdx의 인덱스 1에 저장된 0은 다음 최장 증가 부분 수열에서 큰 값의 인덱스를 가리키고 있습니다.
인덱스가 2로 이동한다면,
dp의 값은 업데이트가 되는데 5보다 3이 작지만 이진 탐색으로 right가 마지막 인덱스를 가리켜서 업데이트 됩니다.
이렇게 값이 더 커서 업데이트가 되는 경우가 아니라 이진 탐색으로 바뀌게 되는 경우는 idx를 먼저 업데이트합니다.
(개수가 증가하는 것이 아니라 내부의 값을 변경하므로)
따라서 idx가 가리키는 인덱스는 2로 수정됩니다. preIdxs[2] = 0을 가리킵니다.
마지막 인덱스 3에 도달하면 7을 DP에 넣습니다.
preIdxs[3] = 2 (dp 사이즈 - 1)
idxs[2] = 3 (인덱스는 실제 arr의 위치를 가리킴)
총 나온 결과로 시뮬레이션을 확인하면 다음과 같습니다.
List<Integer> lis = new ArrayList<>();
int idx = idxs[dp.size() - 1];
while (lis.size() < dp.size()) {
lis.add(nums[idx]);
idx = preIdxs[idx];
}
최종 최장 증가 부분 수열을 찾기 위한 list를 선언합니다.
dp.size() - 1의 값인 2를 인덱스로 하여 idxs 배열에서 찾습니다
값 3을 가지고 arr[3]의 값을 list에 추가합니다.
값 3으로 preIdxs[3] -> 다음 idx에서 찾을 인덱스 2를 가져와 idx로 업데이트 합니다.
import java.io.*;
public class Main {
static final int MOD = 1000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String encode = br.readLine();
if (encode.charAt(0) == '0') {
System.out.println("0");
return;
}
int len = encode.length();
long[] dp = new long[len + 1];
dp[0] = dp[1] = 1; // 하나로 초기화
// dp는 1번 인덱스, 문자열은 0번
for (int i = 2; i <= len; i++) {
char now = encode.charAt(i - 1); // 현재 문자 판단
char pre = encode.charAt(i - 2); // 이전 문자
if (now == '0') {
// 120 이 있는 경우, 20은 가능한 문자이므로 1이 있었던 위치의 dp 활용 (두개가 하나이므로)
if (pre == '1' || pre == '2') dp[i] = dp[i - 2];
else break;
}
else {
// 앞 문자가 0인 경우 무조건 주어진 숫자 하나만 선택 가능하므로 그대로 ex) 03 -> 3
if (pre == '0') dp[i] = dp[i - 1];
else {
int num = (pre - '0') * 10 + (now - '0'); // 숫자로 만들기
if (1 <= num && num <= 26) dp[i] = (dp[i - 2] + dp[i - 1]) % MOD;
else dp[i] = dp[i - 1]; // 28의 경우 알파벳 변환 불가하므로 한개 선택 => 그대로
}
}
}
System.out.println(dp[len] % MOD);
}
}
2. 풀이 중점 과정
해당 문제는, 문자열의 인덱스와 DP의 인덱스를 설정하는 과정이 중요하였습니다. 이 부분을 해결하지 못하여 코드를 참조하여 작성하였습니다.
풀이할 때, 예외 처리가 중요하였는데, 고려해야 할 사항은 다음과 같습니다.
시작이 0인 경우 불가
10, 20을 만들 수 있는 위치의 '0'이 아닌 경우 불가 ex) 30, 300
이전 문자와 현재 문자로 숫자를 만들었을 때, 26이 넘어가는 경우 각각 개별적인 선택만 가능 ex) 27
이전 숫자가 0인 경우는 현재 숫자는 2개를 만들 수 없고 선택해야 함 ( 위에서, 10, 20을 만들 수 있는 위치의 '0'이 아닌 경우에서 2개가 연속된 0인지 판단하는 로직이 있으므로 여기서는 선택)
만약 2개의 문자열을 만들 수 있다면 하나만 선택하기 위해 dp[i - 1] + 두 개를 문자로 묶어 하나로 만들기 위한 dp[i - 2]로 점화식을 만들 수 있습니다.
문자열은 0부터 시작하고, dp는 1부터 시작하여
문자의 길이가 2라면, 문자열 인덱스는 0, 1 까지 이고,
dp는 dp[2]가 문자 길이 2에 대한 값을 나타내도록 하였습니다.
자세한 풀이는 주석으로 처리하였습니다. 이상으로 암호코드 자바 풀이를 마치도록 하겠습니다. 감사합니다.
import java.util.*;
import java.io.*;
public class Main {
static final int MOD = 9901;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] dp = new int[n][3]; // [x][0]: 모두 선택 안함, [x][1]: 왼쪽만 넣음, [x][2]: 오른쪽만 넣음
Arrays.fill(dp[0], 1); // 0번째에서는 모두 선택 안하거나, 왼쪽에만 넣거나 오른쪽에만 넣을 수 있음
for (int i = 1; i < n; i++) {
// 모두 선택안하고 시작한 경우, 모두 선택 X, 왼쪽만 넣은 경우, 오른쪽만 넣은 경우 모두 넣고, 이번에 선택 안함
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // 이전에 모두 선택 안한 것, 오른쪽을 선택한 것을 선택하고 이번은 왼쪽을 선택
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; // 이전에 모두 선택 안한 것, 왼쪽만 선택한 경우를 가져온 후 오른쪽만 선택
}
int sum = 0;
for (int i = 0; i < 3; i++) sum += dp[n - 1][i];
sum %= MOD;
System.out.println(sum);
}
2. 풀이 중점 사항
해당 문제는 x by y 배열에서, i번째의 행에서 사자를 모두 놓지 않는지, 왼쪽만 놓는지, 오른쪽에만 놓는지를 구분하기 위해 이차원 배열의 dp로 0, 1, 2 세 가지를 나누는 과정이 중점이었습니다.
int[][] dp = new int[n][3]; // [x][0]: 모두 선택 안함, [x][1]: 왼쪽만 넣음, [x][2]: 오른쪽만 넣음
하나의 사례를 예시로 들면 다음과 같습니다. (O: 사자 선택, X: 사자 선택 하지 않음)
1) X X <-- 모두 선택 X
2) X X X X X X 첫 번째 행에서 모두 선택하지 않은 경우
O X X O X X 왼쪽의 모습처럼 왼쪽만 선택, 오른쪽만 선택, 모두 선택하지 않는 경우로 나눌 수 있습니다.
이를 코드로 구현하면, 모두 선택하지 않은 2차원 배열에서 0 인덱스는 모두 선택 X + 왼쪽만 선택 + 오른쪽만 선택 % MOD로 할 수 있습니다.
1) X O
2) X O X O 첫번째 행에서 오른쪽만 고른 경우는
O X X X 그 다음 행에서 왼쪽만 선택하거나, 모두 선택하지 않는 경우로 나눌 수 있습니다.
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // 이전에 모두 선택 안한 것, 오른쪽을 선택한 것을 선택하고 이번은 왼쪽을 선택
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; // 이전에 모두 선택 안한 것, 왼쪽만 선택한 경우를 가져온 후 오른쪽만 선택
이를 코드로 구현하면 다음과 같이 현재 주어진 인덱스 행에서 왼쪽만 선택 혹은 오른쪽만 선택하는 두 가지로 나눠서 dp를 계산할 수 있습니다.
시작이 대문자이거나 "_"인 경우, 마지막 문자열이 "_"로 끝나는 경우는 처음에 확인이 가능합니다.
// __ 불가 _A 불가 A_불가
boolean upperCase = false; // 만약 대문자가 있다면 c++로만 바꿀 수 있음
boolean toJava = false; // false라면 c++, true라면 자바로 바꾸기
char pre = str.charAt(0); // 이전 문자 파악
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch <= 'Z') {
if (toJava) { // _A로 끝나면 안되므로 _ 나왔는지 판단 (toJava라면 _이 나옴)
System.out.println("Error!");
return;
}
upperCase = true; // 대문자 true 설정
}
if (ch == '_') { // 만약 _가 있는데 대문자가 섞여 있다면 불가
if (upperCase || pre == '_') {
System.out.println("Error!");
return;
}
toJava = true;
}
pre = ch;
}
모든 문자가 전부 소문자와 대문자로만 이루어져 있다면, 이는 Java의 변수명 형태로 작성된 것입니다.
따라서, c++로 변경 가능합니다.
반면, 모든 문자가 소문자와 "_"로만 쓰인 경우는 Java로 변경이 가능합니다.
이와 같이 O(n)으로 탐색하며 어떠한 문자로 변경 가능한지 판단합니다.
if (toJava) { // 자바로 바꿔야 함
boolean nextUpper = false; // 다음이 대문자가 나와야함
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (nextUpper) {
sb.append(String.valueOf(ch).toUpperCase()); // 문자열 대문자로 변경
nextUpper = false; // 초기화
} else {
if (str.charAt(i) == '_') nextUpper = true; // 다음 문자열 대문자로 설정
else sb.append(ch);
}
}
}
else { // c++로 바꿔야 함
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch <= 'Z') { // 만약 대문자라면
sb.append("_"); // "_소문자"로 바꾸기
sb.append(String.valueOf(ch).toLowerCase());
} else sb.append(ch);
}
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Set<String> set = new HashSet<>(List.of("c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="));
int result = 0; // 결과 출력
String str = br.readLine();
String tmp = ""; // 문자열
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
tmp += c; // 문자열 추가 하기
if (tmp.length() == 3) { // 3개인 경우 dz 이후 문자
if (tmp.equals("dz=")) {
result++; // 하나의 문자
tmp = ""; // 문자를 모두 소모한 경우이므로
} else {
result += 2; // 앞의 두개가 불가한 문자이므로
tmp = String.valueOf(c); // 새로운 c 설정
}
}
if (tmp.length() == 2) {
if (tmp.equals("dz")) continue; // dz=일수 있으므로 넘기기
if (set.contains(tmp)) tmp = "";
else tmp = String.valueOf(c);
result++; // 만약 set에 있다면 하나로 쳐서 ++, 만약 아니라면, 이전 길이에 대한 ++,
}
}
if (tmp.length() >= 1) { // 한개 혹은 두개에서 끝난 경우
result += tmp.length(); // 문자열이 있다는 것은 크로아티아 알파벳 만족 불가
}
System.out.print(result);
}
}
2, 풀이 중점 사항
정의해야 할 문자를 미리 set에 컬렉션 생성자로 생성하여 tmp 문자가 같은지 판단하는 방법으로 문제를 해결할 수 있었습니다.
실수하기 좋은 위치가 마지막에 한 번 더 tmp.length() >= 1 인지 확인하는 로직입니다.
예를 들어 tmp가 "" 아닌 상태에서 종료될 수 있습니다. 특정 문자 하나가 남아있거나, dz의 특성으로 continue 하여 넘어간 것일 수 있습니다. 따라서, tmp의 길이가 1 이상이라면 남아있는 문자열 개수를 더해주는 것이 중요하였습니다.
import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = parseInt(br.readLine());
StringGame stringGame = new StringGame();
for (int i = 0; i < t; i++) {
stringGame.addStr(br.readLine());
stringGame.addTarget(parseInt(br.readLine()));
}
stringGame.find();
}
}
class StringGame {
List<String> strs = new ArrayList<>(); // 문자열을 담을 리스트
List<Integer> targets = new ArrayList<>(); // k를 담을 타겟 리스트
Map<Character, List<Integer>> map = new HashMap<>(); // 해시맵
void addStr(String str) {
strs.add(str);
}
void addTarget(int k) {
targets.add(k);
}
void init() {
for (char c = 'a'; c <= 'z'; c++) map.put(c, new ArrayList<>());
} // 미리 각 문자에 대한 어레이 리스트 생성하여 맵에 저장
void find() {
init();
StringBuilder sb = new StringBuilder();
// T: 100 W: 10000 idx: 10000 / 26 (k = 1) , 삭제 10000 / 26, 알파벳 26
// O(T * W + T * 10000 / 26 * 2 * 26) = O(300만)
for (int i = 0; i < strs.size(); i++) { // 문자열 순회
String str = strs.get(i);
int k = targets.get(i);
int min = Integer.MAX_VALUE; // 먼저 최소값 맥스로 설정
int max = -1; // max는 문자열 길이이므로 1 이상 나올 수 있으므로 -1로 최소화 설정
for (int j = 0; j < str.length(); j++) { // 각 문자에 대한 charAt으로 탐색
List<Integer> idxs = map.get(str.charAt(j));
idxs.add(j); // 인덱스 추가하기
}
Set<Character> set = map.keySet(); // 맵에서 키셋을 가져오기
for (Character ch : set) { // 키셋을 순회하며 ch 가져옴
List<Integer> idxs = map.get(ch); // 각 맵에 저장되어 있는 인덱스를 저장한 리스트 가져오기
if (idxs.size() >= k) { // k보다 같거나 크다면, k개 이상이 알파벳이 존재한다는 의미
for (int idx = 0; idx + (k - 1) < idxs.size(); idx++) { // 현재 인덱스부터 k - 1 큰 인덱스까지
min = Math.min(min, idxs.get(idx + k - 1) - idxs.get(idx) + 1); // 1 ~ 3까지의 길이는 3이므로 + 1
max = Math.max(max, idxs.get(idx + k - 1) - idxs.get(idx) + 1);
}
}
idxs.clear(); // 저장된 인덱스 모두 제거하기
}
if (min == Integer.MAX_VALUE && max == -1) sb.append(-1).append("\n");
else sb.append(min).append(" ").append(max).append("\n");
}
System.out.print(sb);
}
}
2. 풀이 중점사항
시간 복잡도 계산
해당 문제는 1초라는 시간이 주어졌고, 1024M라는 충분한 메모리가 제시되어 있습니다.
저는 각 문자열을 탐색하면서 map에 저장하고, map에 저장된 리스트의 길이가 k보다 같거나 크다면 내부의 인덱스를 순회하며 인덱스 간의 길이가 가장 길고 짧은 것을 판단하는 로직을 생각하였습니다.
가장 최악의 케이스를 고려해보면 다음과 같습니다.
T: 100 (케이스 개수)
W: 10000 (문자열 길이)
C: 26개의 알파벳이 모두 10000 / 26 개를 나눠가짐
K: 1 (k = 1이므로 idx에 저장된 값을 모두 탐색)
A: 알파벳 26개
따라서, 계산은 O(T * W + T * C * A) = O(100 * 10000 + 100 * 10000 / 26 * 26 * 2(add 후 clear)) = O(약 300만)
1초당 1억번이 가능하다고 가정하면 대략적으로 300만이면 충분히 가능한 시간이라고 판단하였습니다.
Map 사용
Map<Character, List<Integer>> map = new HashMap<>(); // 해시맵
--- 중략 ----
void init() {
for (char c = 'a'; c <= 'z'; c++) map.put(c, new ArrayList<>());
} // 미리 각 문자에 대한 어레이 리스트 생성하여 맵에 저장
---- 중략 ----
Set<Character> set = map.keySet();
HashMap에 먼저 알파벳과 arrayList<>를 저장하였습니다.
그리고 각 문자열을 순회하며 각 문자가 나온 인덱스를 map에 저장하였습니다.
map.keySet()으로 알파벳을 모두 가져왔습니다.
idx.size() >= k개 활용
for (Character ch : set) { // 키셋을 순회하며 ch 가져옴
List<Integer> idxs = map.get(ch); // 각 맵에 저장되어 있는 인덱스를 저장한 리스트 가져오기
if (idxs.size() >= k) { // k보다 같거나 크다면, k개 이상이 알파벳이 존재한다는 의미
for (int idx = 0; idx + (k - 1) < idxs.size(); idx++) { // 현재 인덱스부터 k - 1 큰 인덱스까지
min = Math.min(min, idxs.get(idx + k - 1) - idxs.get(idx) + 1); // 1 ~ 3까지의 길이는 3이므로 + 1
max = Math.max(max, idxs.get(idx + k - 1) - idxs.get(idx) + 1);
}
}
idxs.clear(); // 저장된 인덱스 모두 제거하기
}
idxs.size()로 k와 비교를 한 후, idx + (k - 1)가 idx.size()보다 작을 때까지 순회하며 값을 업데이트하였습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
List<String> strs = new ArrayList<>(); // 문자열 담을 리스트
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) strs.add(br.readLine()); // 문자열 리스트에 추가
for (String str : strs) {
int cnt = 0; // 회문, 유사회문, 그 외 판단
int left = 0; // 포인터 왼쪽
int right = str.length() - 1; // 포인터 오른쪽
while (left < right) { // left 포인터가 right 포인터보다 작을 때 까지 , 만약 홀수길이이의 문자열이라면 중앙을 제외한 나머지가 모두 맞으면 가능 abkba
if (str.charAt(left) != str.charAt(right)) { // 만약 양쪽 포인터가 가리키는 문자열이 같지 않다면
if (str.charAt(left + 1) == str.charAt(right)) { // 만약 두 포인터가 같지 않다면 유사회문 판단을 위해 left를 한칸 옮겨서 판단
cnt = move(str, left + 1, right);
if (cnt == 1) break; // 만약 왼쪽 포인터를 한번 더 옮긴 것이 유사회문이라면 종료
}
if (str.charAt(left) == str.charAt(right - 1)) { // 유사회문이 아닌 경우 right를 한칸 옮기고 진행
cnt = move(str, left, right - 1);
if (cnt == 1) break; // 유사회문 종료
}
cnt = 2; // 둘 다 아니거나, cnt = 2라면,
break;
} else { // 유사회문 없이 돌아간다면, 하나씩 포인터 양쪽에서 옮겨주기
left++;
right--;
}
}
if (cnt == 0) sb.append(0).append("\n");
else if (cnt == 1) sb.append(1).append("\n");
else sb.append(2).append("\n");
}
System.out.print(sb);
}
static int move(String str, int left, int right) { // 유사회문 판단을 위한 포인터 이동
while (left < right) {
if (str.charAt(left) == str.charAt(right)) {
left++;
right--;
} else return 2; // 유사회문도 아니므로 2 리턴
}
return 1; // 유사회문
}
}
2. 풀이 중점 사항
이번 풀이는 포인터를 이동하는 방식으로 문제를 해결할 수 있었습니다.
a b c b a
p1 -> <- p2
포인터를 하나씩 옮겨가며 값을 찾되, 두 포인터가 가리키는 값이 다를 수 있습니다. 이 경우 유사회문일 가능성이 있으므로, left를 옮기고 검사하고, 아니라면, 오른쪽을 한번 더 옮겨서 유사회문을 검사하는 로직을 작성하였습니다.
if (str.charAt(left + 1) == str.charAt(right)) { // 만약 두 포인터가 같지 않다면 유사회문 판단을 위해 left를 한칸 옮겨서 판단
cnt = move(str, left + 1, right);
if (cnt == 1) break; // 만약 왼쪽 포인터를 한번 더 옮긴 것이 유사회문이라면 종료
}
if (str.charAt(left) == str.charAt(right - 1)) { // 유사회문이 아닌 경우 right를 한칸 옮기고 진행
cnt = move(str, left, right - 1);
if (cnt == 1) break; // 유사회문 종료
}
cnt = 2; // 둘 다 아니거나, cnt = 2라면,
break;
다음과 같이, if - else if 가 아니라 왼쪽 유사회문 검사 후, 오른쪽 유사회문 검사하는 이유는 반례에서 찾을 수 있습니다.
만약 테스트 케이스가 'abbab'가 주어졌다고 가정하겠습니다.
// 잘못된 코드
if (str.charAt(left + 1) == str.charAt(right)) { // 만약 두 포인터가 같지 않다면 유사회문 판단을 위해 left를 한칸 옮겨서 판단
cnt = move(str, left + 1, right);
if (cnt == 1) break; // 만약 왼쪽 포인터를 한번 더 옮긴 것이 유사회문이라면 종료
}
else if (str.charAt(left) == str.charAt(right - 1)) { // 유사회문이 아닌 경우 right를 한칸 옮기고 진행
cnt = move(str, left, right - 1);
if (cnt == 1) break; // 유사회문 종료
}
cnt = 2; // 둘 다 아니거나, cnt = 2라면,
break;
만약 이처럼 if else if를 적용하게 된다면, 먼저 기술된 left + 1만 실행됩니다.
a b b a b
p1 p2 -------> arr[p1] != arr[p2]
p1 p2 -------> arr[p1] = arr[p2]
p1 p2 -------> arr[1] != arr[p2]
abbab 는 유사회문일지라도 left + 1를 하면 일반 문자열이 됩니다.
따라서, if문으로 left + 1을 먼저 거치고, 오른쪽도 right - 1로 검사할 수 있도록 하였습니다.
