새싹프로그래머의 이야기

[문제 풀이]

• 두 큐의 합이 같게 되려면 모든 원소의 평균이 정수여야 하며, 각 큐의 합이 평균과 동일하게 만들어주면 됩니다.
• 문제에 대한 설명과 같이, 시간복잡도을 낮추고 큐의 특성을 활용하기 위해 deque()를 사용했으며, 원소의 합이 큰 쪽에서 작은 쪽으로 원소를 보내주도록 구현하였습니다.
• 이때 매번 큐의 합을 구해주는 것이 아닌 구해놓은 합에 대하여 +- 연산을 통해 시간 복잡도를 낮췄습니다.
• 마지막으로 두 개의 큐가 비지 않고 큐의 길이 * 2번 만큼 이동하게 된다면 원 상태가 되므로 해당 조건을 추가하였습니다.

[풀이 코드]

from collections import deque


def solution(queue1, queue2):
    answer = 0
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    s = (sum1 + sum2) / 2

    if s - int(s) > 0 or max(queue1) > int(s) or max(queue2) > int(s):
        return -1

    dq1 = deque(queue1)
    dq2 = deque(queue2)

    while dq1 and dq2 and sum1 != sum2 and answer <= 600000:
        if sum1 < sum2:
            v = dq2.popleft()
            dq1.append(v)

            sum1 += v
            sum2 -= v
        else:
            v = dq1.popleft()
            dq2.append(v)

            sum1 -= v
            sum2 += v
        answer += 1

    return answer if sum1 == sum2 else -1

[풀이 방법]

• 해당 문제는 주어진 cards라는 리스트에서 Circular한 그룹이 몇개가 있는지, 각 길이가 어떠한지 알아야 하는 문제입니다.
• 배열 요소를 따라가는 것은 Circular한 성질을 가지고 있으므로, 1개 이상의 그룹이 만들어집니다. 
• 또한 cards에는 중복된 요소가 들어가 있지 않으므로, 모든 요소를 탐색(즉, 모든 그룹을 탐색)하게 되면 배열의 모든 index를 탐색하게 됩니다.
• 따라서, 배열의 모든 요소가 탐색될 때까지 문제 조건에 맞춰 그룹화를 해주었습니다.

[풀이 코드]

# 두 개의 그룹의 곱이 최대가 되는 값을 찾아야한다.
# 그룹은 어떤 수로 시작해도 같은 그룹이 만들어진다.
def solution(cards):
    answer = 0
    group = []
    isopen = [-1] * len(cards)
    rnd = 1
    while isopen.count(-1) != 0:
        idx = isopen.index(-1)
        isopen[idx] = rnd
        while True:
            idx = cards[idx] - 1
            isopen[idx] = rnd
            if isopen[cards[idx] - 1] == rnd:
                break
        group.append(isopen.count(rnd))
        rnd += 1

    group.sort()
    return 0 if len(group) <= 1 else group[-1] * group[-2]

[풀이 방법]

• order에는 택배가 실려야할 순서가 있습니다. order = [4,3,1,2,5] 라면 4번째 상자, 3번째 상자, 1번째 상자 순으로 order에 맞춰 실어야 합니다.
• 이때, 순서에 맞지 않는 택배가 왔을 경우를 위한 보조 컨테이너가 있습니다. 보조 컨테이너는 stack 구조 입니다.
• 택배는 무조건 첫번째부터 순서대로 나오므로, for문을 통해 탐색을 해주었습니다. 문제 조건에 맞춰 나오는 상자의 순서와 order가 맞지 않을 경우 stack에 넣었습니다.

*이때 핵심이 되는 경우는 for문 안에 while문 입니다. 보조컨테이너 역할을 하는 q가 비어있지 않을 경우, 매 상황에 처리될 수 있는지 확인하는 코드입니다.

[풀이 코드]

from collections import deque


def solution(order):
    answer = 0
    q = deque()
    now = 0

    for i in range(len(order)):
        if i + 1 != order[now]:
            q.append(i + 1)

        if i + 1 == order[now]:
            answer += 1
            now += 1

        while q and q[-1] == order[now]:
            q.pop()
            answer += 1
            now += 1

    return answer

[문제 풀이]

• enemy 배열을 앞에서 탐색하며 무적권을 먼저 사용하는 방법을 활용했습니다.
• 하지만 사용했다해서 끝이 아니라 값을 비교하면서 무적권 안에 현재 마주한 적 수보다 작은 라운드에 무적권이 사용되었다면 현재 라운드에 무적권을 사용한 것으로 갱신해주었습니다.

