susinlee 님의 블로그

[문제]

https://leetcode.com/problems/average-selling-price/description/

[풀이]

시계열 조인 문제로 두 가지 방법이 있다. 일반적인 조인 방법(merge)과 투 포인터 접근법을 사용한 방법(merge_asof)이다. 

일반적인 조인 방법은 모든 가능한 왼쪽-오른쪽 조합을 계산하는 것으로 O(M x N) 의 시간복잡도를 가지며, 이후 필터링 하는 것은 비용이 너무 크다.

반면, merge_asof는 O(N)의 투 포인터 접근법을 사용해 왼쪽과 오른쪽 데이터를 순회하는데, 이는 시간 정렬이 필요하지만, 시계열 데이터 처리에서는 일반적으로 시간 정렬을 필요로 하기 때문에 큰 문제가 되지 않는다.

1. merge 조인 방법

먼저 일반적인 조인 방법으로 풀어보자. prices와 units_sold를 product_id 열을 키로 병합한다. product_id의 모든 고유값을 가져와야 하므로 left join 해준다.

merged = prices.merge(units_sold, how='left')

병합한 테이블로부터 purchase_date가 start_date와 end_date 사이에 있는 행을 필터링 해준다. 추가로 purchase_date가 빈값인 행도 필터링해준다.

cond1 = merged['purchase_date'].between(merged['start_date'], merged['end_date'])
cond2 = merged['purchase_date'].isna()
merged = merged[cond1 | cond2]

자 이제 병합과 필터링을 끝마친 데이터프레임이 완성됐다. product_id 열로 그룹화한 뒤 각 product_id 별 평단가를 구해보자.

def weighted_mean(df, value, weight):
    vs = df[value]
    ws = df[weight]
    if ws.sum() != 0:
        return round((vs * ws).sum() / ws.sum(), 2)
    else:
        return 0

merged.groupby('product_id').apply(weighted_mean, 'price', 'units', include_groups=False)

product_id로 그룹화된 데이터프레임을 product_id 별로 weighted_mean 함수에 던져준다. 그러면 함수 내부에서 우리가 구하고 싶은 평균단가를 구할 수 있다. units.sum()가 0인 product_id는 0을 반환한다. 아래는 전체 코드다.

def average_selling_price(prices: pd.DataFrame, units_sold: pd.DataFrame) -> pd.DataFrame:
    merged = prices.merge(units_sold, how='left')
    cond1 = merged['purchase_date'].between(merged['start_date'], merged['end_date'])
    cond2 = merged['purchase_date'].isna()
    merged = merged[cond1 | cond2]

    def weighted_mean(df, value, weight):
        vs = df[value]
        ws = df[weight]
        return round((vs * ws).sum() / ws.sum(), 2) if ws.sum() != 0 else 0
        
    return merged.groupby('product_id').apply(weighted_mean, 'price', 'units', include_groups=False).reset_index(name='average_price')

2. merge_asof 를 이용한 방법

해당 방법을 사용하기 위해서는 먼저 병합할 열을 정렬을 해주어야 한다.

prices = prices.sort_values('start_date')
units_sold = units_sold.sort_values('purchase_date')

먼저 merge_asof 함수에 대해 알아보자.

pandas.merge_asof(left, right, on=None, left_on=None, right_on=None, by=None, left_by=None, right_by=None, tolerance=None, allow_exact_matches=True, direction='backward')

left, right :  병합할 두 데이터프레임이다.

on : 두 데이터프레임에서 병합할 공통 열 이름이다.

left_on, right on : on 대신 각 데이터프레임에서 사용할 열을 별도로 지정할 수 있다.

 by, left_by, right_by : 추가적인 그룹화 기준 열을 지정할 수 있다.

direction : 병합 방향을 설정한다. 

• 'backward' : left 값보다 작은 right의 값 중 가장 가까운 값 (기본값)
• 'forward' : left 값보다 큰 right의 값 중 가장 가까운 값
• 'nearest' : 가장 가까운 값 (작거나 크거나 상관없음)

merge_asof 는 항상 left join 만 수행한다. 구매 데이터를 가지고 평단가를 구하는 것이기 때문에 units_sold 기준으로 병합한다.

우리가 해야하는 것은 start_date 열과 purchase_date 열을 키로 product_id 별로 비교해서 병합하는 것이다.

purchase_date  값이 start_date 보다 커야 하니 start_date이 purchase_date 값과 같거나 작은 값 중 가장 가까운 값을 가져오도록 해야한다. 

merged = pd.merge_asof(units_sold, prices, by='product_id', left_on='purchase_date', right_on='start_date')

내부적으로 어떻게 돌아간 것인지 한번 시각화해보자.

by 매개변수로 product_id 의 고윳값을 나누고 해당 그룹별로 start_date와 purchase를 정렬된 상태로 나열한다.

