BOJ 3080 - 아름다운 이름 [Java / Python]

상근이가 뭐 하고 살든 알 바 아니지만 이런 이상한 짓은 좀 안 했으면 좋겠다. 사람이름은 타고나길 이쁜 거지 뭘 위치를 정해가며 아름답네 마네 한단 말인가... 여하튼 참여 중인 캠프에서 문제는 던져줬고, 나는 풀어야 하는 입장이었다.

 

문제만 보면 어떤 규칙인지는 알겠는데, 그냥 사전순 정렬하면 끝나는 거 아닌가 하는 생각이 든다. 필자는 예제 데이터를 보고나서야 문제가 요구하는 조건을 이해할 수 있었다. 예제를 먼저 살펴보자.

 

예제 1번은 비교적 쉽다. I로 시작하는 문자 하나와 J로 시작하는 문자가 2개 있으므로, J문자들을 정렬하는 2가지 경우에 앞뒤로 IVO를 붙여주는 걸 생각할 수 있다. 그렇게하면 2 * 2로 4가 나온다. 이 추측이 맞는지 아래 예제로 확인해 보자

 

 

 

문자의 한 열씩 비교하면서 진행한다. 현재까지는 모두 같은 문자다

 

 

3번째 열에서 처음으로 다른 글자가 나온다. MATO는 여기서 분리되고, 4열에서 MARA와 MARIKA가 분리된다. 5번째 열은 모두 다른 값을 가지고 있으므로 뒤의 과정은 생략한다. 최종적으로 묶은 단어 그룹은 아래와 같다.

 

 

먼저 MARTA와 MARTNA가 속한 MART그룹을 정렬하면 2!을 얻을 수 있다. 이어서 MAR그룹을 MARA, MARIKA, MART그룹 이렇게 3개로 구분해 정렬하면 3!, 마지막으로 MATO와 MAR그룹을 2개로 구분해 2!까지 곱하면 최종적으로 24라는 값을 얻을 수 있다.

 

예제 3의 경우도 동일하다. 각 그룹별로 나눠서 2! * 2! * 2! * 1! = 8이다.

 

 

 

앞 글자부터 비교하는 인덱스의 문자가 동일한지 체크하면서 그룹을 나눠준다. 다른 그룹이 나온다면 해당 그룹의 인덱스를 넘겨가며 재귀 호출 하는데, 혹시나 비교 인덱스보다 짧은 문자가 있다면 별도로 체크해서 그룹 수를 하나 늘려줬다. 짧은 문자열부터 순차적으로 처리할 수 있도록 시작 전에 사전순 정렬을 진행한다. 팩토리얼 연산이 필요해서 구현했고, 곱셈 또한 오버플로우가 나지 않도록 메서드로 분리해서 사용했다.

package solution.hanghae.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class test3080 {

    static int N;
    static String[] names;
    static int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        names = new String[N];

        for (int i = 0; i < N; i++) {
            names[i] = br.readLine();
        }

        Arrays.sort(names);

        System.out.println(countOfSort(0, N, 0));
    }

    private static long countOfSort(int s, int e, int lng) {
        long ret = 1;
        int group = 0;

        // 길이가 짧아 비교가 불가능한 그룹이 있는지 체크
        boolean checkShort = false;

        for (int i = s; i < e; i++) {
            // 탐색하는 문자의 길이가 조건보다 짧다면 체크하고 인덱스를 다음으로 넘겨준다.
            if (names[i].length() <= lng) {
                s++;
                checkShort = true;
                continue;
            }
            
            // 현재 탐색해야할 문자
            char lastAlp = names[s].charAt(lng);
            
            // 탐색하는 문자와 현재 문자열의 해당 위치 문자가 다른 경우
            if (names[i].charAt(lng) != lastAlp) {
                // 시작 인덱스부터 현재 진행 중인 인덱스 전까지 탐색하도록 넘겨주고 
                ret = multiple(ret, countOfSort(s, i, lng + 1));
                // 시작점을 현재로 당겨온다
                s = i;
                // 단어 그룹 증가
                group++;
            }

            // 순환이 끝날 때 마지막 그룹에 대한 로직 실행
            if (i + 1 == e) {
                ret = multiple(ret, countOfSort(s, e, lng + 1));
                group++;
            }
        }
        
        // 짧은 단어 그룹이 있다면 그룹 하나 증가
        if (checkShort){
            group++;
        }
        
        ret = multiple(ret, factorial(group));

        return ret;
    }

    private static long factorial(int n) {
        if (n == 1 || n == 0) {
            return 1L;
        }

        return n * factorial(n - 1) % MOD;
    }

    private static long multiple(long a, long b) {
        return a * b % MOD;
    }
}

 

 

