[BOJ] 14기 SW마에스트로 1차 코테대비

Coding Test Study 2023 Soma1

💻230204~230208 (실5 ~ 골2)

1. 부분 문자열 (실5) 6550

import sys
input = sys.stdin.readline

while True:
  try:
    s, t = map(str, input().rstrip().split())
    j = 0
    cnt = 0
    for i in range(len(t)):
      if t[i] == s[j]:
        cnt += 1
        j += 1
      if j == len(s):
        break

    if cnt == len(s):
      print('Yes')
    else:
      print('No')

  except:
    break

2. 암호해독 (실4) 14584

import sys
input = sys.stdin.readline

code = input().rstrip()
N = int(input())
word = [input().rstrip() for _ in range(N)]

f = 0
code = list(code)

for i in range(26):
  result = ''.join(code)
  for j in range(N):
    if word[j] in result:
      f = 1
      break
  if f == 1:
    print(result)
    break
  code = list(map(lambda x:chr((ord(x)-ord('a')+1)%26+ord('a')), code))

3. 암호해독 (실3) 2149

import sys
input = sys.stdin.readline

key = input().rstrip()
word = input().rstrip()

#원래 배열로 만들기
code = []
start = 0
for i in range(len(word)//len(key)):
  c = []
  for j in range(len(key)):
    c.append(word[j*(len(word)//len(key))+i])
  code.append(c)

#키 순서 찾기
n = []
for i in range(len(key)):
  cnt = 0
  for j in range(len(key)):
    if key[j] < key[i]: #자기보다 작은 것의 개수 세기
      cnt += 1
  if cnt in n: #같은 알파벳이 나오면 뒤에 있는 것이 숫자가 더 큼
    while cnt in n:
      cnt += 1
    n.append(cnt)
  else:
    n.append(cnt)

#새로운 배열에 순서바뀐 암호문 넣기
result = []
for i in range(len(word)//len(key)):
  r = []
  for j in n:
    r.append(code[i][j])
  result.append(r)

#출력
for i in range(len(word)//len(key)):
  for j in range(len(key)):
    print(result[i][j], end='')

4. 세 수의 합 (골4) 2295

import sys
input = sys.stdin.readline

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

U.sort()

for i in range(N-1, 0, -1):
  for j in range(i-1, -1, -1):
    if U[j]*3 < U[i]:
      break
    num = U[i] - U[j]
    start, end = 0, j
    while start <= end:
      if num < U[start] + U[end]:
        end -= 1
      elif num > U[start] + U[end]:
        start += 1
      else:
        print(U[i])
        exit()

5. 이중 우선순위 큐 (골4) 7662

import heapq
import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
  minQ, maxQ, dict, total = [], [], {}, 0
  k = int(input())
  for i in range(k):
    c, n = map(str, input().split())
    n = int(n)

    if c == "I":
      total += 1
      heapq.heappush(minQ, n)
      heapq.heappush(maxQ, -n)
      if n in dict:
        dict[n] += 1
      else:
        dict[n] = 1

    if c == "D":
      try:
        if n == 1:
          maxV = -heapq.heappop(maxQ)
          while not dict[maxV]:
            maxV = -heapq.heappop(maxQ)
          dict[maxV] -= 1
          total -= 1
        elif n == -1:
          minV = heapq.heappop(minQ)
          while not dict[minV]:
            minV = heapq.heappop(minQ)
          dict[minV] -= 1
          total -= 1
      except IndexError:
        maxQ, minQ = [], []

  if total > 0:
    while True:
      if dict[-maxQ[0]] == 0:
        heapq.heappop(maxQ)
      else:
        break
    while True:
      if dict[minQ[0]] == 0:
        heapq.heappop(minQ)
      else:
        break
    print(-maxQ[0], minQ[0])
  else:
    print("EMPTY")

6. 트리의 지름 (골4) 1967

dfs? bfs?

import sys
input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n+1)]
weight = [[] for _ in range(n+1)]
for i in range(n-1):
  p, c, w = map(int, input().split())
  tree[p].append(c)
  tree[c].append(p)
  weight[p].append(w)
  weight[c].append(w)
print(tree)

def dfs(v, total, visited):
  visited[v] = 1
  print(v, end=' ')
  for i in tree[v]:
    if not visited[i]:
      dfs(i, total, visited)

visited = [0]*(n+1)
dfs(1, 0, visited)

7. 노드사이의 거리 (골5) 1240

8. IOIOI (실1) 5525

N = int(input())
M = int(input())
S = input().rstrip()

answer  = 0
i = 0
cnt = 0

while i < M-1:
  if S[i:i+3] == 'IOI':
    i += 2
    cnt += 1
    if cnt == N:
      answer += 1
      cnt -= 1
  else:
    i += 1
    cnt = 0

print(answer)

9. Thinking Heap (골2) 15942

10. N과 M (4) (실3) 15652

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
U = [i+1 for i in range(N)]

def dfs(cnt, arr):
  if cnt == M:
    print(' '.join(map(str, arr)))
    return
  for i in range(N):
    if len(arr) == 0 or arr[-1] <= U[i]:
      arr.append(U[i])
      dfs(cnt+1, arr)
      arr.pop()

dfs(0, [])

11. Hashing (브2) 15829

import sys
input = sys.stdin.readline

L = int(input())
string = input().rstrip()

def H(word, i):
  return (ord(word)-ord('a')+1)*(31**i)

result = 0
for i in range(L):
  result += H(string[i], i)
print(result%1234567891)

12. 카드2 (실4) 2164

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
Q = deque([i+1 for i in range(N)])

while len(Q) > 1:
  Q.popleft()
  Q.append(Q.popleft())

print(Q[0])

13. 스택 수열 (실2) 1874

14. 쉬운 최단거리 (실1) 14940

15. 삼각형 만들기 (실3) 1448