[TIL]24-12-24

크리스마스 이브의 알고리즘 공부~

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

Blue Jeans 라는 문제이고 왜 이름이 블루진인지는 모르겠으나
lcs인척하는 lcs로 풀면 안되는 문제였다;;
그냥 무식하게 브루트포스법으로 공통되는 긴 문자열을 찾으면 되는거였다.

n = int(input())

def find_common_substring(strings):
    first_string = strings[0]
    max_common = ""
    
    # 첫 번째 문자열의 모든 부분 문자열 생성 (길이 3 이상)
    for length in range(3, len(first_string) + 1):  # 최소 길이 3부터 시작
        for start in range(len(first_string) - length + 1):
            substring = first_string[start:start + length]
            
            # 나머지 문자열에서 공통 여부 확인
            if all(substring in s for s in strings[1:]):
                # 최장 길이 또는 사전순으로 앞선 문자열 업데이트
                if len(substring) > len(max_common) or (len(substring) == len(max_common) and substring < max_common):
                    max_common = substring
    
    return max_common if max_common else "no significant commonalities"

for _ in range(n):
    m = int(input())
    strings = [input() for _ in range(m)]
    result = find_common_substring(strings)
    print(result)

그리고 파이썬 문법적으로 새로 알게된 것..!

문자열 비교에서 <, > 연산자는 사전순 정렬(lexicographical order)에 따라 동작한다고한다!

따라서 "abc" < "abd" 라는 조건문이 있으면 abc가 abd보다 사전순으로 앞이므로 더 작은 값으로 취급되어 맞는 조건식인거다.

import sys
input=sys.stdin.readline
# 데이터셋트개수
n=int(input())


def common(data):
    first =data[0]
    max=""
    for length in range(3,len(first)+1):
        # 부분 문자열 시작위치 정하기
        # (부분 문자열이 data의 범위를 벗어나지 않게)
        for start in range(len(first)-length+1):
            sub=first[start:start+length]
            # 나머지 문자열에 sub와 공통부분이 있는 지 비교
            if all(sub in d for d in data[1:]):
                #  길이가 긴 공통문자열을  max 에 저장
                if len(sub)>len(max) :
                    max=sub
                # 만약 길이가 같다면 사전순으로 앞에오는 문자열을 택함
                elif len(sub)==len(max) and sub<max:
                    max=sub
    # max값이 갱신되지 않았다는 뜻은 길이가 3미만인 경우이므로 멘트 출력
    return max if max else "no significant commonalities"



for _ in range(n):
    # 각 세트 안 염기서열 개수
    m=int(input())
    data=[input() for _ in range(m)]
    print(common(data))

다시 이해하면서 코드를 작성해보았다.
for 문에서 부분문자열이 data의 범위를 벗어나지 않게끔하는 아이디어를 구상하는것이 좀 어렵겠다는 생각이 들었다. 그리고 all 함수를 써서 나머지 문자열들과 비교한다는 아이디어도..