알고리즘 공부 21일차

오늘은 따끈따끈하게 올라온 프로그래머스 2단계 문제인 시소 짝꿍을 풀어보려 한다. 이 문제를 보자마자 떠오른 것은 dict를 이용해보자 였다. dict를 통해 몸무게들을 효율적으로 정리한다면 짝꿍 만들기도 어렵지 않을 것이라 생각했기 때문이다. 그래서 처음엔 몸무게가 같은 짝과 다른 짝으로 나누어서 구현을 했다. 이런 단순한 아이디어로 짠 코드이다.

def solution(weights):
    answer = 0
    siso={}
    for i in weights:
        if not i in siso:
            siso[i]=1
        else:
            siso[i]+=1
    for i in siso:
        if siso[i]>1:
            answer+=siso[i]*(siso[i]-1)
        for k in range(2,5):
            if i%k==0:
                a=i//k
                for j in range(2,5):
                    if j!=k:
                        if j*a in siso:
                            answer+=siso[i]*siso[j*a]
    return answer//2

하지만 테스트 케이스는 통과하지만 제출에선 40점 정도로 통과하지 못했다. 그래서 생각한 것이 다른 짝 같은 경우 시소 (2,3),(2,4),(3,4)에 앉으면 성립되는 경우들만을 측정하고자 했다. 조금만 생각해보면 다른 경우는 이 경우의 역이라는 것을 알 수 있기에 중복을 피하고자 이런 조건을 생각했다. 또한 예시에는 몸무게가 꼭 정수라는 조건이 없다는 것을 까먹어서 i%k 부분을 다 없애고 한번 돌려보고자 했다.(사실 이부분은 헷갈렸던 것이 실수로 넘어가면 나누는 과정에서 분명 작은 오차가 발생할 것 같아 확실한 정답이 안나올 것 같았다) 이런 걱정에도 불구하고 돌렸을 때 정답처리가 되었다. 아래는 그 코드다.

def solution(weights):
    answer = 0
    siso={}
    for i in weights:
        if not i in siso:
            siso[i]=1
        else:
            siso[i]+=1
    for i in siso:
        if siso[i]>1:
            answer+=siso[i]*(siso[i]-1)/2
        if (i/2)*3 in siso:
            answer+=siso[i]*siso[(i/2)*3]
        if (i/2)*4 in siso:
            answer+=siso[i]*siso[(i/2)*4]
        if (i/3)*4 in siso:
            answer+=siso[i]*siso[(i/3)*4]
    return answer