[프로그래머스-LV1] 숫자 짝궁 풀이 (꿀팁들)

문제 확인은 아래 링크를 통해 확인해주세요!
https://school.programmers.co.kr/learn/courses/30/lessons/131128

1. 문제 설명

2. 내가 짠 코드

"""
프로그래머스 LV1: 숫자 짝궁 (11~16번 테스트케이스 시간 초과로 실패)
https://school.programmers.co.kr/learn/courses/30/lessons/131128
"""

def solution(X, Y):
    x_dict = { x: X.count(x) for x in set(X)}
    y_dict = { y: Y.count(y) for y in set(Y)}
    
    data = []
    for x_key, x_value in x_dict.items():
        if x_key in y_dict.keys():
            for _ in range(min(x_dict[x_key], y_dict[x_key])):
                data.append(x_key)
    
    if len(data) == 0:
        return '-1'
    else:
        data = sorted(data, reverse=True)
        data = int("".join(data))
        return str(data)

원래 문제에서 최대 몇백만자리 까지 이런거 확인 안하다가.. 확인을 해야겠다고 많이 느껴서 확인해봤는데 300만이어서 나름..? 고려를 해서 짜봤지만 테스트 케이스 11번에서 16번까지 시간초과로 에러가 발생했다.

3. 뭐가 문제였을까?

• 내가 짠 방식은 X의 각 숫자의 count를 세기 위해 리스트를 순회한다. 예를 들어 set(X)에 [1,2,3]이 있으면 X에 1이 몇개있는지 쭉 순회해서 더하고, 2가 몇개있는지 쭉 순회해서 더하고 이런식으로 작동하는 것이다. 그러면 만약에 X가 300만 개의 수가 있다고 가정해보면 300만 * 3번의 순회를 하게 되는 것이다. 아주 비효율적이다.
• sorted, int/str로의 형변환도 생각보다 많은 시간이 소요되고 비효율적인 것 같다. 가급적이면 최대한 피하는 것이 좋다고 생각한다. (물론 시간복잡도 내에서는 사용해도 좋다!)

4. 그래서 어떻게 보완했는데?

"""
프로그래머스 LV1: 숫자 짝궁 (휴.. 풀었다)
https://school.programmers.co.kr/learn/courses/30/lessons/131128
"""

def solution(X, Y):
    x_count, y_count = [0] * 10, [0] * 10
    
    # 숫자 몇번 나왔는지 저장
    for x in X:
        x_count[int(x)] += 1
    for y in Y:
        y_count[int(y)] += 1
        
    # print(x_count, y_count)
    
    result = ""
    for i in range(9, -1, -1):
        result += str(i) * min(x_count[i], y_count[i])
    
    if result == "":
        return "-1"
    else:
        zeroCheck = True
        for j in range(len(result)):
            if result[j] != '0':
                zeroCheck = False
                break
        if zeroCheck == True:
            return "0"
        return result

• 0부터 9까지의 수만 나온다고 문제에 적혀있었으니 각 숫자가 몇 개 나왔는지 저장할 수 있는 배열을 선언해서 한 번만 순회해서 저장할 수 있게 한다.
• 반복문을 9부터 0으로 접근을 해야 sorted를 피할 수 있다. 우리는 최대의 숫자를 만들어야 하니까!
• 이부분이 은근 까다로웠는데 결국은 성공을 했다. 예를 들어 00으로 나오거나 023123 이런식으로 나와버리면 우리는 0 그리고 23123으로 출력을 하고싶은 것이다. 원래는 int로 형변환을 하고 다시 str로 형변환 해서 return을 하고 싶었는데 그러면 시간이 많이 소요되니까.... 앞에 0이 있고 뒤에 추가 숫자가 붙으면 추가 숫자만 return하고, 뒤에 추가숫자가 없으면 0만 return하게 했다.
• 아 잠만.. 블로그 올리고 바로 확인해봤는데 zeroCheck 부분을 그냥 len(result) == 0의 count면 0만 출력하게 하면 되네...? 에효 멍청하네 참...

5. 느낀점

• LV1이어서 얕보다가 큰코다침. 은근 빡셈..
• 이래서 부캠 코딩테스트 뚫을 수 있을랑가 싶다.
• 그래도 뭔가 감을 잡았다. 코딩테스트 뿐만 아니라 앞으로 개발할 때 어떤 메서드는 이런 효율성을 가지고 있고 항상 더욱 효율적인 코드를 짤 수 있게 많은 고민과 노력을 해야 한다는 것을 깨달았다.