231123 - kakao2022 : 진수변환+소수판별, BFS+백트래킹, DFS완전탐색, 2차원누적합

[robert-min]

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

신고 결과 받기

유저 아이디는 최대 1,000개, report의 길이는 최대 200,000이므로 신고된 유저 아이디를 배열에 관리한다면 최악의 경우 O(아이디 개수 * report의 길이) 만큼의 시간이 걸립니다. 따라서 신고된 유저 아이디를 해시(또는 연관 배열) 자료구조를 이용해 관리하면 효율적으로 목록을 완성할 수 있습니다. 이때, 신고한 유저 목록에는 같은 아이디가 중복되어 들어가지 않도록 주의해야 합니다.

위와 같이 목록을 만들었다면 신고된 유저 아이디를 순회하면서 정지 기준을 만족하는 유저가 있다면(신고한 유저 수가 k 이상이면) 신고한 유저 목록을 순회하면서 메일을 보냈다는 표시(카운트를 1 증가) 해주면 됩니다.

from collections import defaultdict

def solution(id_list, report, k):

    users = defaultdict(list)
    warning = defaultdict(int)
    for r in report:
        a, b = r.split()

        if b not in users[a]:
            users[a].append(b)
            warning[b] += 1
    # print(users)
    # print(warning)

    delete_id = []
    for key, val in warning.items():
        if val >= k:
            delete_id.append(key)
    # print(delete_id)

    answer = []
    for i in id_list:
        cnt = 0
        for u in users[i]:
            if u in delete_id:
                cnt += 1
        answer.append(cnt)

    return answer

[robert-min]

k진수에서 소수 개수 구하기(진수변환+소수판별)

이 문제는 진법 변환 후에 변환된 숫자를 0을 기준으로 파싱하고, 파싱 한 숫자를 소수 판별해 해결할 수 있는 문제입니다.

소수 판별하는 데에는 대표적으로 2가지 방법이 있습니다. 첫 번째로 에라토스테네스의 체가 있고, 두 번째는 어떤 수 n을 2부터 루트(n)까지 나눈 나머지가 모두 0이 아님을 확인하는 방법이 있습니다. 효율적인 소수 판별 알고리즘인 에라토스테네스의 체를 사용해서도 풀 수 있지만, 이 문제에서는 두 번째 방법으로도 충분히 해결할 수 있습니다.

이 문제의 제한사항을 살펴보면 n이 1부터 1,000,000까지이고 k는 3부터 10까지이므로, 1,000,000을 3진수로 바꾸면 1,212,210,202,001입니다. 일반적으로 진법 변환은 문자열을 사용해 구현하므로, 진법 변환된 문자열을 0을 기준으로 파싱 한 후에 소수를 판별하는 과정에서 정수 자료형으로 변환이 필요하게 됩니다. 이때, 개발 언어에 따라서 int 자료형의 표현 범위를 벗어날 수 있음을 유의해서 문제를 풀어야 합니다. 예를 들어 997,244를 3진수로 바꾸면 1,212,122,221,222가 됩니다. 이 숫자는 0이 없기 때문에 진법 변환된 숫자 그대로 정수 자료형으로 변환해서 소수 판별을 해야 하는데, 이는 int 자료형의 표현 범위를 벗어난다는 것을 알 수 있습니다

import math

def change_k(n, k):
    global str_n
    if n < k:
        if n > 0:
            str_n += str(n)
        return
    a, b = divmod(n, k)
    change_k(a, k)
    str_n += str(b)

def is_prime(num):

    if num == 1:
        return False

    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def check(str_n):
    tmp = ""
    cnt = 0
    for s in str_n:
        if s == "0":
            if tmp and is_prime(int(tmp)):
                cnt += 1
            tmp = ""
        else:
            tmp += s

    if tmp and is_prime(int(tmp)):
        cnt += 1
    return cnt

def solution(n, k):
    global str_n
    str_n = ""

    change_k(n, k)
    # print(str_n)

    answer = check(str_n)

    return answer

[robert-min]

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

주차 요금 계산

이 문제는 문자열 처리 능력과, 주어진 주차 요금표를 코드를 통해 정확히 구현할 수 있는지를 확인하는 문제였습니다.

특히, 이 문제는 입/출차 시각과 누적 주차 시간을 모두 ‘분’단위로 환산하여 저장하면 조금 더 쉽게 해결할 수 있습니다.

차량번호의 범위가 0000~9999이므로, 차량의 수는 최대 1만 대입니다. 이를 이용하여 두 배열 in_time, total_time을 다음과 같이 정의합니다.