purchase_date 값보다 start_date 값이 작거나 같은 것 중 가까운 값을 선택해서 병합된다.

이런 매커니즘으로 병합이 진행된다.

아직 몇가지 작업이 남아있다. purchase_date가 큰 값 중 작은 값이라도 end_date 값보다 커진다면 제외해 주어야 한다. 위의 케이스에서는 그런 경우는 없지만 일반화를 위해 처리해주자.

badprice = merged['purchase_date'] > merged['end_date']
merged.loc[badprice, ['price', 'units']] = 0

앞서 일반 조인과 마찬가지로 데이터프레임을 요구에 맞게 만들어주면 된다.

def weighted_mean(df, value, weight):
        vs = df[value]
        ws = df[weight]
        return round((vs * ws).sum() / ws.sum(), 2) if ws.sum() != 0 else 0

merged = merged.groupby('product_id').apply(weighted_mean, 'price', 'units', include_groups=False).reset_index(name='average_price')

마지막으로 product_id 3인 그룹도 처리해주어야 한다. 해당 그룹은 구매 기록이 없으므로 average_price 를 0으로 처리해주어야 한다.

priceIds = set(prices['product_id'].unique())
soldIds = set(units_sold['product_id'].unique())
missingIds = priceIds.difference(soldIds)
fill = pd.DataFrame({'product_id': list(missingIds), 'average_price': [0]*len(missingIds)})

이제 두 테이블을 합쳐주자

pd.concat([merged, fill])

전체코드

def average_selling_price(prices: pd.DataFrame, units_sold: pd.DataFrame) -> pd.DataFrame:
    prices = prices.sort_values('start_date')
    units_sold = units_sold.sort_values('purchase_date')

    merged = pd.merge_asof(units_sold, prices, by='product_id', left_on='purchase_date', right_on='start_date')

    badprice = merged['purchase_date'] > merged['end_date']
    merged.loc[badprice, ['price', 'units']] = 0

    def weighted_mean(df, value, weight):
            vs = df[value]
            ws = df[weight]
            return round((vs * ws).sum() / ws.sum(), 2) if ws.sum() != 0 else 0

    merged = merged.groupby('product_id').apply(weighted_mean, 'price', 'units', include_groups=False).reset_index(name='average_price')

    priceIds = set(prices['product_id'].unique())
    soldIds = set(units_sold['product_id'].unique())
    missingIds = priceIds.difference(soldIds)
    fill = pd.DataFrame({'product_id': list(missingIds), 'average_price': [0]*len(missingIds)})

    return pd.concat([merged, fill])

[문제]

https://leetcode.com/problems/not-boring-movies/

[풀이]

1. 조건1) 모듈 연산으로 id가 홀수인 행 필터링

2. 조건2) != 연산으로 description이 boring이 아닌 행 필터링

3. rating으로 내림차순 정렬

Pandas

import pandas as pd

def not_boring_movies(cinema: pd.DataFrame) -> pd.DataFrame:
    cond1 = cinema['id'] % 2 == 1
    cond2 = cinema['description'] != 'boring'
    return cinema[cond1 & cond2].sort_values(by='rating', ascending=False)

SQL

# Write your MySQL query statement below
SELECT *
FROM Cinema
WHERE id % 2 = 1 AND description != 'boring'
ORDER BY rating DESC

그래프 자료구조에 대해 배웠다. 신장 트리와 최소 신장 트리 크래프 자료구조에 대해 배웠다. 신장 트리와 최소 신장 트리 크루스칼 알고리즘을 배웠는데, 대충 어떤 구조인지 어떤 알고리즘인지만 파악했다. 외우진 못했고 (구현하라고 하면 할 수 있으려나?) 나중에 써먹을 일이 있다면 검색해서 써먹어야겠다.

[문제]

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

[풀이]

1. 날짜 비교를 datetime 모듈로 진행하였다.

2. 월이 28일까지라서 보정작업을 해줘야 한다.

3. 월이 28일이면서 달이 12월이면 연도도 보정작업을 해줘야 한다.

from datetime import datetime

def solution(today, terms, privacies):
    answer = []
    date_today = datetime.strptime(today, '%Y.%m.%d')

    dic = {s[0]: s[2:] for s in terms}

    for i, s in enumerate(privacies):
        d, t = s.split(' ')
        add_month = int(dic[t])
        year, month, day = map(int, d.split('.'))

        year = year + (month + add_month - 1) // 12
        month = (month + add_month - 1) % 12 + 1
        day = (day - 1 + 27) % 28 + 1
        if day == 28:
            month = (month - 1 + 11) % 12 + 1
            if month == 12:
                year -= 1

        date_new = datetime(year, month, day)

        if date_new < date_today:
            answer.append(i + 1)

    return answer