이 문제는 예제 3의 예시처럼 주어진다면 재귀 깊이가 3000까지 깊어질 수 있는데, 파이썬은 기본적으로 재귀 깊이를 1000으로 제한하고 있다. 위 방식으로 파이썬 코드를 작성해 제출하면 Recursion Error가 발생한다. 강제로 제한을 풀고 진행하더라도 메모리 초과가 발생하므로, 좌표를 deque에 저장하며 반복문 사용 형태로 수정해 주었다.

'''
java 재귀 방식 : 메모리 = 44424kb, 응답 속도 = 544ms
python 반복문 사용 : 메모리 = 40800kb, 응답 속도 = 4380ms
pypy3 반복문 사용 : 메모리 200832kb, 응답 속도 = 940ms
'''

import sys
from collections import deque

n = int(sys.stdin.readline())
MOD = 1_000_000_007
names = [sys.stdin.readline().rstrip() for _ in range(n)]
facto = [0 for _ in range(3000)]

facto[0] = 1
facto[1] = 1

# 정렬된 상태에서 시작해야 같은 패턴을 가진 문자를 길이별로 잘라낼 수 있음
names.sort();

# q생성
queue = deque()
queue.append([0, n, 0])


def count_of_sort(q):
    ret = 1

    while q:
        # s : 시작 인덱스, e : 끝 인덱스, lng : 현재 탐색중인 문자열의 인덱스
        s, e, lng = q.popleft()
        group = 0
        # 길이가 짧아서 다음으로 넘어가지 못하는 그룹이 있는지 체크합니다
        check_short = False

        # 주어진 범위 탐색 시작
        for i in range(s, e):
            # 탐색 범위 안에 주어진 길이보다 짧은 단어가 있다면 체크 후 넘어갑니다
            # 다음 lng으로 넘어갈 때 포함되지 않도록 s를 뒤로 한칸 밀어줍니다
            if len(names[i]) <= lng:
                s += 1
                check_short = True
                continue

            # 탐색할 문자 지정
            last_alp = names[s][lng]

            # 문자가 달라지면, s부터 현재까지의 인덱스를 묶어 q에 넣어줍니다. lng위치의 문자 비교는 끝났기 때문에 1 증가시켜줍니다.
            # 시작지점을 현재 인덱스로 옮긴 후, 단어 묶음 변수를 하나 늘려줍니다
            if names[i][lng] != last_alp:
                q.append([s, i, lng + 1])
                s = i
                group += 1

            # 순회가 끝나고 남아있는 그룹이 있다면 q에 넣어 줍니다
            if (i + 1) == e:
                q.append([s, e, lng + 1])
                group += 1

        # 만약 길이가 짧아 문자열 비교를 하지 못한 그룹이 있다면 처리합니다
        if check_short:
            group += 1

        ret = multiple(ret, factorial(group))

    return ret


def factorial(number):
    if facto[number] == 0:
        facto[number] = number * factorial(number - 1) % MOD

    return facto[number]


def multiple(a, b):
    return a * b % MOD


print(count_of_sort(queue))

 

 

 

CS나 네트워크 관련 포스팅을 하고 싶은데, 캠프에서 제공되는 문제 난이도가 높다 보니 따로 시간을 내지 못하고 있다. 문제 풀이만 하려고 시작한 블로그가 아닌데... 조만간 다른 주제도 올릴 수 있도록 달려보겠다,,