[풀이 코드]

import heapq


def solution(n, k, enemy):
    answer = 0
    invinc = [0] * k  # 무적권

    for i in range(len(enemy)):
        # invinc[0] 랑 비교하면서 invinc 대체
        if enemy[i] > invinc[0]:
            n -= heapq.heapreplace(invinc, enemy[i])
        else:
            n -= enemy[i]
        if n < 0:
            return i
    return len(enemy)  # 만약 배열이 다 돌고 나서도 여기로 나온다면 n > 0 이라는 뜻으로 무조건 clear

[문제 풀이]

• m 길이의 롤러로 페인트를 칠하기 때문에 (현재 벽을 칠하는 칸 + m - 1)칸 까지 벽이 칠해지게 됩니다.
• 칠해야하는 제일 앞 칸 벽부터 칠하면서 함께 칠해진 벽을 같이 section에서 제외되도록 코드를 구성했습니다.

[문제 코드]

from collections import deque
def solution(n, m, section):
    answer = 0
    s = deque(section)
    while s:
        val = s[0]
        while s and val <= s[0] <= val + m-1:
            s.popleft()
        answer += 1
    return answer

[풀이 방법]

• 각 자리 수를 모두 0으로 만들어주면 0으로 갈 수 있으므로, 각 자리 수를 0으로 만들거나 10으로 만들어서 0으로 만들었습니다.
• ±10^c(c>=0)의 거리만큼 이동할 수 있으므로, 0으로 가는 것과 10으로 가는 것중 버튼을 적게 누르는 값을 answer에 더해주었습니다.(이때, 10으로 간다면 올림을 해주었습니다.)
• 이때, 가장 문제가 되는 경우가 5인 경우였습니다. 5인 경우 0과 10까지의 거리가 동일하고, 올림할 다음 수가 5 이상인 경우 올림을 해야 더 적은 버튼을 누를 수 있으므로 올림하는 경우로 처리하였습니다.

[풀이 코드]

from collections import deque


def solution(storey):
    answer = 0
    q = deque([i for i in str(storey)[::-1]])
    roundup = 0

    while q:
        num = int(q.popleft())

        if roundup == 1:
            num += 1
            roundup = 0

        answer += num if 10 - num > num else 10 - num
        roundup = 1 if 10 - num < num else 1 if q and num == 5 and int(q[0]) >= 5 else 0

    return answer + 1 if roundup == 1 else answer

[풀이 방법]

• 저는 문제를 풀 때, 실제로 두 좌표 간의 적분 값을 식으로 구해서 문제를 풀었습니다.
• 다만, 문제를 다 풀고 나서 보니 두 좌표 (x1,y1) , (x2,y2) 가 있을 때, (y1+y2) / 2 한 값이 적분 값이 된다는 것을 알 수 있었습니다.(뒤늦게 깨달아버렸습니다..)

[풀이 코드]

# (앞의 좌표 + 뒤의 좌표 /2) 넓이가 나옴
def func(pos1, pos2):
    x1, y1 = pos1
    x2, y2 = pos2
    A = (y2 - y1) / (x2 - x1)

    return (A / 2 * (x2 ** 2 - x1 ** 2) + (y2 - A * x2) * (x2 - x1))


def solution(k, ranges):
    answer = []
    pos = [(0, k)]
    integral = []

    while k != 1:
        k = k // 2 if k % 2 == 0 else k * 3 + 1
        pos.append((pos[-1][0] + 1, k))

    # 한칸 구간별 적분 결과 구하기
    for idx in range(0, len(pos) - 1):
        integral.append(func(pos[idx], pos[idx + 1]))

    length = len(integral)
    for a, b in ranges:
        if -b > length - a:
            answer.append(-1)
        else:
            answer.append(sum(integral[a:length + b]))

    return answer

[문제 풀이]

• sorted 함수를 통해 간단하게 풀 수 있었습니다. 코드와 같이 sorted 함수의 key에 lambda x : (x[col -1],-x[0]) 을 설정해주면 일차적으로 col번째 해당하는 값을 통해 정렬이 되는데, 해당 값이 같을 경우 제일 앞의 값(x[0])을 기준으로 정렬하게 됩니다. reverse를 설정해주지 않으면 오름차순 정렬이 이루어지므로, -x[0]을 활용할 경우 col번째 값이 같은 값들을 정렬할 때 내림차순 정렬이 이루어집니다.

