PWC 350 좋은 부분 문자열 / 셔플 쌍

Source: Dev.to

작업 1: 좋은 부분 문자열

과제

문자열이 주어집니다. 문자열에서 길이가 3인 좋은 부분 문자열의 개수를 반환하는 스크립트를 작성하세요. 부분 문자열에 같은 문자가 두 번 이상 나타나면 좋지 않은 것으로 간주합니다.

예시

생각하는 부분

정규 표현식으로도 해결할 수 있지만, 가장 간단한 방법은 문자열을 세 글자씩 슬라이딩 윈도우로 이동하면서 세 글자가 모두 서로 다른지 확인하는 것입니다.

코딩하는 부분

sub goodSubstring($str) {
    my $good = 0;
    my @s = split //, $str;
    for (0 .. $#s - 2) {
        my ($first, $second, $third) = @s[$_, $_+1, $_+2];
        $good++ if $first ne $second && $first ne $third && $second ne $third;
    }
    return $good;
}

주의 사항

• 문자열을 문자 리스트로 나누어 인덱싱을 쉽게 합니다.
• 배열 슬라이스 @s[$_, $_+1, $_+2]는 연속된 세 문자를 추출합니다.
• 세 글자만 다루므로 쌍별 불일치 검사가 간단합니다.

작업 2: 셔플 페어

과제

두 정수 A ≤ B가 서로 다른 순서로 같은 숫자를 포함하고 있을 때, A = B * k 를 만족하는 정수 k 가 존재하면 이를 셔플 페어라고 합니다. 여기서 정수 k 가 그 페어의 증인이 됩니다.

함수에 $from, $to, $count 를 전달했을 때, $from ≤ i ≤ $to 범위 내에서 적어도 $count 개의 서로 다른 셔플 페어에 속하는 정수 i 의 개수를 반환하도록 하세요.

예시

1. 입력: $from = 1, $to = 1000, $count = 1
   출력: 0 – 1000 이하에서는 셔플 페어가 없습니다.

2. 입력: $from = 1500, $to = 2500, $count = 1
   출력: 3 – 해당 숫자는 1782 (→ 7128, k=4), 2178 (→ 8712, k=4), 2475 (→ 7425, k=3) 입니다.

3. 입력: $from = 1_000_000, $to = 1_500_000, $count = 5
   출력: 2 – 1428570 과 1429857 은 각각 다섯 개의 셔플 파트너를 가집니다.

4. 입력: $from = 13_427_000, $to = 14_100_000, $count = 2
   출력: 11 – 여섯 개 숫자는 세 개의 파트너를, 다섯 개 숫자는 두 개의 파트너를 가집니다.

5. 입력: $from = 1030, $to = 1130, $count = 1
   출력: 2 – 1035 (→ 3105, k=3) 와 1089 (→ 9801, k=9) 입니다.

고찰

이 문제는 몇 가지 최적화를 적용한 완전 탐색이 가장 효과적입니다:

1. 정규 형태: 숫자의 자릿수를 정렬합니다; 두 숫자는 정규 형태가 같을 때만 서로의 순열입니다.
2. 탐색 범위: 주어진 n에 대해, 같은 자릿수를 유지하려면 배수 2..9만 고려하면 됩니다. 그보다 큰 배수는 자릿수가 늘어나 셔플 페어가 될 수 없습니다.
3. 조기 종료:
   • 같은 자릿수에서 가능한 최대값(999…)을 계산합니다.
   • 배수의 첫 번째 혹은 마지막 자릿수가 원래 숫자에 존재하지 않으면 바로 제외합니다.

도우미: 정규 형태

sub canonical($n) {
    join "", sort split //, $n;
}

주요 해결책

sub shufflePair($from, $to, $count) {
    my $answer = 0;

    for my $n ($from .. $to) {
        my $base = canonical($n);
        my $max  = (9 x length($n)) + 0;   # 예: 3자리 수이면 999
        my $pair = 0;

        for my $k (2 .. 9) {
            my $multiple = $n * $k;
            next if $multiple > $max
                 || index($base, substr($multiple, 0, 1)) = $count;
        }
    }
    return $answer;
}

주의 사항

• 각 n에 대해 canonical($n)을 $base에 캐시합니다.
• $max는 같은 자릿수를 유지할 수 있는 최대값을 제한합니다.
• 첫/마지막 자릿수에 대한 간단한 검사(index 사용)는 불필요한 정렬을 피하게 해 줍니다.
• 최종적으로 숫자가 $count 개 이상의 셔플 파트너를 가질 때 카운트를 증가시킵니다.