프로그래머스 [Lv. 2] 시소 짝꿍 {언어 : Python} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드 1

def solution(weights):
    answer = 0
    visited = [0 for _ in range(4001)]
    
    for w in weights:
        visited[w] += 1
    
    v = [0 for _ in range(4001)]
    for w in weights:
        if v[w]:
            continue
        v[w] = 1
        cnt = visited[w]
            
        if cnt > 1:
            answer += cnt * (cnt - 1) // 2
        if visited[w*2]:
            answer += cnt * visited[w*2]
        if w * 3 % 2 == 0 and visited[w*3//2]:
            answer += cnt * visited[w*3//2]
        if w * 4 % 3 == 0 and visited[w*4//3]:
            answer += cnt * visited[w*4//3]
            
    return answer

정답 코드 2

def solution(weights):
    answer = 0
    visited = [0 for _ in range(4001)]
    
    for w in weights:
        visited[w] += 1
    
    for w in range(100, 4001):
        cnt = visited[w]
            
        if cnt > 1:
            answer += cnt * (cnt - 1) // 2
        if 4000 >= w * 2 and visited[w*2]:
            answer += cnt * visited[w*2]
        if 4000 >= w * 3 // 2 and w * 3 % 2 == 0 and visited[w*3//2]:
            answer += cnt * visited[w*3//2]
        if 4000 >= w * 4 // 3 and w * 4 % 3 == 0 and visited[w*4//3]:
            answer += cnt * visited[w*4//3]
            
    return answer

정답 코드 3

def solution(weights):
    answer = 0
    visited = [0 for _ in range(4001)]
    
    for w in weights:
        visited[w] += 1
    
    for w in list(set(weights)):
        cnt = visited[w]
            
        if cnt > 1:
            answer += cnt * (cnt - 1) // 2
        if visited[w*2]:
            answer += cnt * visited[w*2]
        if w * 3 % 2 == 0 and visited[w*3//2]:
            answer += cnt * visited[w*3//2]
        if w * 4 % 3 == 0 and visited[w*4//3]:
            answer += cnt * visited[w*4//3]
            
    return answer

풀이 방법

1. 길이가 4001인 방문 배열을 만든다.
   1. 무게가 4000이 최대이기 때문이다.
2. weights를 순회하면서 무게의 개수를 방문배열에 저장한다.
3. 정답 코드 1이나 2 또는 3처럼 현재 무게가 중복 되지 않게 한다.
4. 자기와 짝꿍이 될 수 있는 큰 수를 찾는다.
   1. 같은 위치에 타는 경우
      1. 2m | 2m, 3m | 3m, 4m | 4m 
      2. 현재 무게의 개수로 경우의 수를 계산한다.
         1. (현재 개수) * (현재 개수 - 1) // 2
   2. 다른 위치에 타는 경우
      
      1. 4m | 2m => 내 무게 * 4 // 2 가 정수 이고 visited에 존재 하는 경우
         1. visited에 저장된 개수 * 현재 무게의 개수
      2. 4m | 3m => 내 무게 * 4 // 3 이 정수 이고 visited에 존재 하는 경우
         1. visited에 저장된 개수 * 현재 무게의 개수
      3. 3m | 2m => 내 무게 * 3 // 2 가 정수 이고 visited에 존재 하는 경우
         1. visited에 저장된 개수 * 현재 무게의 개수
5. 이렇게 구한 값들의 총합인 answer를 반환한다.

느낀점

• 왜 딕셔너리를 쓰는지 알 것 같다.