날짜 비교를 그냥 총 일수를 구해서 해버리는게 더 가독성 좋고 효율적이고 편하다

[문제]

https://leetcode.com/problems/confirmation-rate/description/

[풀이]

1. 모든 user_id가 보여야 하므로 Signups 테이블을 기준으로 LEFT JOIN

2. action 열에서 confirmed인 행과 아닌 행들을 1과 0으로 나눠서 comfirmation_rate을 mean 함수로 손쉽게 구할 수 있음

3. user_id로 그룹화 해준뒤 mean과 round 함수 적용

Pandas

import pandas as pd

def confirmation_rate(signups: pd.DataFrame, confirmations: pd.DataFrame) -> pd.DataFrame:
    df = pd.merge(signups, confirmations, on='user_id', how='left')
    df['confirmation_rate'] = df['action'].apply(lambda x: 1 if x=='confirmed' else 0)
    return df.groupby('user_id', as_index=False)['confirmation_rate'].mean().round(2)

SQL

SELECT s.user_id
       , ROUND(AVG(IF(action='confirmed', 1, 0)), 2) as confirmation_rate
FROM Signups s
LEFT JOIN Confirmations c
    ON s.user_id = c.user_id
GROUP BY s.user_id

1. 스택과 큐, 이진 트리 자료구조에 대해서 배웠다.

2. 웹 크롤링에 대해서 배웠다. 웬만하면 API를 쓰고, 없을 때 고려해보자.

3. 무언가 보고서를 올릴 때나 질문을 할 때 주제를 명확히 하고 그에 대한 결론을 제시하며, 상대에게 기대하는 반응을 생각하면서 글을 작성하자.

[문제]

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

[풀이]

1. 드래그의 시작점과 끝점의 규칙을 찾는다.

2. 드래그 시작점(lux, luy) 에서 lux는 파일 처음 나오는 행, luy는 파일이 처음 나오는 열이 된다.

3. 드래그 끝점(rdx, rdy) 에서 rdx는 (파일이 존재하는 마지막 행 + 1), rdy는 (파일이 존재하는 마지막 열 + 1) 이 된다.

4. 격자판을 완전탐색하면서 '#' 문자가 나오면 행과 열을 저장한다.

5. min, max 함수를 이용해서 해당 값들을 구해준다.

def solution(wallpaper):
    rows = []
    cols = []
    
    for i, v1 in enumerate(wallpaper):
        for j, v2 in enumerate(v1):
            if v2 == '#':
                rows.append(i)
                cols.append(j)    

    lux, luy = min(rows), min(cols)
    rdx, rdy = max(rows), max(cols)
    
    return [lux, luy, rdx+1, rdy+1]

[문제]

https://leetcode.com/problems/managers-with-at-least-5-direct-reports/description/

[풀이]

Pandas

import pandas as pd

def find_managers(employee: pd.DataFrame) -> pd.DataFrame:
    # manager = employee.groupby('managerId', as_index=False).size()
    # merged = manager.merge(employee, left_on='managerId', right_on='id')
    # return merged[merged['size']>=5][['name']]

    managers = employee.groupby('managerId', as_index=False)\
    .agg(reporting=('id', 'count'),).query('reporting >=5 ')['managerId']
    return employee[employee['id'].isin(managers)][['name']]

SQL

SELECT name
FROM Employee
WHERE id IN (SELECT managerId
            FROM Employee
            GROUP BY managerId
            HAVING COUNT(managerId) >= 5)

-- SELECT e.name
-- FROM Employee AS e 
-- INNER JOIN Employee AS m ON e.id=m.managerId
-- GROUP BY m.managerId
-- HAVING COUNT(m.managerId) >= 5

agg 함수와 query 함수에 대해 알아보자.

1. agg 함수

agg 함수는 집계 함수를 적용할 때 사용함. 데이터프레임이나 그룹화된 데이터에 대해 여러 집계 함수를 한 번에 적용할 수 있는 도구임.

주요 특징

1) 하나의 열에 여러 집계 함수 적용 가능

2) 여러 열에 서로 다른 집계 함수 적용 가능

3) 그룹화된(groupby()) 데이터와 함께 사용 가능

문법

DataFrame.agg(func=None, axis=0, *args, **kwrags)

func : 집계 함수 또는 함수의 리스트/딕셔너리. 함수는 문자열이나 python 함수로 전달 가능 ('mean' or np.mean)

axis : 0 이 열기준으로 기본값, 1은 행 기준

반환값은 집계된 결과를 포함하는 DataFrame 또는 Series

1) 단일 열에 여러 함수 적용하려면 함수를 리스트 형태로 전달한다. 

result = df['A'].agg(['sum', 'mean', 'max']) # 시리즈 반환
result = df[['A']].agg(['sum', 'mean', 'max']) # 데이터프레임 반환

