문제 링크
문제
티어: 골드 3
알고리즘: dp
동혁이의 키보드에는 버튼 세 개와 LCD창 한 개가 달려 있다. LCD창에는 문자열 S가 쓰여 있다. 그리고 커서는 문자열의 가장 왼쪽 글자에 위치해 있다. 버튼 세 개는 왼쪽, 오른쪽, 엔터키이다.
왼쪽 키는 만약 현재 커서에서 왼쪽으로 더 갈 수 있으면, 왼쪽으로 커서를 한 칸 이동시키는 역할을 하고, 오른쪽 키도 현재 커서에서 오른쪽으로 갈 수 있으면 오른쪽으로 커서를 한 칸 이동시키는 역할을 한다. LCD창의 크기는 정확하게 문자열 S의 크기와 같다. 그리고 커서는 절대로 LCD창을 벗어나지 않는다. 엔터키는 문자열을 컴퓨터에 전송해서 컴퓨터 화면에 출력하는 역할을 한다. 문자열이 화면에 출력되면, 그 문자는 빈 칸으로 변한다.
동혁이는 LCD창에 쓰여 있는 문자열을 컴퓨터 화면에 알파벳 순서대로 쓰려고 한다. 동혁이는 완벽주의자이기 때문에, 문자열 S에 있는 모든 문자를 하나도 빠짐없이 출력하려고 한다. 만약 a가 LCD창에 3개가 있으면 컴퓨터 화면에는 a가 3번 나와야 한다.
LCD창에 쓰여 있는 문자열이 주어질 때, 그 문자열을 알파벳 순서대로 출력할 때, 키의 입력을 최소화하는 프로그램을 작성하시오.
입력
첫째 줄에 LCD창에 쓰여 있는 문자열 S가 주어진다. 문자열 S는 길이는 50보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다.
출력
동혁이의 신기한 키보드로 문자열 S에 쓰여 있는 문자를 알파벳 순서대로 출력하고자 할 때, 키를 누르는 횟수의 최솟값을 출력하시오.
풀이
키를 누르는 횟수의 최솟값을 출력해야 한다.
커서는 가장 왼쪽에 있고, 커서의 이동 거리만을 따질 것이다. 왜냐하면 엔터는 어차피 S.length()로 고정이기 때문이다.
만약 다음과 같은 문자열이 있다고 해보자
aacbabc 이 문자열을 aaabbcc로 출력해야 한다.
a를 전부 출력하기 위한 최소 이동 거리는 가장 오른쪽에 있는 a까지 커서를 옮겼을 때 거리다.
그리고 출력된 상태는 aaa이다. 현재 커서는 4다.
다음 출력해야 될 알파벳은 b다.
현재 커서에서 왼쪽과 오른쪽의 b가 있는데 이동 경로는 두 가지 경우의 수로 나눠진다.
- 현재 커서 -> 왼쪽 b -> 오른쪽 b
- 현재 커서 -> 오른쪽 b -> 왼쪽 b
즉, b를 다 출력하고 나서 위치할 수 있는 커서가 두 곳이라는 의미다.
출력된 상태는 aaabb다.
다음 출력해야 될 알파벳은 c다.
b의 마지막 커서 둘 다 왼, 오에 c가 위치하기 때문에
경우의 수는 총 4가지 존재한다.
이렇게 마지막 커서에서 다음 출력해야 될 문자가 양쪽에 존재한다면 2의 지수승으로 증가하는 것을 볼 수 있다.
계산해 보면 모든 경우의 수를 구해도 가능하다. 최악의 경우의 수가 약 2^25정도 이기 때문이다.
그런데 잘 생각해 보면 각 문자 별 마지막 커서의 위치는 최대 2곳이기 때문에 모든 경우의 수를 구할 필요 없다.
현재 가리키고 있는 커서가 같다면 그 이후부터는 똑같기 때문에 현재까지의 이동 거리를 비교해서 더 작은 값을 넣어주면 된다.
그래서 dp[A][2] -> A는 문자의 종류를 나타냄, 그리고 [A][0]은 왼쪽, [A][1]은 오른쪽으로 정의할 수 있다.
dp 풀이의 시간 복잡도는 O(S)다.
소스 코드
import java.io.*;
import java.util.*;
class Info {
int ind, v;
Info(int ind, int v) {
this.ind = ind;
this.v = v;
}
}
public class Main {
static final int MAX = 100000000;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S = br.readLine();
boolean[] visited = new boolean[26];
ArrayList<Character> list = new ArrayList<>();
for(int i=0; i<S.length(); i++) {
int ind = (int) S.charAt(i) - 97;
if(!visited[ind]) {
visited[ind] = true;
list.add(S.charAt(i));
}
}
Collections.sort(list);
int[][] cLocation = new int[list.size() + 1][2]; //0은 왼쪽, 1은 오른쪽 인덱스
for(int i=0; i<list.size(); i++) {
int cursor = -1;
for(int j=0; j<S.length(); j++) {
if(S.charAt(j) == list.get(i)) {
if(cursor == -1) {
cLocation[i + 1][0] = j;
}
cursor = j;
}
}
cLocation[i + 1][1] = cursor;
}
Info[][] dp = new Info[list.size() + 1][2]; //0은 왼쪽 먼저 이동, 1은 오른쪽 먼저 이동
for(int i=1; i<=list.size(); i++) {
for(int j=0; j<2; j++) {
dp[i][j] = new Info(-1, MAX);
}
}
dp[1][1] = new Info(cLocation[1][1], cLocation[1][1]);
for(int i=2; i<=list.size(); i++) {
for(int j=0; j<2; j++) {
if(dp[i - 1][j].ind != -1) {
//경우의 수가 존재함
if(cLocation[i][0] < dp[i - 1][j].ind && dp[i - 1][j].ind < cLocation[i][1]) {
//현재 커서에서 이동할 수 있는 방향이 왼, 오라면
int fLeft = (dp[i - 1][j].ind - cLocation[i][0]) + (cLocation[i][1] - cLocation[i][0]);
int fRight = (cLocation[i][1] - dp[i - 1][j].ind) + (cLocation[i][1] - cLocation[i][0]);
if(dp[i][1].v > fLeft + dp[i - 1][j].v) {
dp[i][1] = new Info(cLocation[i][1], fLeft + dp[i - 1][j].v);
}
if(dp[i][0].v > fRight + dp[i - 1][j].v) {
dp[i][0] = new Info(cLocation[i][0], fRight + dp[i - 1][j].v);
}
} else if(cLocation[i][0] < dp[i - 1][j].ind) {
//왼쪽만
int v = dp[i - 1][j].ind - cLocation[i][0] + dp[i - 1][j].v;
if(dp[i][0].v > v) {
dp[i][0] = new Info(cLocation[i][0], v);
}
} else {
//오른쪽만
int v = cLocation[i][1] - dp[i - 1][j].ind + dp[i - 1][j].v;
if(dp[i][1].v > v) {
dp[i][1] = new Info(cLocation[i][1], v);
}
}
}
}
}
System.out.println(Math.min(dp[list.size()][0].v + S.length(), dp[list.size()][1].v + S.length()));
}
}