[프로그래머스] 시소 짝꿍 (python)

문제 요약

https://school.programmers.co.kr/learn/courses/30/lessons/152996

 

1. 시소에는 중심으로부터 2m, 3m, 4m 거리의 지점에 좌석이 존재

2. 두 명이 시소에 마주보고 앉았을 때, 두 명의 (무게) x (중심으로부터의 거리)가 같으면 시소 짝꿍이라고 한다.

3. weights 배열에 사람들의 몸무게 주어지며 길이는 2 ~ 100,000이다. 

4. 몸무게는 모두 정수.

 

이때, 시소 짝궁의 수를 구하는 문제이다. 

 

첫 번째 접근 (틀림)

1. weights를 작은 순서대로 정렬시킨다. 

2. 정렬시킨 weights 배열을 따라가면서 같은 몸무게의 연속된 값을 세어준다. 

3. 연속된 값이 끝나면, 몸무게가 같은 사람끼리의 짝꿍 수 nC2 = n*(n-1)/2 를 세어준다. 

4. 주어진 무게보다 작은 무게들 중 1/2, 2/3, 3/4인 몸무게가 있다면 카운트한다. 

def solution(weights):
    answer = 0

    weights.sort()

    cnt = 1
    for i in range(1, len(weights)):
        if weights[i] == weights[i - 1]:
            cnt += 1
        else:
            if cnt > 1:
                answer += cnt * (cnt - 1) // 2
                cnt = 1

            if weights[i] / 2 in weights[:i]:
                answer += 1
            if weights[i] * 2 / 3 in weights[:i]:
                answer += 1
            if weights[i] * 3 / 4 in weights[:i]:
                answer += 1
    if cnt != 1:
        answer += cnt * (cnt - 1) // 2

    return answer

 

위 풀이 방식은 본인보다 1/2, 2/3, 3/4만큼 적은 몸무게를 가진 사람이 있다면, 그 사람의 수를 모두 한명으로 더해주어서 틀린 것을 알 수 있었다. 

 

두 번째 접근 (맞음)

1. 딕셔너리를 이용해 배열에 있는 몸무게들의 개수를 저장해주었다. 

2. visit 배열을 사용해 이미 확인한 몸무게 값에 대해서는, 몸무게가 같은 사람들끼리의 짝꿍을 찾는 연산을 수행하지 못하도록 했다. 

3. 현재 몸무게보다 1/2, 2/3, 3/4인 몸무게 값들의 수를 딕셔너리에서 찾아 answer에 더해주었다.

코드

def solution(weights):
    answer = 0

    dic = {}
    for w in weights:
        if w not in dic:
            dic[w] = 1
        else:
            dic[w] += 1

    visit = []  
    for w in weights:
        if dic[w] > 1 and w not in visit:
            visit.append(w)
            answer += dic[w] * (dic[w] - 1) / 2

        if w / 2 in dic:
            answer += dic[w / 2]
        if w * 2 / 3 in dic:
            answer += dic[w * 2 / 3]
        if w * 3 / 4 in dic:
            answer += dic[w * 3 / 4]

    return answer

 

 

다른 풀이 

def solution(weights):
    dic={}
    friend_list=[2,3/2,4/3]
    answer = 0
    for weight in weights:
        if weight in dic:
            dic[weight]+=1
        else:
            dic[weight]=1

    for weight in dic:
        if dic[weight]>1:
            answer+=dic[weight]*(dic[weight]-1)/2
        for friend in friend_list:
            if weight*friend in dic:
                answer+=dic[weight]*dic[weight*friend]

    return answer

 

해당 풀이는 for문을 딕셔너리에서 돌려주어 몸무게가 같은 것들에 대한 연산을 생략할 수 있다.