[풀이 코드]

def solution(data, col, row_begin, row_end):
    data = sorted(data, key=lambda x: (x[col - 1], -x[0]))
    seq = []
    for i in range(row_begin - 1, row_end):
        s = 0
        for val in data[i]:
            s += val % (i + 1)
        seq.append(s)

    answer = seq[0]
    for i in range(1, len(seq)):
        answer = answer ^ seq[i]
    return answer

[풀이 방법]

• 틱택토에서 성립되지 않은 case를 찾았습니다.
  
  • 1. O가 완성 되었는데 X의 개수가 O의 개수와 같거나 더 많은 경우
  • 2. X가 완성 되었는데 O와 X의 개수가 다른 경우
  • 3. O와 X가 둘다 완성된 경우
  • 4. O의 갯수가 X의 개수보다 작거나 O의 개수가 X의 개수 + 1 보다 많은 경우
  • 이 문제에서 제일 시간을 많이 잡아먹은 경우는 4번 조건 이었습니다.  완성된 case가 없어도, O의 갯수는 항상 x의 개수와 같거나 더 많아야 하며, O의 개수가 X의 개수 + 1 보다 클 수 없습니다.
• 그런 다음, 주어진 배열을 탐색하면서 수직 / 수평 / 대각선으로 만들어질 수 있는 case를 모두 찾았습니다.

[풀이 코드]

def get_count(board):
    o = 0
    x = 0

    for i in board:
        o += i.count('O')
        x += i.count('X')

    return (o, x)


def get_game_set(board, o, x):
    horizontal = []
    vertical = [''] * 3
    diagonal = [''] * 2

    for i in range(len(board)):
        diagonal[0] += board[i][i]
        diagonal[1] += board[2 - i][i]

    for i in range(len(board)):
        for j in range(len(board)):
            vertical[j] += board[i][j]

    for line in board:
        if line[0] == line[1] and line[1] == line[2]:
            horizontal.append(line[0] * 3)

    fin = horizontal + vertical + diagonal

    if 'OOO' in fin and 'XXX' in fin:
        return 0
    elif ('XXX' in fin and o != x):  # "XXX"만 완성되면 O와 X의 갯수는 동일해야한다
        return 0
    elif ('OOO' in fin and x >= o):  # "OOO"만 완성되면 O의 갯수는 무조건 X의 갯수보다 많아야한다.
        return 0

    return 1


def solution(board):
    o, x = get_count(board)
    if o < x or o > x + 1:
        return 0

    return get_game_set(board, o, x)

[풀이 방법]

• 그래프 탐색 문제로 bfs 활용
• 경유지가 있으므로, (시작점에서 경유지까지의 최단거리 + 경유지에서 끝점까지의 최단거리)를 계산
• 미로를 탈출 할 수 없는 경우는 시작점에서부터 레버까지 도달하지 못하는 경우와 레버에서 끝점 까지 도달하지 못하는 경우가 있음

[풀이 코드]

from collections import deque


def search(r, c, maps, distance):
    visited = []
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    q = deque([(r, c)])

    while q:
        x, y = q.popleft()

        if (x, y) in visited:
            continue
        visited.append((x, y))
        for dx, dy in direction:
            nx, ny = x + dx, y + dy

            if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]) or maps[nx][ny] == 'X' or (nx, ny) in visited:
                continue
            distance[nx][ny] = distance[x][y] + 1
            q.append((nx, ny))


def solution(maps):
    answer = 0
    maps = [list(line) for line in maps]
    distance = [[0] * len(maps[0]) for _ in range(len(maps))]
    sr, sc, lr, lc, er, ec = 0, 0, 0, 0, 0, 0

    for i in range(len(maps)):
        if 'S' in maps[i]:
            sr, sc = i, maps[i].index('S')
        if 'L' in maps[i]:
            lr, lc = i, maps[i].index('L')
        if 'E' in maps[i]:
            er, ec = i, maps[i].index('E')

    search(sr, sc, maps, distance)
    if distance[lr][lc] == 0:
        return -1

    answer += distance[lr][lc]
    distance = [[0] * len(maps[0]) for _ in range(len(maps))]
    search(lr, lc, maps, distance)
    if distance[er][ec] == 0:
        return -1
    return answer + distance[er][ec]