in_time[i] = i번 차량이 주차장에 입차 된 시각 입차 된 적이 없거나, 출차되었다면 -1을 저장 total_time[i] = i번 차량의 누적 주차 시간

그 후 records에 담긴 원소를 순차적으로 처리해 줍니다.

“IN”을 포함하고 있다면, 시각을 저장합니다. in_time[차량번호] = 시각 “OUT”을 포함하고 있다면, 누적 주차 시간을 갱신합니다. total_time[차량번호] += ( 시각 – in_time[차량번호] ) in_time[차량번호] = -1

records를 모두 처리한 후에도 출차되지 않은 차량이 있다면, 즉, in_time[i] != -1인 모든 i번 차량에 대해서는 23시 59분(1439분)에 출차되었다고 간주하고, total_time[i]를 갱신해 줍니다.

total_time[i] += ( 1439 – in_time[i] )

위와 같은 방법으로 누적 주차 시간을 계산한 후, total_time[i] > 0 를 만족하는 모든 i번 차량에 대해서, 오름차순으로 주차 요금을 계산해서 배열에 담으면 문제를 해결할 수 있습니다

from collections import defaultdict
import math

def convert(time):
    h, m = map(int, time.split(":"))
    m += h * 60
    return m

def solution(fees, records):
    cars, total = defaultdict(int), defaultdict(int)
    for record in records:
        time, num, flag = record.split()
        if flag == "IN":
            cars[num] = convert(time)
        else:
            total[num] += convert(time) - cars[num]
            cars[num] = -1
    # print(cars)

    end = convert("23:59")
    for num, val in cars.items():
        if val == -1: continue
        total[num] += end - val

    total = sorted(total.items(), key = lambda x : x[0])
    # print(total)

    answer = []
    for num, val in total:
        if val <= fees[0]:
            answer.append(fees[1])
        else:
            remain =  (val - fees[0]) / fees[2]
            tmp = fees[1] + math.ceil(remain) * fees[3]
            answer.append(tmp)

    return answer

[robert-min]

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

양궁대회(BFS+백트래킹)

이 문제는 완전 탐색, 구현 문제입니다. 이 문제는 DFS, 비트 마스킹, 중복조합 등등 다양한 방법으로도 풀이가 가능한데요, 가장 많은 풀이가 나온 DFS를 이용한 완전 탐색으로 풀이를 진행하겠습니다.

이 문제를 해결하기 위해서는 각 점수를 아예 안 맞추거나 어피치보다 1발을 더 맞히는 경우로 각 점수(10점 ~ 0점)마다 2가지(총 2048가지)를 완전 탐색하면 됩니다.

예를 들어, 어피치가 [2,0,1,1,0,0,0,0,0,0,0]처럼 화살을 맞췄을 경우 라이언은 과녁 점수 10점을 3발 맞추거나 0발 맞추거나만 선택하면 됩니다. 9점~0점도 동일한 방식으로 어피치보다 1발을 더 맞추거나 아예 안 맞추도록 구현하면 되고, 중간에 화살을 다 쐈을 경우는 나머지 과녁 점수를 모두 0발 맞춘 것으로 처리하면 됩니다. 만약 1점까지 쏘고도 화살이 남았을 경우는 남은 화살을 0점에 다 쏘도록 처리할 수 있습니다. 이렇게 가능한 모든 경우를 살펴보면서 라이언과 어피치의 최대 점수 차이를 구하면 됩니다.

만약 10점부터 0점까지를 0발부터 n발까지 하나씩 증가시키면서 완전탐색한다면 최악의 경우 시간 초과가 발생할 수 있는 점 유의하시길 바랍니다.

중복 조합으로 푸는 경우에도 10점부터 0점까지(11가지의 경우) 총, 10발의 화살을 쏘는 게 되기 때문에 11H10 = (11 + 10 – 1) C10 = 20C10 = 184,756으로 모든 경우의 수를 확인하면서 충분히 제한 시간 안에 문제를 해결할 수 있습니다.

