[프로그래머스] Level1 : 숫자 짝꿍[Python]

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

복잡하게 푼 감이 있지만 그래도 문제의 의도에 맞게 푼거 같아서 코드 수정 없이 올림(Level1치고 난이도가 높았음)

 

우선 이 문제의 핵심은 반복문을 진행할수록 문자열의 길이를 줄이면서 해야한다.

why? - 아마 첫번째 생각한대로 알고리즘을 작성하게되면 시간초과가 발생할 것이다.

(내 기억상 테스트 케이스 5개정도가 시간초과가 발생)

deque자료구조를 사용하여 시간초과를 해결해보려 했지만, 역시나 시간초과가 발생하여 생각을 전환해보고자 하였고,

문자열 X를 기준으로 반복문을 돌면서 매 시점마다 X[0]의 문자의 개수를 count하여 X와 Y의 최소 개수만큼 리스트에 집어넣고 해당 문자는 X와 Y에서 제거해주는식으로 진행하였다.

 

풀이 :

1. X와 Y를 리스트로 변환해줌으로써 replace, count 메소드를 사용할 수 있게 함.

2. X가 ''이 될때까지 반복하면서 매시점마다 X[0]에 해당하는 문자의 개수를 X와 Y에서 count하여 더 작은 개수만큼 best_friend 리스트에 해당 문자(X[0]) 추가

3. best_friend의 있는 문자들을 내림차순으로 정렬

4. best_friend의 원소 크기만큼 조건문을 분기하여 answer 초기화

• best_friend == 0 일 경우 짝꿍이 없는 것이므로 answer = -1,
• best_frined != 0 일 경우 첫번째 원소가 '0'이면 answer = '0', 첫번째 원소가 '0'이 아니면 문자열을 합쳐줌

 

코드 :

def solution(X, Y):
    answer = ''
    best_frined = []
    X_list = list(X)
    Y_list = list(Y)
    while X:
        if len(Y) == 0:
            break
        temp = X[0]
        temp_X_count = X_list.count(temp)
        temp_Y_count = Y_list.count(temp)
        min_count = temp_X_count if temp_X_count < temp_Y_count else temp_Y_count

        for _ in range(min_count):
            best_frined.append(temp)
        X = X.replace(temp,"")
        Y = Y.replace(temp,"")

    best_frined.sort(reverse=True)
    if len(best_frined) == 0:
        answer = "-1"
    else:
        if best_frined[0] == '0':
            answer = '0'
        else:
            answer = "".join(best_frined)
    return answer