8/7 Coding Test

✅ Programmers

🎈 시소 짝꿍

시소는 중심으로부터 2m, 3m, 4m 거리의 지점에 좌석이 하나씩 있고 시소를 마주보고 타는 경우, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 두 사람을 시소 짝꿍이라고 한다.

즉, 탑승한 사람의 무게와 시소 축과 좌석 간 거리 곱이 양쪽 다 가으 경우 시소 짝꿍이라고 한다.

사람들의 몸무게 배열인 weights가 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하는 문제.

• weights 길이 : [2, 100,000], weights 내 사람들의 몸무게 [100, 1,000] (뉴턴 단위)

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

< 풀이 과정 >

주어진 weights 배열의 최대 길이가 10만이기에 2중 for문을 사용하는 경우 시간초과가 발생하는 문제.
따라서 다음 과정을 거쳐 해결했다.

• 빈 딕셔너리 자료구조 dic을 만든 후 각 뉴턴을 키로, 뉴턴 별 개수를 값으로 갖는 자료구조를 만들어준다.
• dic 자료구조를 loop문으로 돌며 dic원소 내 같은 뉴턴 수가 1개인 경우, 해당 뉴턴의 2/3배, 3/4배, 2배인 경우가 있다면 곱을 더해주고, 동일 뉴턴 수가 2개 이상인 경우 n(n-1)/2를 더해준다.

최종적으로 시소 짝꿍이 된 쌍의 수인 answer를 리턴.

🎈 테이블 해시 함수

DB 내 한 테이블은 컬럼이 모두 정수 타입인 상황이다. 이때 해당 테이블은 2차원 행렬로, 열은 컬럼, 행은 튜플로 나타낸다. 첫 컬럼은 기본키로 모든 튜플에 대해 uniqueness를 보장하고 테이블에 대한 해시함수를 아래와 같이 정의하였다.

• 해시함수는 col, row_begin, row_end를 입력으로 받는다.
• 테이블의 행(튜플)을 col번째 컬럼을 기준으로 오름차순 정렬하되 만약 값이 동일한 경우 첫 컬럼 값 기준으로 내림차순 정렬
• 정렬된 데이터에서 S_i를 i번째 행에 대해 각 컬럼 값을 i로 나눈 나머지의 합으로 정의
• row_begin <= i <= row_end인 모든 S_i를 누적해 bitwise XOR한 값을 해시 값으로 반환

최종적으로 테이블인 data, col, row_begin, row_end가 주어졌을 때 S_row_begin XOR S_row_end를 구하는 문제.

def solution(data, col, row_begin, row_end):
    answer = 0
    data.sort(key=lambda x: [x[col-1], -x[0]])
    for i in range(row_begin, row_end + 1):
        total = 0
        for j in data[i-1]:
            total += j%i
        answer ^= total
    return answer

< 풀이 과정 >

문제로 주어진 환경을 그대로 구현해주면 되는 문제.

• 주어진 data를 col번째는 오름차순, 값이 같으면 첫번째 컬럼 기준으로 내림차순 정렬
• for문으로 [row_begin,row_end]에 속하는 행들의 순서인덱스를 i로 두고 S_i를 계산해준다.
• j로 data[i-1]번째 행 내 모든 값을 두고 S_i += j%i로 두어 값들을 계산해준다.
• 이후 최종적으로 answer에는 XOR처리한 total값만 저장

✍️ 파이썬 비트연산자

비트 AND (&): 두 비트 모두 1인 경우에만 1을 반환합니다.
비트 OR (|): 두 비트 중 하나라도 1이면 1을 반환합니다.
비트 XOR (^): 두 비트가 서로 다른 경우에만 1을 반환합니다.
비트 NOT (~): 비트를 반전시킵니다. 0은 1로, 1은 0으로 변환됩니다.
왼쪽 시프트 (<<): 비트를 왼쪽으로 이동시킵니다. (왼쪽에 비트 추가)
오른쪽 시프트 (>>): 비트를 오른쪽으로 이동시킵니다. (오른쪽에 비트 제거)

# 비트 AND (&)
result_and = 10 & 6  # 1010 & 0110 = 0010 (2진수) -> 2 (10진수)
# 비트 OR (|)
result_or = 10 | 6   # 1010 | 0110 = 1110 (2진수) -> 14 (10진수)
# 비트 XOR (^)
result_xor = 10 ^ 6  # 1010 ^ 0110 = 1100 (2진수) -> 12 (10진수)
# 비트 NOT (~)
result_not = ~10    # ~1010 = 0101 (2진수) -> -11 (10진수)
# 왼쪽 시프트 (<<)
result_left_shift = 10 << 2  # 1010을 왼쪽으로 2비트 이동 -> 101000 (2진수) -> 40 (10진수)
# 오른쪽 시프트 (>>)
result_right_shift = 10 >> 2  # 1010을 오른쪽으로 2비트 이동 -> 10 (2진수) -> 2 (10진수)

🎈 최고의 집합

n과 s가 주어지고 자연수 n개로 이루어진 집합 중 다음 조건을 만족하는 집합을 최고의 집합이라 부른다.

• 각 원소의 합이 S가 되는 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합.

입력값으로 n과 s가 주어질때 결과로 최고의 집합을 리턴하는 문제.

def solution(n, s):
    answer = [s//n] * n
    if n > s:
        return [-1]

    for _ in range(s%n):
        answer[n-1] += 1
        n -= 1
    return answer

< 풀이 과정 >

• 길이가 n인 answer 배열을 만들어주고, 각 원소는 s//n의 값을 가진다.
• answer 배열 내 원소의 합이 s가 되어야 하므로, s를 n으로 나눈 나머지 만큼 뒷부분에 +1씩 더해준다.