from collections import deque
def bfs(n, info):
    result = []
    # 현재 쏘고있는 인덱스, 화살
    Q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
    max_gap = 0

    while Q:
        idx, arrow = Q.popleft()

        if sum(arrow) == n: # 화살을 다 쏜 경우
            apeach, lion = 0, 0
            for i in range(11):
                if info[i] == 0 and arrow[i] == 0: continue
                if info[i] >= arrow[i]:
                    apeach += 10 - i
                else:
                    lion += 10 - i

            if apeach < lion:
                gap = lion - apeach
                if max_gap > gap: continue

                # 같은 gap일 경우 가장 마지막에 있는 값이 최소
                if max_gap < gap:
                    max_gap = gap
                    result.clear()

                result.append(arrow)

        elif sum(arrow) > n:   # 화살을 더 많이 쏜 경우
            continue

        elif idx == 10:  # 화살을 덜 쏜 경우
            tmp = arrow.copy()
            tmp[idx] = n - sum(tmp)
            Q.append((-1, tmp))

        else:   # 화살 쏘기
            tmp = arrow.copy()
            tmp[idx] = info[idx] + 1
            Q.append((idx+1, tmp))

            tmp2 = arrow.copy()
            tmp2[idx] = 0
            Q.append((idx+1, tmp2))

    return result

def solution(n, info):
    global answer
    answer = []
    answer = bfs(n, info)
    if not answer:
        return [-1]

    return answer[-1]

[robert-min]

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

양과 늑대 (DFS완전탐색)

4번 문제와 마찬가지로 이 문제 역시 다양한 방법으로 해결할 수 있는 문제인데요, 가장 많은 풀이가 나온 DFS를 이용한 완전탐색으로 풀이를 진행하겠습니다.

이 문제는 현재 위치, 현재까지 모은 양의 수, 늑대의 수, 그리고 다음으로 방문할 수 있는 노드 정보를 적절히 관리해 주면서 DFS를 이용해 완전탐색해서 해결할 수 있습니다. DFS를 수행하는 함수의 파라미터는 다음과 같이 구성할 수 있습니다.

DFS(현재 노드 번호, 양의 수, 늑대의 수, 다음으로 방문할 수 있는 노드의 집합)

현재 방문한 노드에 양이 있다면 양의 수를, 늑대가 있다면 늑대의 수를 1 증가시킵니다. 이때, xor 연산을 활용하면 아래와 같이 간단하게 구현할 수 있습니다. 현재 위치를 cur이라고 했을 때 현재 위치에 양이 있다면(info[cur]가 0인 경우) sheep에는 1이 더해지고, wolf에는 0이 더해집니다. 만약 늑대가 있다면 (info[cur]가 1이라면) sheep에는 0이 더해지고, wolf에는 1이 더해집니다.

sheep += info[cur] ^ 1 // xor wolf += info[cur] 다음으로 양의 수와 늑대의 수를 비교합니다. 만약 늑대가 양보다 많다면 현재 노드를 방문하는 것은 불가능하므로 더 이상 탐색하지 않습니다.

양의 수가 늑대의 수보다 더 많다면 모은 양의 최댓값을 갱신하고, 현재 노드의 자식 노드들을 다음으로 방문할 수 있는 노드 집합에 추가합니다.

이제 ‘다음으로 방문할 수 있는 노드의 집합’에 들어있는 모든 노드를 하나씩 방문하며 DFS 탐색을 수행합니다. 이 때, 다음으로 방문하는 노드의 번호를 ‘다음으로 방문할 수 있는 노드의 집합’에서 제거해 주어야 합니다.

이러한 방식으로 완전 탐색이 종료되면 최대로 모을 수 있는 양의 수를 구할 수 있습니다.

def dfs(sheep, wolf):
    global info, edges, visited, answer
    if sheep > wolf:
        answer.append(sheep)
    else:
        return

    for u, v in edges:
        if visited[u] and not visited[v]:
            visited[v] = 1
            if info[v] == 0:
                dfs(sheep+1, wolf)
            else:
                dfs(sheep, wolf+1)
            visited[v] = 0

def solution(i, e):
    global info, edges, visited, answer
    info = i
    edges = e
    answer = []
    visited = [0] * len(info)
    visited[0] = 1
    dfs(1, 0)

    return max(answer)

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=python3

파괴되지 않는 건물 (2차원누적합)

def solution(board, skill):
    answer = 0
    M = len(board[0])
    N = len(board)
    matrix = [[0] * (M + 1) for _ in range(N + 1)]

    for t, r1, c1 , r2, c2, degree in skill:
        if t == 2: degree = -degree

        matrix[r1][c1] -= degree
        matrix[r1][c2+1] += degree
        matrix[r2+1][c1] += degree
        matrix[r2+1][c2+1] -= degree
    # print(matrix)

    # 행방향 누적합
    for i in range(N):
        for j in range(M):
            matrix[i][j+1] += matrix[i][j]

    # 열방향 누적합
    for i in range(N):
        for j in range(M):
            matrix[i+1][j] += matrix[i][j]

    # print(matrix)

    for i in range(N):
        for j in range(M):
            if board[i][j] + matrix[i][j] > 0:
                answer += 1

    return answer