우주의 IT 소행성

def solution(n, lost, reverse):
    result = 0

    # 도난을 당한 학생 리스트
    lost_list = [-99 for _ in range(n)]
    for i in lost:
        lost_list[i - 1] = i

    # 여벌을 가져온 학생 리스트
    reverse_list = [0 for _ in range(n)]
    for i in reverse:
        reverse_list[i - 1] = i

    # 여벌을 가져온 학생이 도난 당했을 경우
    for i in reverse_list:
        if i in lost:
            reverse_list[i - 1] = 0
            lost_list[i - 1] = -99

    for i in reverse_list:
        if i > 0:
            data = [-1, 1]
            for j in data:
                if i + j in lost_list:
                    lost_list[i + j - 1] = -99
                    break

    result = lost_list.count(-99)
    return result


n = int(input())
lost = list(map(int, input().split()))
reverse = list(map(int, input().split()))
print(solution(n, lost, reverse))

문제의 조건을 파악할 때
1. 여벌을 가져온 학생은 좌 우 학생에게 1벌을 빌려줄 수 있음.
2. 여벌을 가져온 학생이 도난당했을 경우도 있음
3. 여벌을 가져온 학생을 통해 최대한의 학생이(그리디) 체육복을 입을 수 있게 하라

도난/여벌 학생 리스트를 만들어 여벌 학생의 좌우를 탐색한다.
좌 우에 한 곳이라도 도난당한 학생이 있을 경우 체육복을 건내주고, 순서 마무리
마지막 카운트를 세 주면 최대 값이 나옴.

다른 사람의 코드

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    print(_reserve)
    print(_lost)

    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

n = int(input())
lost = list(map(int, input().split()))
reverse = list(map(int, input().split()))
print(solution(n, lost, reverse))

front와 back을 지정하여 lost 리스트에서 하나씩 remove를 해주었다.

간결하고 깔끔한 코드가 아닐 수 없다.

나는 사실 반복문에서 특정 리스트의 원소를 remove하는 것을 별로 좋아하지 않는다.

반복 중에 리스트의 요소에 변동이 생기게 되면 인덱스 범위를 넘어서거나 반복에 문제가 생길 때가 많았기 떄문이다

하지만 이번 문제 케이스의 경우에는 반복문에서 lost의 인덱스를 통해 어떤 분기가 결정되는게 아니므로 적합하게 사용할 수 있는 것이였다. 이런 다양한 문제를 많이 풀어봐야겠다.

from collections import deque
import sys
input = sys.stdin.readline
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

# 모든 도시 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0  # 출발 도시에서 출발 도시까지 거리는 0

# 모든 도로 정보 입력
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

# BFS 실행
queue = deque([x])
while queue:
    now = queue.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            queue.append(next_node)

# 최단 거리가 K인 도시의 번호 오름차순 출력
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True

# 최단 거리가 K인 도시가 없을 때 -1 출력
if check == False:
    print(-1)

BFS를 사용하여 푼 문제

그래프에서 모든 간선의 비용이 동일할 때에는 너비 우선 탐색으로 손쉽게 해결할 수 있다.

노드의 개수 N의 최대 : 30000

간선의 개수 M의 최대 : 10000

O(N + M)으로 해결해야 하는 문제로, 특정 도시 X를 시작점으로 BFS를 수행해 모든 도시까지의 최단 거리를 계산한 후, 각 최단 거리를 하나씩 확인하며 그 값이 K인 경우에 해당 도시의 번호를 출력한다.

파이썬의 pop() 함수를 잘 사용하여 풀 수 있음(deque 처럼, pop(0), pop())

+ 문제에 reverse 기능이 있는데, 이런 reverse가 나올 떄에는 2번 호출되면 제자리로 돌아온다는 사실을

항상 인지하고 있어야 한다. 매번 reverse를 해주면 그만큼 사용하는 메모리가 많아진다.

그리고 어차피 reverse를 하더라도 주어진 연산은 삭제밖에 없으니, reverse의 토큰 수에 따라서 왼쪽이나 오른쪽 수를 지워주기만 하면 된다.,

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    commands = input()
    n = int(input())
    data = input().rstrip()[1:-1].split(",")
    result = 0
    reverse_count = 0

    if n == 0:
        data = []

    for command in commands:
        if command == 'R':
            reverse_count += 1

        elif command == 'D':
            if len(data) > 0:
                if reverse_count % 2 == 0:
                    data.pop(0)
                else:
                    data.pop()
            else:
                result = -1

    if reverse_count % 2 == 1:
        data.reverse()
    if result == -1:
        print("error")
    else:
        print("[" + ",".join(data) +"]")

시리즈에 맞게 역시 itertools의 combinations_With_Replacement (중복조합)을 이용하면 되는 문제

이 itertools에 관련된 총 정리글을 조만간 게시글에 올려봐야겠다.

from itertools import combinations_with_replacement
n, m = map(int, input().split())
data = [i for i in range(1, n + 1)]
for i in combinations_with_replacement(data, m):
    for j in i:
        print(j, end=' ')
    print()