PWC 367 중첩된 이상현상

I’m unable to access external websites, so I can’t retrieve the article from the link you provided. If you paste the text you’d like translated (excluding any code blocks or URLs you want to keep unchanged), I’ll be happy to translate it into Korean while preserving the original formatting.

Source: …

Task 1 – Maximum Odd Binary

아르테미스 2 달 탐사 주간이며, 우리는 홀수와 관련된 문제를 가지고 있습니다. 저는 이를 Space Oddity라고 부를 것입니다.

이진 문자열이 주어지며, 최소 하나의 1을 포함합니다. 비트를 재배열하여 결과 이진수가 최대 홀수 이진수가 되도록 하고, 그 결과 문자열을 반환하는 스크립트를 작성하십시오. 결과 문자열은 앞에 0이 포함될 수 있습니다.

Cogitation

• 가능한 한 크게 만들려면, 이진수는 1들을 가장 높은 비트(왼쪽) 쪽에 배치해야 합니다.
• 홀수가 되려면, 가장 낮은 비트(오른쪽) 가 1이어야 합니다.

따라서 모든 1을 왼쪽으로 옮기고, 오른쪽 끝에 하나의 1을 남겨두며, 그 사이를 0으로 채워야 합니다.

Three possible solutions

1. Sort

sub mobSort ($str) {
    my @bits = sort { $b cmp $a } split //, $str;   # descending → 1s left
    push @bits, shift @bits;                       # rotate leftmost 1 to the end
    return join "", @bits;
}

내림차순으로 정렬하여 1을 왼쪽에 배치합니다. 가장 왼쪽 비트를 꺼내어 오른쪽 끝에 넣어 회전시킵니다.

2. Split

sub mobSplit ($str) {
    my @bit = ("", "");                # index 0 → zeros, 1 → ones
    $bit[$_] .= $_ for split //, $str; # accumulate each character

    substr($bit[1], -1, 0, $bit[0]);   # insert the zeros just before the final 1
    return $bit[1];
}

0용 문자열과 1용 문자열 두 개를 유지합니다. 길이가 0인 substr을 사용해 마지막 1 바로 앞에 0들을 삽입합니다.

3. Count

sub mobCount ($str) {
    my $n    = length $str;
    my $zero = ($str =~ tr/0//);          # count zeros

    # (n‑zero‑1) ones on the left, then all zeros, then the final 1
    return ("1" x ($n - $zero - 1)) . ("0" x $zero) . "1";
}

tr///는 교체된 문자 수를 반환하므로 이를 이용해 0의 개수를 셉니다. 출력 길이는 입력 길이와 동일합니다.

Performance (simple benchmark)

               Rate   sorting   splitting   counting
sorting    128 205/s        --        -28%       -95%
splitting  178 571/s       39%         --       -93%
counting  2 500 000/s    1850%      1300%         --

정렬은 O(n log n) 복잡도를 가지므로 가장 느립니다. 카운팅 방식이 압도적으로 빠릅니다.

Source: …

작업 2 – 충돌 이벤트

두 개의 이벤트가 주어집니다. 각각은 시작 시간과 종료 시간으로 정의됩니다. 두 이벤트가 충돌하는지(즉, 교집합이 비어 있지 않은지) 판단하는 스크립트를 작성하세요.

충돌 정의

• 두 구간이 최소 1분 이상 겹칠 때 충돌이 발생합니다.
• 한 이벤트가 정확히 다른 이벤트가 시작하는 순간에 끝난다면 충돌이 없습니다(교집합이 비어 있음).

예시 사례

접근 방법

1. 변환: 각 HH:MM 문자열을 자정 이후 경과된 분 수로 바꿉니다.
2. 정규화: 자정을 넘는 구간은 모듈러 연산을 이용해 정규화합니다.
3. 검사: 두 구간이 겹치는지 확인합니다.

보조 함수 (Perl)

# Convert "HH:MM" → minutes since midnight
sub toMinute ($hhmm) {
    my ($h, $m) = split ":", $hhmm;
    return $m + 60 * $h;
}

# Turn a pair of minute values into a normalized range [beg, end)
# Handles intervals that span midnight.
sub toRange ($minBeg, $minEnd) {
    my $duration = ($minEnd - $minBeg) % 1440;   # length of the event
    return [ $minEnd - $duration, $minEnd ];    # may be negative → before midnight
}

# Determine whether two half‑open ranges overlap.
sub isOverlap ($range1, $range2) {
    use enum qw( BEG=0 END=1 );                  # for readability
    return $range1->[END] > $range2->[BEG] &&   # end of 1 after start of 2
           $range1->[BEG] < $range2->[END];     # start of 1 before end of 2
}

# Main API: given two arrayrefs ["HH:MM","HH:MM"], return true/false
sub isConflict ($event1, $event2) {
    return isOverlap(
        toRange( map { toMinute($_) } $event1->@* ),
        toRange( map { toMinute($_) } $event2->@* )
    );
}

• toMinute는 시와 분을 파싱합니다.
• toRange는 실제 시작(beg)과 종료(end) 값을 계산하며, 자정 넘어가는 경우를 올바르게 처리합니다.
• isOverlap는 반열린 구간 [beg, end)에 대한 전통적인 구간 겹침 조건을 검사합니다.
• isConflict는 모든 과정을 연결해 두 배열 참조(각 이벤트)를 받아 true/false를 반환합니다.

사용 예시

my $e1 = [ "23:30", "00:30" ];
my $e2 = [ "00:00", "01:00" ];

say isConflict($e1, $e2) ? "true" : "false";   # prints "true"

이 스크립트는 자정을 넘는 경우를 포함해 충돌을 정확히 판별합니다.