[레벨1][파이썬] 숫자 짝궁

 

https://school.programmers.co.kr/learn/courses/30/lessons/131128#qna

프로그래머스

 

1. 1차 시도(문자열 슬라이싱) → 시간 초과

문자열 슬라이싱을 이용하여 풀이하였으나 시간 초과가 발생하였습니다.

def solution(X, Y):
    result_str = ""
    for i in X:
        target = Y.find(i)
        if target > -1:
            result_str += Y[target]
            Y = Y[:target] + Y[target + 1 :]

    if len(result_str) == 0:
        return "-1"

    answer = str(int("".join(sorted(result_str, reverse=True))))

    return answer

 

2. 2차 시도(문자열을 리스트로 변환) → 시간 초과

문자열을 리스트로 변환하여 풀이하였으나 시간 초과가 발생하였습니다.

def solution(X, Y):
    result_list = []

    if len(X) > len(Y):
        small_list = list(Y)
        big_str = X
    else:
        small_list = list(X)
        big_str = Y

    for i in big_str:
        if i in small_list:
            result_list.append(i)
            small_list.remove(i)

    if len(result_list) == 0:
        return "-1"

    if result_list[0] == "0":
        return "0"

    return "".join(sorted(result_list, reverse=True))

 

3. 3차 시도(딕셔너리 이용) → 성공

딕셔너리를 이용한 3차 시도에서 시간 초과 문제가 해결할 수 있었습니다.

def solution(X, Y):
    X_dict = {}
    for i, v in enumerate(X):
        try:
            X_dict[v] += 1
        except:
            X_dict[v] = 1
    Y_dict = {}
    for i, v in enumerate(Y):
        try:
            Y_dict[v] += 1
        except:
            Y_dict[v] = 1

    answer = ""
    for key in X_dict:
        try:
            Y_dict[key]
        except:
            continue
        else:
            if X_dict[key] > Y_dict[key]:
                answer += key * Y_dict[key]
            else:
                answer += key * X_dict[key]

    if len(answer) == 0:
        return "-1"

    answer = "".join(sorted(list(answer), reverse=True))

    if answer[0] == "0":
        return "0"

    return answer

 

4. 리팩토링(딕셔너리와 셋 이용) → 성공

딕셔너리와 셋을 이용해 시간 복잡도를 개선하였습니다.

def solution(X, Y):
    X_dict = {key: X.count(key) for key in set(X)}  # X의 각 요소의 개수를 카운트한 딕셔너리 생성
    Y_dict = {key: Y.count(key) for key in set(Y)}  # Y의 각 요소의 개수를 카운트한 딕셔너리 생성

    answer = ""
    for key in set(X) & set(Y):  # X와 Y에 공통으로 있는 요소만 처리
        count = min(X_dict[key], Y_dict[key])  # X와 Y에서 해당 요소의 최소 개수를 구함
        answer += key * count  # 요소를 해당 개수만큼 반복하여 추가

    if not answer:
        return "-1"

    answer = "".join(sorted(answer, reverse=True))  # 결과 문자열을 정렬하여 역순으로 변환

    if answer[0] == "0":
        return "0"

    return answer

 

1) 딕셔너리 생성 방식 개선: X_dict와 Y_dict를 딕셔너리 컴프리헨션을 사용하여 더 간결하게 생성합니다. set(X)와 set(Y)로 각각의 고유한 요소만을 처리하고, count() 메서드를 사용하여 해당 요소의 개수를 카운트합니다.

2) 공통 요소 처리: set(X) & set(Y)를 사용하여 X와 Y에 공통으로 있는 요소만 처리하도록 변경합니다. 이를 통해 중복 계산을 피하고, 불필요한 요소를 건너뛰게 됩니다.

3) 문자열 조작 최소화: 결과 문자열 answer를 직접 조작하면서 요소를 추가합니다. 딕셔너리에서 해당 요소의 최소 개수를 가져와서 요소를 해당 개수만큼 반복하여 추가합니다. 이를 통해 문자열 조작을 최소화하고 성능을 향상하였습니다.

4) 결과 문자열 정렬: answer를 정렬할 때 리스트로 변환할 필요 없이 문자열로 그대로 정렬합니다.