BOJ) 문자열

문자열

1120번: 문자열

풀이

 

문자열 두개가 주어질 때, 오른쪽 문자열의 길이는 항상 왼쪽보다 크다.

왼쪽 문자열의 맨 앞이나 맨 뒤에 a~z 문자 하나를 적절하게 배치했을 때, 왼쪽과 오른쪽의 문자열의 인덱스가 다른 수의 최소값을 찾는 문제다.

문제의 조건에 최대 길이가 50이라고 주어졌지만, 이를 먼저 확인하지 않고 brute force라 dfs로 그냥 모든 경우의 수를 조합했다.

 

하지만, 메모리 초과가 떠서 위의 조건을 추가적으로 확인했다.

어차피 좌측과 우측의 문자열의 길이가 다를 때, 앞과 뒤에 새로운 문자을 추가하는 것이면 새롭게 추가하는 문자는 똑같은 문자를 추가하면 된다고 생각했다. 그래서, 문자열의 차이만큼 시작점을 다르게해서 가장 많이 같은 문자를 가진 위치를 찾았다.

 

문제에서 주어진 예시로 보면,

문제 예시

둘 중 오른쪽의 경우가 차이가 더 적은 것을 알 수 있다.

그렇다면, 오른쪽의 경우에서 맨 앞에 a라는 문자 하나만 붙여주면 되기때문에, 차이는 2로 그대로 남는다.

따라서, 위와 같이 오른쪽 문자열의 인덱스의 시작점을 0 ~ left와 right의 길이 차이 부터 시작해서 각 경우에 차이가 가장 적은 숫자가 문제의 정답이 된다.

 

코드 결과

 

 

 

 

코드 1 (메모리 초과)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private final static char START = 'a', END = 'z';
    private static int answer, len;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();
        solution(st.nextToken(), st.nextToken());
    }

    private static void solution(String left, String right) {
        len = right.length();
        answer = len;
        LinkedList<Character> list = new LinkedList<>();
        for(int i=0; i<left.length(); i++) { list.offer(left.charAt(i)); }
        setAnswer(len- left.length(), right.toCharArray(), list);
        System.out.println(answer);
    }

    private static void setAnswer(int n, char[] right, LinkedList<Character> list) {
        if(n ==0) {
            int cnt=0;
            for(int i=0; i<len; i++) {
                if(right[i] != list.get(i)) { cnt++; }
            }
            answer = Math.min(cnt, answer);

            return;
        }
        for(char ch = START; ch<=END; ch++) {
            list.offer(ch);
            setAnswer(n-1, right, list);
            list.pollLast();
            list.addFirst(ch);
            setAnswer(n-1, right, list);
            list.pollFirst();
        }
    }
}

 

코드 2 (성공)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();
        solution(st.nextToken().toCharArray(), st.nextToken().toCharArray());
    }

    private static void solution(char[] left, char[] right) {
        int answer = right.length;
        int leftLen = left.length;
        int diff = answer-leftLen;
        for(int i=0; i<=diff; i++) {
            int cnt =0;
            for(int j=0; j<leftLen; j++) {
                if(left[j] != right[j+i]) { cnt++; }
            }
            answer = Math.min(cnt,answer);
        }
        System.out.println(answer);
    }
}