[Algorithm] 숫자 짝꿍(python)

❗ 본 포스팅은 Programmers의 코딩테스트 연습문제를 활용합니다. 다양한 문제를 풀어보고 싶다면

    Programmers를 방문하세요.

 

프로그래머스의 숫자 짝꿍문제이다.

 

 

위의 사진처럼 문제가 주어졌는데 문제를 해석해보았다.

1. X하고 Y가 문자열로 주어진다.
2. X와 Y의 공통된 숫자를 뽑아낸다.
3. 뽑아낸 숫자들로 가장 큰 숫자를 만들어서 문자열로 출력한다.

---

처음에 X,Y를 반복문 돌려서 해결하려고 했는데 문자열로 3백만자가 들어가게 되면 당연히 시간초과가 난다..

그래도 시도해봤는데 역시 시간초과..

 

from collections import deque
def solution(X, Y):

X = deque(list(X))
Y = deque(list(Y))
answer = ''
for i in X:
    if i in Y:
        Y.remove(i)
        answer+=i
if len(answer)==0:
    answer="-1"
else:
    answer = list(str(int(answer)))
    answer.sort(reverse = True)
    answer = ''.join(answer)


return answer

## 시간초과....

 

그래서 생각해본게 Counter를 이용해보는것!

"X,Y의 각 문자열의 개수를 세고 공통된 것들만 뽑아내면 되지않을까?"

 

 

from collections import Counter

def solution(X, Y):
    X = Counter(X) # X의 문자열 count
    Y = Counter(Y) # Y의 문자열 count
    answer = "-1"
    XY = X&Y # 둘의 공통인 부분을 뽑아냄
    XY = sorted(XY.items(), reverse = True) # XY를 내림차순으로 정렬
    if XY: # XY가 True면 밑에 코드를 실행
        answer = ""
        for x,y in XY:
            answer+=(x*y) 
        if sum(list(map(int, answer)))==0:
            answer = "0"

    return answer

 

 

** 자료형 변환 .. int(”1234”)이게 문자열이 커지면 속도가 엄청 느리다. 그래서 list(map(int,”1234”)) 이런식으로 바꿔주는게 시간초과가 안난다.(이거 풀면서 처음알았네요 ㅎㅎ..)

 

** 0~9까지 밖에 없으므로 가장 큰 값은 내림차순으로 정렬한 다음에 각 숫자의 갯수만큼 문자열을 쭉 늘려주면 된다. ex) ‘1’ 3개 ‘2’ 2개 → ‘22111’