sen_log

난이도 골드3, 골드4 알고리즘: DP 두 문제의 기본 조건은 같다. 1부터 N까지의 번호를 가진 아이들이 무작위 순서를 가지고 일렬로 서있다. 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구해야 하는 것도 같다. 다만 아이를 옮기는 방식이 다르다. 7570번: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다. 2631번: 줄 서있는 어린이 중 한 명을 선택하여 다른 어린이와 자리를 바꾼다. 우선 2631번부터 보면, 아무 자리로 옮길 수 있으므로 이미 번호 순서대로 서있는 아이들을 제외한 나머지 아이들을 순서에 맞게 이동시키면 정답이다. 예를 들어 다음과 같은 N=6의 배열이 있다면 [3, 5, 6] 혹은 [1, 2, 4]가 이미 번호 순서대로 서있는 가장 긴 수열이다...

난이도 골드2 알고리즘: 투 포인터 문제 풀이를 위해 파악해야 할 중요한 점은 두 가지이다. 입력 문자열의 길이는 최대 3,000,000이다. ㅋㅋ루ㅋㅋ 문자열은 좌우대칭이다. 우선 입력이 크기 때문에 최대한 O(N)으로 연산을 해야한다. 즉 문자열의 각 원소에 대해 한번만 탐색하고 지나가는 풀이를 고안해야 한다는 것이다. 두번째로 ㅋㅋ루ㅋㅋ 문자열은 R을 중심으로 같은 개수의 K가 양 쪽에 붙은 좌우 대칭이다. 이 두 가지 특징을 통해 투 포인터를 떠올릴 수 있어야 한다. 투 포인터까지 떠올렸으면, 이제 각 포인터를 어떻게 움직여야 할 지 생각해야 한다. ㅋㅋ루ㅋㅋ 문자열은 K 사이에 R이 있는 문자열이다. (물론 K는 없을 수 있음) 따라서 투 포인터 바깥의 K와 안 쪽의 R로 ㅋㅋ루ㅋㅋ 문자열을 생..

난이도 골드2 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { private static Comparator comparator = new Comparator() { @Override public int compare(long[] x, long[]..