복기
[모의고사] 구현 1회차 복기
nahowo
2025. 2. 4. 23:53
- 날짜: 2025/2/4
- 주제: 구현
- 시간: 2시간
- 1/4
문제 1: 후보 추천하기
https://www.acmicpc.net/problem/1713
import sys
import heapq
input = sys.stdin.readline
def solution():
n = int(input())
pic = [] # [추천 횟수, 게시 시점, 학생 번호]
r = int(input())
rec = list(map(int, input().split()))
picD = set()
for i in range(r):
if len(pic) < n: # 사진틀이 남아있는 경우
if rec[i] in picD: # 이미 존재하는 학생인 경우
for t in range(len(pic)):
if rec[i] == pic[t][2]:
pic[t][0] += 1
heapq.heapify(pic)
break
else: # 존재하지 않는 학생인 경우
picD.add(rec[i])
heapq.heappush(pic, [1, i, rec[i]])
else: # 사진틀이 남아있지 않는 경우
if rec[i] in picD: # 이미 존재하는 학생인 경우
for t in range(len(pic)):
if rec[i] == pic[t][2]:
pic[t][0] += 1
heapq.heapify(pic)
break
else: # 존재하지 않는 학생인 경우
removed = heapq.heappop(pic)
picD.remove(removed[2])
picD.add(rec[i])
heapq.heappush(pic, [1, i, rec[i]])
result = []
for i in range(len(pic)):
result.append(pic[i][2])
result.sort()
return result
print(*solution())
- 단순구현인데 heapq를 잘못 사용해서 몇번 틀렸다…
- 사진틀에 이미 존재하는 학생의 경우 추천수를 증가시키는데, 이 때 heapify를 해주지 않으면 최소 힙이 유지되지 않는다.
문제 2: 체스
https://www.acmicpc.net/problem/1986
- 시간 안에 못 풀었다.
- 시간복잡도를 생각해보자. 나이트는 총 8번의 이동을 하고, 폰은 이동하지 않으며 퀸은 최악의 경우 4n - 4번 이동한다. n과 m의 제한이 각 1000이고 퀸의 개수는 최대 100개이므로 4 * 10^5인데 n*m이 더 크기 때문에 전체 시간복잡도는 O(nm), O(10^6)이다.
- 보드는 0으로 초기화한다. 퀸(1), 나이트(2), 폰(3)을 미리 보드에 배치한다.
- 나이트의 이동: 범위 내의 8방향을 전부 -1로 변경한다.
- 퀸의 이동: 8방향으로 직진하면서 전부 -1로 변경하다가 방해물을 만나거나(1, 2, 3) 범위를 벗어나면 멈춘다.
- 이동 후 보드를 순회하면서 0인 부분을 센다.
import sys
input = sys.stdin.readline
dq = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, 1], [1, -1], [-1, -1]]
dk = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]]
def solution():
n, m = map(int, input().split())
board = [[0] * (m) for _ in range(n)]
tmp = list(map(int, input().split()))
q = tmp[0]
queen = []
for i in range(1, q * 2, 2):
queen.append([tmp[i] - 1, tmp[i + 1] - 1])
board[queen[-1][0]][queen[-1][1]] = 1
tmp = list(map(int, input().split()))
k = tmp[0]
knight = []
for i in range(1, k * 2, 2):
knight.append([tmp[i] - 1, tmp[i + 1] - 1])
board[knight[-1][0]][knight[-1][1]] = 2
tmp = list(map(int, input().split()))
p = tmp[0]
pawn = []
for i in range(1, p * 2, 2):
pawn.append([tmp[i] - 1, tmp[i + 1] - 1])
board[pawn[-1][0]][pawn[-1][1]] = 3
# move queen
for i, j in queen:
for di, dj in dq:
ni, nj = i + di, j + dj
while 0 <= ni < n and 0 <= nj < m and (board[ni][nj] == 0 or board[ni][nj] == -1):
board[ni][nj] = -1
ni += di
nj += dj
# move knight
for i, j in knight:
for di, dj in dk:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < m and (board[ni][nj] == 0 or board[ni][nj] == -1):
board[ni][nj] = -1
# count
cnt = 0
for i in range(n):
for j in range(m):
if board[i][j] == 0:
cnt += 1
return cnt
print(solution())
문제 3: 주사위
https://www.acmicpc.net/problem/1041
- 시간 안에 못 풀었다.
- n이 1인 경우는 당연히 주사위 5면이 보인다.
- n이 1보다 큰 경우는 각각 주사위의 3면, 2면, 1면이 보이는 주사위로 나눌 수 있는데,
- 3면은 무조건 4개
- 2면은 8n - 12개
- 1면은 5n^2 -16n + 12개이다.
- 이웃하는 3면이 최소인 경우, 이웃하는 2면이 최소인 경우와 최소인 경우를 각각 n면과 곱해주면 된다.
- 3면 이웃은 생각하기 귀찮아서 배열로 만들었다…
- 2면 이웃은 마주보는 경우만 제외하면 되는데, 인덱스 합이 5인 경우에 해당한다.
import sys
input = sys.stdin.readline
three = [[0, 1, 2], [0, 1, 3], [0, 2, 4], [0, 3, 4],
[5, 1, 2], [5, 1, 3], [5, 2, 4], [5, 3, 4]]
def solution():
n = int(input())
numbers = list(map(int, input().split()))
if n == 1:
return sum(numbers) - max(numbers)
threeSide = 4
twoSide = 8 * n - 12
oneSide = 5 * (n ** 2) - 16 * n + 12
minThree = sum(numbers)
for t in three:
tmpSum = numbers[t[0]] + numbers[t[1]] + numbers[t[2]]
minThree = min(minThree, tmpSum)
minTwo = sum(numbers)
for i in range(6):
for j in range(i + 1, 6):
if i + j == 5:
continue
tmpSum = numbers[i] + numbers[j]
minTwo = min(minTwo, tmpSum)
return threeSide * minThree + twoSide * minTwo + oneSide * min(numbers)
print(solution())
문제 4: 순열의 순서
https://www.acmicpc.net/problem/1722
- 시간 안에 못 풀었다.
- k번째 순열을 구하는 함수와 임의의 순열의 순서를 구하는 함수를 따로 구현했다. 둘 다 팩토리얼을 이용하기 때문에 cache[n]에 n!을 넣어주었다.
- k번째 순열을 수하는 함수(getPerm)
- 자리수를 하나씩 증가시키며 몇 번째 순열인지 확인한다.
- i번째 자리가 1인 순열의 개수는 (n-i)! 개
- i번째 자리가 2인 순열의 개수는 (n-i)! 개,
- …
- k가 (n-i)!보다 크다면 i번째에 들어갈 숫자를 하나씩 증가시킨다. 물론 이전 자릿수를 만드는 데에 사용되는 숫자는 사용할 수 없다.
- k가 (n-i)!보다 크다면 현재 숫자가 i - 1자리의 숫자가 된다.
- 자리수를 하나씩 증가시키며 몇 번째 순열인지 확인한다.
- 임의의 순열의 순서를 구하는 함수(getK)
- 위와 유사하게 함수를 작성했다.
import sys
input = sys.stdin.readline
def factorial(n):
cache = [0] * (n + 1)
result = 1
for i in range(1, n + 1):
result *= i
cache[i] = result
return cache
def getPerm(k, n, cache): # 1
perm = [0] * n
visited = [False] * (n + 1)
for i in range(1, n + 1): # 현재 구성하려는 수열 위치
for j in range(1, n + 1): # 수열 요소
if not visited[j]:
if k <= cache[n - i] or k == 1:
perm[i - 1] = j
visited[j] = True
break
elif k > cache[n - i]:
k -= cache[n - i]
return perm
def getK(perm, n, cache): # 2
k = 1
p = list(range(1, n + 1)) # 남아있는 수열 요소
for i in range(1, n + 1):
idx = p.index(perm[i - 1])
k += idx * cache[n - i]
p.remove(perm[i - 1])
return [k]
def solution():
n = int(input())
cache = factorial(n)
q = list(map(int, input().split()))
num = q[0]
answer = 0
if num == 1:
answer = getPerm(q[1], n, cache)
else:
answer = getK(q[1:], n, cache)
return answer
print(*solution())