프로그래머스 - [1차] 뉴스 클러스터링

들어가기 전에

문제를 해결하기 위해 어떤 생각을 했는지 기록하기 위해 쓰는 글입니다.

O(10^8)의 계산을 1초라 가정했습니다.

잘못되거나 개선이 필요한 부분 지적은 언제나 환영입니다!

 

지문 해석

두 문자열 str1, str2을 upper나 lower를 통해 대문자나 소문자로 변환해야 한다

변환된 문자를 슬라이딩 윈도우를 통해 특수문자가 있는지 확인하고, 없다면 배열에 추가한다.

각각 시간 복잡도가 O(n)이 나온다.

 

그 후, 슬라이딩 윈도우의 결과를 가지고 교집합과 합집합을 구한다.

여기서 주의할 점은 교집합을 구하는 과정에서 교집합이 된 쌍은 다음 교집합 확인에서 제외해야 한다.

예를 들자면 A = {1, 1, 2, 2, 3}, B = {1, 2, 2, 4, 5} 의 교집합에서

A[0] = 1과 B[0] = 1 이 서로 교집합 매칭이 됐다면, B[0]은 다음 A[1] = 1과 교집합 매칭을 하면 안 된다.

(나는 특수문자를 주는 식으로 매칭에서 제외시켰다.)

이렇게 검증을 하면 O(N ^ 2)의 시간 복잡도가 나오지만, N = 1000이기에 TLE의 요소는 없다.

 

그 후 계산은 무척 간단하니 설명은 하지 않는다.

 

코드

def solution(str1, str2):
    str1, str2 = str1.upper(), str2.upper()
    str1J, str2J = [], []
    for i in range(0, len(str1) - 1):
        a, b = str1[i], str1[i + 1]
        if a < 'A' or a > 'Z' or b < 'A' or b > 'Z':
            continue
        str1J.append(str1[i:i + 2])
    for i in range(0, len(str2) - 1):
        a, b = str2[i], str2[i + 1]
        if a < 'A' or a > 'Z' or b < 'A' or b > 'Z':
            continue
        str2J.append(str2[i:i + 2])
    a, b = 0, 0
    for i in range(len(str1J)):
        s = str1J[i]
        for j in range(len(str2J)):
            if s == str2J[j]:
                str1J[i] = '-'
                str2J[j] = '-'
                break
    for s in str1J:
        if s == '-':
            b += 1
        a += 1
    for s in str2J:
        if s != '-':
            a += 1


    if a == 0 and b == 0:
        answer = 1
    else:
        answer = b / a
    answer = (int)(answer * 65536)
    return answer

 

다른 사람의 풀이

이 글을 쓴 목적이기도 하다.

모범 답안과 비교하니, 파이썬의 이점을 활용하지 못하고 너무 정직하게 문제를 풀었다.

정규표현식 부분은 다루지 않는다.

 

1. set 끼리 비트 연산 가능

평소 자바 코딩을 하다보니 될 거라곤 전혀 생각도 못하고 있었던 부분이다.

&를 하면 교집합 연산이 되고

|를 하면 합집합 연산이 됐다.

 

나는 이 부분을 이중 포문을 통해 일치하는 문자열은 '-'를 넣어서 뺐다.

 

2. extend 내장 함수

리스트에 다른 리스트를 합칠 때 append를 사용했고, 단순히 append를 하면 리스트가 통째로 원소 하나가 돼서

for문을 돌려서 넣어왔다.

하지만, extend를 쓴다면 '' 같은 의미없는 값을 제외한 모든 원소를 추가해준다.

참 미개하게 문제를 풀어왔다.

 

바꾼 코드

def solution(str1, str2):
    str1, str2 = str1.upper(), str2.upper()
    str1J, str2J = [], []
    for i in range(0, len(str1) - 1):
        a, b = str1[i], str1[i + 1]
        if a < 'A' or a > 'Z' or b < 'A' or b > 'Z':
            continue
        str1J.append(str1[i:i + 2])
    for i in range(0, len(str2) - 1):
        a, b = str2[i], str2[i + 1]
        if a < 'A' or a > 'Z' or b < 'A' or b > 'Z':
            continue
        str2J.append(str2[i:i + 2])
    
    answer = 65536
    total = set(str1J) | set(str2J)
    h, g = [], []
    if total:
        for t in total:
            h.extend(t * max(str1J.count(t), str2J.count(t)))
            g.extend(t * min(str1J.count(t), str2J.count(t)))
        answer = int(len(g) / len(h) * 65536)
    print(g)
    return answer