시리즈라면 시리즈 형태로 반환하고 데이터프레임이면 데이터프레임 형태로 반환한다

2) 여러 열에 동일한 함수 적용

# 모든 열에 대해 'sum' 함수 적용
result = df.agg('sum') # 시리즈 반환 (index가 열)
result = df.agg(['sum']) # 데이터프레임 반환 (index가 함수)
result = df.agg(['sum', 'mean']) # 데이터프레임 반환 (index가 함수)

3) 여러 열에 다른 함수 적용

result = df.agg({'A': 'sum', 'B': 'mean'}) # 시리즈 반환
result = df.agg({'A': ['sum'], 'B': ['mean']}) # 데이터프레임 반환
result = df.agg({'A': ['sum', 'mean'], 'B': ['count','mean']}) # 데이터프레임 반환

{열이름 : 함수} 처럼 딕셔너리 형태로 전달하면 된다. 여러 함수를 전달하려면 딕셔너리 값에 리스트로 감싸서 전달해주면 된다.

4) 그룹화된 데이터에 사용

# group 열을 그룹화한 후 value 열에 sum과 mean 함수 적용
result = df.groupby('group').agg({'value': ['sum', 'mean']})

5) 여러 함수 적용 결과에 새로운 이름 지정 

# value 열에 sum 함수를 적용한 열의 이름을 total_sum 로 한다
# value 열에 mean 함수를 적용한 열의 이름을 avg_value 로 한다
result = df.groupby('group').agg(total_sum=('value', 'sum'),
                                 avg_value=('value', 'mean'))

2. query 함수

문자열 기반으로 데이터프레임을 필터링할 수 있는 방법을 제공함 (SQL 스타일의 조건문 사용)

문법

DataFrame.query(expr, inplace=False, **kwargs)

expr : 필터링 조건을 나타내는 문자열. SQL과 비슷한 형식으로 작성

반환값은 조건에 맞는 행만 포함하는 새로운 데이터프레임

1. 조건문으로 필터링

# A가 15보다 큰 행 필터링
filtered_df = df.query("A > 15")

2. 여러 조건 사용

# A가 15보다 크고 B가 20보다 작은 행
filtered_df = df.query("A > 15 and B < 20")

3. 문자열 조건

# 이름이 Alice인 행
filtered_df = df.query("Name == 'Alice'")

컬럼 이름에 공백이나 특수문자가 있으면 컬럼명을 백틱(`) 으로 묶어서 사용해야 함

[문제]

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

[풀이] 

1. 딕셔너리를 통해 각 유형을 key로 해서 점수를 구해준다.

2. 각 지표별로 타입을 가져오고, 해당 타입을 key로 하여 점수를 가져온다.

3. 점수를 비교해서 성격 유형을 선택한다. 점수가 같을 때에는 사전순으로 가져오게끔 한다.

from collections import defaultdict

def solution(survey, choices):
    person_type = defaultdict(int)
    answer = ''

    for types, score in zip(survey, choices):
        chr1, chr2 = types
        if score - 4 > 0:
            person_type[chr2] += score - 4
        elif score - 4 < 0:
            person_type[chr1] += 4 - score

    for x, y in [('R', 'T'), ('C', 'F'), ('J', 'M'), ('A', 'N')]:
        scoreX, scoreY = person_type[x], person_type[y]

        if scoreX >= scoreY:
            answer += x
        else:
            answer += y

    return answer

[문제]

https://leetcode.com/problems/students-and-examinations/description/?source=submission-ac

[풀이]

cross로 조인한 테이블과 미리 집계한 테이블을 이어 붙일 생각을 할 수 있어야 풀 수 있는 문제다.

판다스로 문제를 풀 때는 테이블을 무작정 이을 생각이 아니라 처리를 먼저 한 다음에 붙일 줄 알아야 한다.

Pandas

import pandas as pd

def students_and_examinations(students: pd.DataFrame, subjects: pd.DataFrame, examinations: pd.DataFrame) -> pd.DataFrame:
    merged = pd.merge(students, subjects, how='cross')

    exam_count = examinations.groupby(['student_id', 'subject_name']).agg(attended_exams=('subject_name', 'count')).reset_index()

    result = merged.merge(exam_count, on=['student_id', 'subject_name'], how='left').sort_values(by=['student_id', 'subject_name'])
    result['attended_exams'] = result['attended_exams'].fillna(0)

    return result

SQL

# Write your MySQL query statement below
SELECT stu.student_id
    , student_name
    , sub.subject_name
    , COUNT(ex.subject_name) as attended_exams
FROM Students stu
JOIN Subjects sub
LEFT JOIN Examinations ex
    ON stu.student_id = ex.student_id
    AND sub.subject_name = ex.subject_name
GROUP BY 1, 2, 3
ORDER BY 1, 3