2021 Dev-Matching: 웹 백엔드 개발자(상반기) 문제풀이

프로그래머스에 새로 생겼길래 풀어봤다. 풀이 자체는 생각 보다 어렵지 않아서 한 번에 포스팅한다!

 

 

1. 로또의 최고 순위와 최저 순위

https://programmers.co.kr/learn/courses/30/lessons/77484

코딩테스트 연습 - 로또의 최고 순위와 최저 순위

 

해결 방법 : 단순 구현

def solution(lottos, win_nums):
    zeros = lottos.count(0)
    correct = [i for i in lottos if i in win_nums] # 맞은 개수
    highest  = 7 - len(correct) - zeros if len(correct) + zeros > 0 else 6 # 모든 zero가 맞음
    lowest  = 7 - len(correct) if len(correct) > 0 else 6 # 모든 zero가 틀림
    
    return [highest, lowest]

 

 

2. 행렬 테두리 회전하기

https://programmers.co.kr/learn/courses/30/lessons/77485

코딩테스트 연습 - 행렬 테두리 회전하기

 

해결 방법 : 단순 구현

• 깔끔하게 풀어보려고 생각해봤지만, 문제 조건상 실제로 테이블을 회전시키는 방법밖에 없는 것 같다.

def solution(rows, columns, queries):
    answer = []
    S = [[(i * columns + j + 1) for j in range(columns)] for i in range(rows)]

    for r1, c1, r2, c2 in queries:

        temp = S[r1-1][c1-1] # 처음에 변경되는 값 유지
        minv = temp # 현재 회전에서의 최솟값 변수
        for u in range(r1-1, r2-1): # 왼쪽 테두리 값 이동
            S[u][c1-1] = S[u+1][c1-1]
            minv = min(minv, S[u+1][c1-1])
        for l in range(c1-1, c2-1): # 아래쪽 테두리 값 이동
            S[r2-1][l] = S[r2-1][l+1]
            minv = min(minv, S[r2-1][l+1])
        for d in range(r2-1, r1-1, -1): # 오른쪽 ..
            S[d][c2-1] = S[d-1][c2-1]
            minv = min(minv, S[d-1][c2-1])
        for r in range(c2-1, c1-1, -1): # 위쪽 ..
            S[r1-1][r] = S[r1-1][r-1]
            minv = min(minv, S[r1-1][r-1])
        S[r1-1][c1] = temp
        
        answer.append(minv)
        
    return answer

 

 

3. 다단계 칫솔 판매

https://programmers.co.kr/learn/courses/30/lessons/77486

코딩테스트 연습 - 다단계 칫솔 판매

 

해결 방법 : DFS 완전탐색

• 문제에 주어진 Input들로 트리를 구성, 판매 금액 딕셔너리 저장
• dfs postorder 방식으로 자식노드들의 수익 10%를 받도록 한다.
  • 한 node의 총 이익금의 10%가 아니라, 모든 개별 판매 내역마다 각자 10%씩 상위로 부여되는 것을 고려해야한다.
  • 따라서 각 판매 내역을 리스트에 저장하여 각 요소들을 기준으로 10% 연산하여 상위 node로 올려주었다.
  • 결국, 특정 노드의 순수익은 = sum(연관된 판매 내역 리스트) - sum(각 판매 내역별 10% 리스트)

from collections import defaultdict
import sys
sys.setrecursionlimit(20000)

def solution(enroll, referral, seller, amount):
    T = defaultdict(list) # 조직도 트리
    S = defaultdict(list) # {직원 : [판매금액1, 판매금액2, ..]} (조건에 seller 중복이 된다고 했으므로)
    R = dict() # {직원 : 최종 수익}

    for node, p in zip(enroll, referral):
        T[p].append(node)
    for s, a in zip(seller, amount):
        S[s].append(a*100)
        
    def dfs(node):
        tot = S[node] if S.get(node) != [] else [0]

        for c in T[node]:
            tot.extend(dfs(c)) # 각 판매내역을 리스트로 저장하기 때문에 extend
        
        R[node] = sum(tot)
        per10 = [int(t/10) for t in tot if int(t/10) > 0] # 상위로 보내지는 10% 금액들
        R[node] -= sum(per10)
        return per10

    dfs("-")
    answer = [R[e] for e in enroll]

    return answer

 

4. 헤비 유저가 소유한 장소

 

해결 방법 : 서브쿼리

• 서브쿼리로 헤비유저를 산정하고 해당 host_id를 갖는 id를 추출하면 된다.

SELECT *
FROM places as p
WHERE host_id in (
    SELECT host_id
    FROM places
    GROUP BY host_id
    HAVING count(id) > 1)
ORDER BY ID