백준 24524번: 아름다운 문자열 (Python/Java)

https://www.acmicpc.net/problem/24524

24524번: 아름다운 문자열

 

 

 

접근

---

만들 수 있는 단어를 찾기 위해 몇 번씩이나 주어진 문자열을 반복 탐색하는 것은 비효율적이고 연산이 늘어난다. 이런 연산을 줄이기 위해 최대한 주어진 문자열 탐색을 줄이도록 하겠다. 이번 풀이에서는 문자열을 딱 한번 탐색할 것이다. 그만큼 아이디어만 생각해낸다면 간단한 문제라는 뜻이다.

 

우선 문제 조건을 다시 한번 살펴보자. 'T 역시 모든 문자가 서로 다르다.'라고 주어졌다. 이 말은 무엇이냐면 T를 이루고 있는 각각의 알파벳을 통해 해당 알파벳이 단어의 몇 번째 위치인지 파악 가능하다는 뜻이다. 만일 T가 'abcd'라면 c는 무조건 단어의 세 번째 알파벳이다. 왜냐? 모든 문자는 서로 다르기 때문에 c는 다른 어떤 위치에서도 나올 수 없기 때문이다.

 

그럼 이 조건을 조금 응용해보도록 하자. 우리는 S에서 T를 찾아야 한다. 만일 S에서 a가 나왔다면 이건 T의 첫 번째 글자를 찾았다는 뜻이다. b라면 두 번째, c라면 세 번째, d라면 네 번째 글자다. 이제 S를 탐색하자. S를 탐색하다 a를 찾았다면 체크하고 넘어가 주자. 첫 번째는 따로 조건 넣을 필요가 없기 때문이다. b를 찾았다면 a를 찾은 적이 있는지 확인한다. a를 찾은 적이 있다면 해당 b는 a보다 뒤에 나온 것이기 때문에 앞 글자와 짝을 이룰 수 있다는 뜻이다. 체크해주자. c를 찾았다면 b를 찾은 적 있는지 확인해주고,... 이를 마지막 글자까지 반복한다.

 

나 같은 경우는 이를 수로 체크해뒀다. T의 길이와 같은 길이의 배열을 만들어두고 0으로 채워뒀다. 만일 위와 같은 경우라면 [0, 0, 0, 0]이 되고, 각각 a, b, c, d를 만난 횟수가 된다. a를 찾았다면 [1, 0, 0, 0]이 된다. 그 후, b를 만났다면 a를 만난 적이 있는지 본다. a에 해당하는 인자가 1이라는 말은 a를 한번 찾은 적이 있다는 말이다. 이 a는 b와 짝지을 수 있다. b를 1 올려준다. 이제 앞서 찾은 a는 지금 찾은 b와 짝지어지기 때문에 다른 b와는 짝지을 수 없다. 다시 1 줄여준다. 이제 배열은 [0, 1, 0, 0]이 된다. 이를 계속 반복해준다. 만일 모든 글자와 짝을 맞춰 T를 완성했다면 마지막 d에 해당하는 배열 인자 값에 1을 더해주게 된다. 그렇다. 배열의 마지막 값이 완성할 수 있는 T의 수가 된다.

 

예제 3을 통해 적용해보자 S는 abba고, T는 ab다. 배열 [0, 0]을 만들어준다. 배열의 첫 번째 인자는 T의 첫 번째 알파벳 a를 뜻하고 두 번째 인자는 T의 두 번째 알파벳 b를 뜻한다. S를 탐색해보자. a를 만났다. 배열의 a자리, 즉 첫 번째 인자에 1을 더해준다.([1, 0]) 다음으로 b를 만났다. b는 T의 두 번째 알파벳이다. 그럼 앞의 글자 a를 만난 적 있는지 확인한다. 배열의 첫 번째 자리는 1이기 때문에 앞서 a를 한번 만난 적이 있다는 것을 확인할 수 있다. 이제 이 a는 b와 짝지어지기 때문에 앞으로 사용할 수 없다. a자리에 1을 빼주고 b자리에 1을 더해준다.([0, 1])

 

다음 b는 짝지어줄 수 있는 앞글자 a가 없다. 배열 첫 번째 인자가 0이기 때문이다. 넘어가 준다. S의 마지막 글자로 a가 나왔다. a는 비교할 앞글자가 없으니 그냥 배열의 첫 번째 인자에 더해준다.([1, 1]) 이제 배열을 확인해본다. 배열의 마지막 자리가 1이다. 즉, S를 통해 구할 수 있는 T 조합은 하나라는 뜻이 된다.

 

 

 

풀이

---

Python

fullWord = list(input())
goalWord = list(input())

idxList = [0 for i in range(26)]
for i in range(len(goalWord)):
    idxList[ord(goalWord[i])-97] = (i+1)

board = [0 for i in range(len(goalWord)+1)]
for i in range(len(fullWord)):
    if idxList[(ord(fullWord[i])-97)] != 0:
        if idxList[(ord(fullWord[i])-97)] == 1:
            board[idxList[(ord(fullWord[i])-97)]] += 1

        else:
            if board[idxList[(ord(fullWord[i])-97)]-1] > 0:
                board[idxList[(ord(fullWord[i])-97)]-1] -= 1
                board[idxList[(ord(fullWord[i])-97)]] += 1

print(board[len(goalWord)])

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args){
        
        Scanner scan = new Scanner(System.in);

        String[] fullWord = (scan.nextLine()).split("");
        String[] goalWord = (scan.nextLine()).split("");

        int[] idxList = new int[26];
        for(int i = 0 ; i < goalWord.length ; i++){
            idxList[goalWord[i].charAt(0)-97] = (i+1);
        }

        int[] board = new int[goalWord.length+1];
        for(int i = 0 ; i < fullWord.length ; i++){
            if(idxList[fullWord[i].charAt(0)-97] != 0){
                if(idxList[fullWord[i].charAt(0)-97] == 1){
                    board[idxList[fullWord[i].charAt(0)-97]]++;
                    
                }else{
                    if(board[idxList[fullWord[i].charAt(0)-97]-1] > 0){
                        board[idxList[fullWord[i].charAt(0)-97]-1]--;
                        board[idxList[fullWord[i].charAt(0)-97]]++;
                    }
                }
            }
        }

        System.out.println(board[goalWord.length]);

    }

}