이번에 프로 플랜이 별조각으로 풀렸다고 해서 별조각도 모을 겸 랜덤 마라톤을 다시 달려봤습니다.

A. 체육은 수학과목 입니다 2

브론즈 V

주어진 정수의 합 + 300이 1800보다 작다면 Yes, 아니면 No 입니다.

print("Yes" if sum(map(int, (input() for _ in range(4)))) + 300 <= 1800 else "No")

B. 알고리즘 수업 - 선택 정렬 1

브론즈 I

의사 코드를 참고하여 문제에서 요구하는 사항을 그대로 구현하면 됩니다.

N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = ()
for i in range(N - 1, 0, -1):
    m = 0
    for j in range(i + 1):
        if A[j] > A[m]:
            m = j

    if m != i:
        A[i], A[m] = A[m], A[i]
        K -= 1

        if K == 0:
            ans = (A[m], A[i])
            break

if K:
    print(-1)
else:
    print(*ans)

C. 다중 항목 선호도 조사 (Small)

브론즈 I

-인 부분을 제외하고 같은 값인 학생의 수를 쿼리마다 세면 시간 복잡도 $\mathcal{O}(nm)$에 해결할 수 있습니다.

n, m = map(int, input().split())

serveys = []
for _ in range(n):
    serveys.append(tuple(input().split()))

for _ in range(m):
    query = tuple(input().split())
    ans = 0
    for s in serveys:
        matches = True
        for column in range(3):
            if query[column] == "-":
                continue
            if query[column] != s[column]:
                matches = False

        if matches:
            ans += 1

    print(ans)

D. 등급 계산하기

실버 V

동점자가 있다면 가장 뒤에 있는 사람을 기준으로 비율이 넘어가는지를 확인하여 비율이 넘어간다면 그 다음 사람부터 해당 등급으로 매겨주면 됩니다.

예를 들어 100점이 3명, 99점이 2명 있다면 5번째 사람까지 1등급이고 그 다음부터는 2등급입니다.

100점이 11명 있다면 11번째 사람까지 1등급이고 이때 11은 2등급 컷이기도 하므로 12번째 사람부터는 3등급입니다.

N = int(input())

ans = [0] * 9
peopleCut = [4, 11, 23, 40, 60, 77, 89, 96, 101]

A = sorted(map(int, input().split()), reverse=True)

rank = 0
for i in range(N):
    ans[rank] += 1
    if i + 1 < N and A[i] == A[i + 1]:
        continue

    while i + 1 >= peopleCut[rank]:
        rank += 1

print(*ans, sep="\n")

E. KUMOH 문자열

실버 III

문제에서 설명한 대각선의 정의에 맞게 개수를 세 주면 됩니다.

$B_i = \max(X, Y)$이지 $B_i = X + Y$가 아님을, 대각선을 볼 때 $1000$번째 열까지 탐색해야 하는 부분을 주의해 줍시다.

target = "KUMOH"
revTarget = target[::-1]

N = int(input())
grid = [input() for _ in range(N)]

ans = 0

for i in range(N):
    chars = []
    for k in range(i + 1):
        if k >= len(grid[i - k]):
            continue

        chars.append(grid[i - k][k])

    s = "".join(chars)
    ans += max(s.count(target), s.count(revTarget))

for j in range(1, 1000):
    chars = []
    for k in range(N):
        if j + k >= len(grid[N - 1 - k]):
            continue

        chars.append(grid[N - 1 - k][j + k])

    s = "".join(chars)
    ans += max(s.count(target), s.count(revTarget))

print(ans)

F. 천상도

실버 II

$N = 1$인 경우는 예외처리 하고 $N > 1$이라고 가정하고 문제를 풀어봅시다.

음수가 있다면 두개씩 곱해주고, 양수는 전부 다 곱해줍니다. 곱할 음수 혹은 양수가 없다면 $N > 1$이므로 $a$에는 항상 $0$이 포함되어 있고 $0$이 답이 됩니다.

N, M = map(int, input().split())

for _ in range(M):
    a = list(map(int, input().split()))

    if N == 1:
        print(a[0])
        continue

    neg = sorted(filter(lambda x: x < 0, a))
    pos = list(filter(lambda x: x > 0, a))

    if len(neg) < 2 and not pos:
        print(0)
        continue

    ans = 1
    for i in range(0, len(neg) - 1, 2):
        ans *= neg[i] * neg[i + 1]

    for i in pos:
        ans *= i

    print(ans)

G. 우리집엔 도서관이 있어

실버 I

쌓인 책들을 정렬하기 위해서 꼭 빼야만 하는 책이 있고 그렇지 않은 책이 있습니다.

해당 방식으로 책들을 두 집합으로 나눈 뒤 빼야만 하는 집합에 속하는 책들 중 번호가 큰 것 부터 빼서 올려놓으면 정렬이 됩니다.

꼭 빼야만 하는 책은 다음과 같습니다.

어떤 책보다 아래에 있으면서 번호가 더 작은 책
그러한 책보다 번호가 더 작은 책

번호가 $N$인 책부터 $1$인 책 까지 아래에 있는 책들을 뺴야만 하는 집합에 넣어주고, 이때 해당 책들보다 번호가 작은 책도 집합에 넣어줍시다. 아래 코드에서는 집합 포함 여부를 bool 배열로 관리했습니다.

번호가 큰 책이 빠졌다면 그것보다 번호가 작은 책은 빠졌을 테니 빼기로 결정한 책이 나오면 바로 break해 주면 됩니다.

마지막으로 집합 결정을 완료한 인덱스를 저장하여 해당 인덱스 직전까지만 탐색하도록 하면 각 책을 한 번만 보므로 총 시간 복잡도 $\mathcal{O}(N)$에 해결할 수 있습니다.

N = int(input())

stack = [0] + [int(input()) for _ in range(N)]
pos = [0] * (N + 1)
for i in range(1, N + 1):
    pos[stack[i]] = i

pull = [False] * (N + 1)
completed = [False] * (N + 1)
minCompletedIdx = N + 1

for i in range(N, 0, -1):
    if pull[i]:
        continue

    for j in range(pos[i] + 1, minCompletedIdx):
        pull[stack[j]] = True

        for k in range(stack[j] - 1, 0, -1):
            if pull[k]:
                break
            pull[k] = True

    minCompletedIdx = pos[i]

print(pull.count(True))

H. 포닉스의 문단속