✅ 17 회차 모의고사 D-14일
🚀 1차 코딩테스트 대비
- 백준 2504 (괄호의 값)
- 백준 2018 (수들의 합 5)
- 백준 11652 (카드)
- 백준 11497 (통나무 건너뛰기)
- SQL 상품 별 오프라인 매출 구하기
1차 풀이
⭐ 1. 백준 2504 (괄호의 값)
# 1. 알고(구현): 백준 2504 (괄호의 값) - https://www.acmicpc.net/problem/2504
import sys
from io import StringIO
sys.stdin = StringIO('''(()[[]])([])''')
input = sys.stdin.readline
def solve():
S = input().strip()
stack = []
answer = 0
temp = 1
for i, char in enumerate(S):
num_type = 2 if char in ['(', ')'] else 3
# 분배법칙 가중치
if char in ['(', '[']:
temp *= num_type
stack.append(char)
else:
pair = '(' if char == ')' else '['
# 짝이 다르면
if not stack or stack[-1] != pair:
answer = 0
break
# 바로 이전과 짝이 맞으면
if S[i-1] == pair:
answer += temp
del stack[-1]
temp //= num_type
print(0 if stack else answer)
solve()⭐ 2. 백준 2018 (수들의 합 5)
# 2. 알고(수학): 백준 2018 (수들의 합 5) - https://www.acmicpc.net/problem/2018
import sys
from io import StringIO
sys.stdin = StringIO('''15''')
input = sys.stdin.readline
def solve():
N = int(input()) # 일반항 a 시작, 길이 k , N = a*k + (k*(k-1)))//2
if N <= 2: # 최적화를 위한 종료.
print(1)
return
right = 1
left = 1
cur_sum = 1 # 숫자 하나로 완성되는 값 미리 저장.
count = 1
right_limt = N // 2 + 1 # 2개 더해서 N 만드는 최대 값중 큰 값
while right <= right_limt:
if cur_sum == N:
count += 1
if cur_sum < N:
right += 1
cur_sum += right
elif cur_sum >= N:
cur_sum -= left
left += 1
print(count)
solve()⭐ 3. 백준 11652 (카드)
# 3. 알고(Map): 백준 11652 (카드) - https://www.acmicpc.net/problem/11652
import sys
from collections import Counter
from io import StringIO
sys.stdin = StringIO('''5
1
2
1
2
1''')
input = sys.stdin.readline
def solve():
N = int(input())
count = Counter(int(input()) for _ in range(N))
print(max(count, key=lambda x: (count[x], -x)))
solve()⭐ 4. 백준 11497 (통나무 건너뛰기)
# 4. 알고(그리디): 백준 11497 (통나무 건너뛰기) - https://www.acmicpc.net/problem/11497
import sys
from itertools import islice
from io import StringIO
sys.stdin = StringIO('''3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6''')
input = sys.stdin.readline
def solve():
N = int(input()) # 작은 것부터 번갈아 양끝에 두는(펜듈럼) 최적 배치
nums = sorted(map(int, input().split()))
pairs = zip(nums, islice(nums, 2, None))
max_difficulty = max(nxt - cur for cur, nxt in pairs)
print(max_difficulty)
T = int(input())
for _ in range(T):
solve()✏️ 5. SQL 상품 별 오프라인 매출 구하기
-- 5. SQL(Lv.2): 상품 별 오프라인 매출 구하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/131533
WITH
OS AS (
SELECT
PRODUCT_ID,
SUM(SALES_AMOUNT) AS COUNT
FROM OFFLINE_SALE
GROUP BY
PRODUCT_ID
)
SELECT
P.PRODUCT_CODE,
P.PRICE*OS.COUNT AS SALES
FROM OS
JOIN PRODUCT P USING (PRODUCT_ID)
ORDER BY
SALES DESC,
PRODUCT_CODE ASC;🚀 2차 코딩테스트 대비
- 백준 19238 (스타트 택시)
- 백준 1890 (점프)
- 백준 10026 (적록색약)
- 백준 6443 (애너그램)
- SQL 취소되지 않은 진료 예약 조회하기
2차 풀이
⭐ 1. 백준 19238 (스타트 택시)
# 1. 알고(시뮬): 백준 19238 (스타트 택시) - https://www.acmicpc.net/problem/19238
import sys
from collections import deque
from heapq import heappop, heappush
from io import StringIO
sys.stdin = StringIO('''6 3 15
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5''')
input = sys.stdin.readline
def solve():
N, M, O = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
directions = [(0, -1), (0, +1), (-1, 0), (+1, 0)]
sr, sc = map(lambda x: int(x) - 1, input().split()) # 인덱스 맞춤
taxi_info = [sr, sc, O]
customers = dict()
for _ in range(M):
r, c, gr, gc = map(lambda x: int(x) - 1, input().split())
customers[(r, c)] = (gr, gc)
while customers: # 고객이 있는 조건이면 시작.
r, c, oil = taxi_info
candidates = list()
if (r, c) in customers: # 현재 택시 위치에 승객이 있으면
candidates.append((0, r, c))
else: # 승객을 찾아야 하면.
visited = set([(r, c)])
dq = deque([(r, c, 0)]) # (row, col dist)
best = float('inf')
while dq:
cur_r, cur_c, dist = dq.popleft()
dist += 1
if dist > best:
break
for dr, dc in directions:
nr, nc = cur_r + dr, cur_c + dc
nxt = (nr, nc)
if 0 <= nr < N and 0 <= nc < N and nxt not in visited and board[nr][nc] == 0:
visited.add(nxt)
if nxt in customers:
heappush(candidates, (dist, nr, nc))
if best == float('inf'):
best = dist
else:
dq.append((nr, nc, dist))
if not candidates: # 고객이 있는데도 후보자가 없는 경우, 종료 ( 벽에 막힘 )
return print(-1)
t_to_c_dist, sr, sc = heappop(candidates)
oil -= t_to_c_dist
if oil < 0: # 손님 태울 기름이 부족.
return print(-1)
taxi_info = [sr, sc, oil] # 손님 태움
gr, gc = customers[(sr, sc)] # 목적지 조사
c_to_g_dist = float('inf')
# 고객시작지에서 고객 도착지 까지 최단 거리 계산
visited = set([(sr, sc)])
dq = deque([(sr, sc, 0)]) # (row, col dist)
while dq:
cur_r, cur_c, dist = dq.popleft()
if cur_r == gr and cur_c == gc:
c_to_g_dist = dist
break
dist += 1
for dr, dc in directions:
nr, nc = cur_r + dr, cur_c + dc
nxt = (nr, nc)
if 0 <= nr < N and 0 <= nc < N and nxt not in visited:
val = board[nr][nc]
if val == 0:
visited.add(nxt)
dq.append((nr, nc, dist))
if c_to_g_dist == float('inf'):
return print(-1) # 도착 불가능한 목적지
oil -= c_to_g_dist
if oil < 0: # 목적지 갈 기름 부족
return print(-1)
taxi_info = [gr, gc, oil + 2*c_to_g_dist]
del customers[(sr, sc)]
print(taxi_info[2])
solve()⭐ 2. 백준 1890 (점프)
# 2. 알고(DP): 백준 1890 (점프) - https://www.acmicpc.net/problem/1890
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0''')
input = sys.stdin.readline
def solve():
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
dp[0][0] = 1
for r, c in product(range(N), repeat=2):
cur = dp[r][c]
jump = board[r][c]
if cur == 0 or jump == 0:
continue
nr = r + jump
if nr < N:
dp[nr][c] += cur
nc = c + jump
if nc < N:
dp[r][nc] += cur
print(dp[N-1][N-1])
solve()⭐ 3. 백준 10026 (적록색약)
# 3. 알고(그래프): 백준 10026 (적록색약) - https://www.acmicpc.net/problem/10026
import sys
from itertools import product
from io import StringIO
sys.stdin = StringIO('''5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR''')
input = sys.stdin.readline
def solve():
N = int(input())
board = [list(input().rstrip()) for _ in range(N)]
directions = [(+1, 0), (-1, 0), (0, +1), (0, -1)]
coords = tuple(product(range(N), repeat=2))
visited = [[False] * N for _ in range(N)]
def find_area(r, c):
base = board[r][c]
visited[r][c] = True
stack = [(r, c)]
while stack:
cur_r, cur_c = stack.pop()
for dr, dc in directions:
nr, nc = cur_r + dr, cur_c + dc
if 0 <= nr < N and 0 <= nc < N:
if not visited[nr][nc] and board[nr][nc] == base:
visited[nr][nc] = True
stack.append((nr, nc))
normal = 0
for r, c in coords:
if not visited[r][c]:
find_area(r, c)
normal += 1
visited = [[False] * N for _ in range(N)]
for r, c in coords:
if board[r][c] == 'R':
board[r][c] = 'G'
color_blind = 0
for r, c in coords:
if not visited[r][c]:
find_area(r, c)
color_blind += 1
print(normal, color_blind)
solve()⭐ 4. 백준 6443 (애너그램)
# 4. 알고(백트래킹): 백준 6443 (애너그램) - https://www.acmicpc.net/problem/6443
import sys
from collections import Counter
from io import StringIO
sys.stdin = StringIO('''2
abc
acba''')
input = sys.stdin.readline
def solve():
input_str = input().rstrip()
input_len = len(input_str)
count = Counter(input_str)
sorted_chars = sorted(count)
answers = list()
anagram = [''] * input_len
def dfs(length):
if length == input_len:
answers.append("".join(anagram))
return
for char in sorted_chars:
if count[char] > 0: # 개수가 남아 있을 때
count[char] -= 1 # 키가 아닌 value 값은 순회중 수정 가능
anagram[length] = char
dfs(length + 1)
# anagram[length] = '' 이거 없어도 됨 (덮어 쓰기 함)
count[char] += 1
dfs(0)
print("\n".join(answers))
N = int(input())
for _ in range(N):
solve()✏️ 5. SQL 취소되지 않은 진료 예약 조회하기
-- 5. SQL(Lv.4): 취소되지 않은 진료 예약 조회하기
-- https://school.programmers.co.kr/learn/courses/30/lessons/132204
WITH
AP AS (
SELECT
APNT_NO,
PT_NO,
MCDP_CD,
APNT_YMD,
MDDR_ID AS DR_ID
FROM APPOINTMENT
WHERE
DATE_FORMAT(APNT_YMD, '%Y-%m-%d') = '2022-04-13'
AND IFNULL(APNT_CNCL_YN, 'N') = 'N'
AND MCDP_CD = 'CS'
)
SELECT
AP.APNT_NO,
PT.PT_NAME,
AP.PT_NO,
AP.MCDP_CD,
DT.DR_NAME,
AP.APNT_YMD
FROM AP
JOIN PATIENT PT USING (PT_NO)
JOIN DOCTOR DT USING (DR_ID)
ORDER BY
AP.APNT_YMD ASC;