1. 럭키 스트레이트
문제 설명
럭키 스트레이트라는 기술을 사용하기 위해서는 현재 캐릭터의 점수를 N이라고 했을 때 자릿수를 기준으로 점수 N을 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황을 의미한다.
(10 <= N <= 99,999,999, 점수 N의 자릿수는 항상 짝수이다, 1초 제한)
(사용 가능하다면 LUCKY를, 사용 불가능하다면 READY를 출력하라.)
ex) 현재 점수가 123,402라면 1+2+3 = 4+0+2 = 6로 동일하므로 사용 가능하다.
문제 풀이
점수 N의 자릿수가 항상 짝수로 주어지므로 N의 자릿수를 반으로 나누어서
문자열 슬라이싱을 통해 왼쪽 부분과 오른쪽 부분을 구해서
각 자릿수마다 더해준 후 비교하면 된다.
정답
n = str(input())
# 점수 N의 중간 길이
center = len(n) // 2
left = n[:center] # 왼쪽 부분
right = n[center:] # 오른쪽 부분
# 왼쪽 부분의 합
left_sum = 0
for i in left:
left_sum += int(i)
# 오른쪽 부분의 합
right_sum = 0
for i in right:
right_sum += int(i)
# 왼쪽 부분의 합과 오른쪽 부분의 합이 같다면
if left_sum == right_sum:
print('LUCKY')
# 왼쪽 부분의 합과 오른쪽 부분의 합이 다르다면
else:
print('READY')2. 문자열 재정렬
문제 설명
알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어진다.
이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤
모든 숫자를 더한 값을 이어서 출력하라.
(1 <= S의 길이 <= 10,000, 1초 제한)
문제 풀이
문제 설명대로 구현하면 되는 문제로 숫자와 알파벳을 어떻게 구분할 것인가에 대한 아이디어만 생각하면 되는 문제이다.
이때 숫자가 없는 경우도 생각해서 처리해야 한다.
(sum = 0으로 초기화한 경우 숫자가 없는 경우에도 0을 이어 붙이기 때문에)
정답 1
숫자로 구성된 문자열 num_list를 만들어서 숫자와 알파벳을 구분했다.
s = str(input())
# 숫자로 구성된 문자열
num_list = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
sum = 0 # 모든 숫자를 더한 값
alphabet = [] # 알파벳 리스트 (정렬을 위해서)
for i in s:
# 숫자로 구성된 경우
if i in num_list:
sum += int(i) # 숫자를 더한다.
# 알파벳으로 구성된 경우
else:
alphabet.append(i) # 알파벳 리스트에 추가한다.
# 알파벳 오름차순으로 정렬한다.
alphabet.sort()
answer = '' # 정답 문자열
# 오름차순 된 알파벳 리스트를 문자열에 추가한다.
for i in alphabet:
answer += i
# 0이 아니라면 모든 숫자를 더한 값을 이어서 출력한다.
if sum != 0:
answer += str(sum)
print(answer)정답 2
위의 구현에서는 숫자를 구분하기 위해서 num_list를 만들었지만
파이썬 기본 라이브러리에서 제공하는 isalpha()를 사용하면
더 간단하게 알파벳을 구분할 수 있다.
s = str(input())
sum = 0 # 모든 숫자를 더한 값
result = [] # 정답 리스트 (정렬을 위해서)
for i in s:
# 알파벳으로 구성된 경우
if i.isalpha():
result.append(i) # 알파벳 리스트에 추가한다.
# 숫자로 구성된 경우
else:
sum += int(i) # 숫자들을 더한다.
# 알파벳 오름차순으로 정렬한다.
result.sort()
# 0이 아니라면 모든 숫자를 더한 값을 이어서 추가한다.
if sum != 0:
result.append(str(sum))
# 리스트를 문자열로 변환하여 출력한다.
print(''.join(result))3. 문자열 압축
문제 설명
해당 링크의 기본 코드가 제공되므로 참고해서 문제를 풀어야 한다.
ababcdcdababcdcd
1개 단위 : ababcdcdababcdcd
2개 단위 : 2ab2cd2ab2cd
8개 단위 : 2ababcdcd
abcabcdede
1개 단위 : abcabcdede
2개 단위 : abcabc2de
3개 단위 : 2abcdede
위와 같은 로직으로 문자열 압축이 가능할 때,
문자열 S에 대하여 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 반환하라.
이때 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다.
xabcabc의 경우 x / abc / abc는 불가능하다.
(1 <= s의 길이 <= 1,000, s는 소문자로만 이루어짐, 1초 제한)
문제 풀이
aabbaccc의 경우
1의 단위로 압축하면 2a2ba3c
2의 단위로 압축하면 압축 불가
3의 단위로 압축하면 압축 불가
4의 단위로 압축하면 압축 불가
5의 단위부터는 압축이 불가능하다.
따라서 단위는 1부터 (문자열의 길이 // 2)까지 가능하다는 것을 알 수 있다.
이를 이용하여 단위를 늘려가며 문자열을 앞에서부터 비교하면 된다.
정답
def solution(s):
result = [] # 정답 리스트
# 문자열 길이가 1인 경우
if len(s) == 1:
return 1
# 1부터 절반까지 단위 증가
for step in range(1, len(s) // 2 + 1):
new = '' # 새로운 문자열
cnt = 1 # 갯수 체크
tmp = s[:step] # 첫번째 문자열
# 앞에서부터 단위 크기만큼 증가하면서 비교
for j in range(step, len(s), step):
# 현재 문자열과 다음 문자열이 동일하다면
if tmp == s[j:j + step]:
cnt += 1
# 현재 문자열과 다음 문자열이 다르다면
else:
# 갯수가 1이 아니라면 갯수를 앞에 기재한다.
if cnt != 1:
new += str(cnt) + tmp
# 갯수가 1이라면 갯수를 표현하지 않는다.
else:
new += tmp
# 초기화
tmp = s[j:j + step]
cnt = 1
# 남아있는 문자열에 대한 처리
if cnt != 1:
new += str(cnt) + tmp
else:
new += tmp
# 해당 단위에 대한 압축 문자열의 길이 저장
result.append(len(new))
# 최솟값 반환
return min(result)4. 자물쇠와 열쇠
문제 설명
기본 코드가 제공되므로 해당 링크를 통해 문제를 해결해야 한다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 X 1인 N X N 크기의 정사각형이고
특이한 모양의 열쇠는 M X M 크기의 정사각형이다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있다.
열쇠는 회전과 이동이 가능하며 열쇠의 돌기와 자물쇠의 홈이 맞으면 열린다.
열쇠를 나타내틑 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이
매개변수로 주어질 때 열쇠로 자물쇠를 열 수 있으면 true, 없으면 false를 반환하라.
key와 lock의 원소는 0(홈) 또는 1(돌기)로 이루어져있다.
(3 <= M <= 20, 3 <= N <= 20, M <= N, 1초 제한)
문제 풀이
자물쇠의 꼭짓점, 모서리 부분에 키가 맞는 경우도 있기 때문에
이를 처리하기 위해 자물쇠를 원래 크기의 3배를 하고 원본을 가운데에 두었다.
예를 들어 원래의 lock 다음과 같은 3 x 3 배열이라고 하면
아래와 같이 9 x 9 배열로 바꿀 수 있다.
키는 M X M으로 M은 N이하라고 했기 때문에 0부터 N x 2까지 이동시킬 경우 자물쇠의 모든 영역과 키의 모든 영역을 맞춰볼 수 있다.
또한 이때 키를 회전시킬 수 있다고 했으므로 90, 180, 270, 360도의 키에 대해서 위의 방법으로 완전 탐색하면 된다.
따라서 2차원 배열 회전 함수와 자물쇠가 모두 1인지 확인하는 함수를 구현하여
자물쇠 3배의 배열에 자물쇠를 중앙에 두고 자물쇠의 왼쪽 위부터 오른쪽 아래까지 모두 탐색할 수 있도록 0부터 N x 2까지 모두 탐색하면 된다.
정확한 시간 복잡도는 계산하기 어렵지만 4 x (N x 2) x (N x 2)로
16N^2이고 N은 20이하이므로 충분하다고 판단할 수 있다.
정답
# 2차원 배열을 시계 방향으로 90도 회전하는 함수
def rotate_matrix_90_degree(a):
n = len(a) # 행 길이 계산
m = len(a[0]) # 열 길이 계산
# 2차원 배열 만들기
result = [[0] * n for _ in range(m)]
# 각 원소를 90도 회전된 위치에 재배치
for i in range(n):
for j in range(m):
result[j][n - i - 1] = a[i][j]
return result
# 자물쇠 중간 부분이 모두 1인지를 확인하는 함수
def check(new_lock):
lock_len = len(new_lock) // 3 # 실제 자물쇠의 크기
# 자물쇠는 new_lock의 중간에 있기 때문에 중간만 탐색
for i in range(lock_len, lock_len * 2):
for j in range(lock_len, lock_len * 2):
# 자물쇠의 중간 부분 중 1이 아닌 부분이 있다면 False
if new_lock[i][j] != 1:
return False
# 모두 1이었다면 True
return True
def solution(key, lock):
n = len(lock) # 자물쇠 크기
m = len(key) # 키 크기
# 자물쇠 크기를 기존의 3배로 변환
new_lock = [[0] * (n * 3) for _ in range(n * 3)]
# 새로운 자물쇠의 중앙 부분에 기본 자물쇠 넣기
for i in range(n):
for j in range(n):
# 3배 늘어난 배열에 기존 크기만큼 우측, 아래로 이동시킨다.
new_lock[i + n][j + n] = lock[i][j]
# 4가지 방향에 대해서 모두 확인
for rotation in range(4):
key = rotate_matrix_90_degree(key) # 키를 90도 회전
# 키를 새로운 자물쇠 영역에서 이동시킨다.
# (x : 오른쪽 이동 y : 아래로 이동)
for x in range(n * 2):
for y in range(n * 2):
# 이동시킨 후 새로운 자물쇠에 열쇠를 끼워 넣기
for i in range(m):
for j in range(m):
# 기존 자물쇠 영역에 키의 값을 더한다.
# 없는 경우 : 0, 맞는 경우 : 1, 겹친 경우 : 2
new_lock[x + i][y + j] += key[i][j]
# 열쇠를 끼워 넣은 후 올바른 배치인가를 확인한다.
if check(new_lock) == True:
return True
# 자물쇠에서 열쇠를 다시 뺀다.
for i in range(m):
for j in range(m):
# 앞에서 더했던 값만큼 다시 빼서 원래 자물쇠 영역으로 만들어준다.
new_lock[x + i][y + j] -= key[i][j]
# True가 반환되지 않았다면 모든 경우에 대해서 만족하지 않는다는 의미로 False 반환
return False5. 뱀
문제 설명
'Dummy' 라는 도스게임이 있다.
이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다.
뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 N x N 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다.
게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다.
뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
- 이동 칸에 사과가 있다면, 그 칸의 사과가 없어지고 꼬리는 움직이지 않는다.
- 이동 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.
즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
조건 :
2 ≤ N ≤ 100, 0 ≤ K(사과의 개수) ≤ 100, 1 ≤ L(방향 변환 횟수)≤ 100
사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
X초가 끝난 뒤에 왼쪽('L') 또는 오른쪽('D')로 90도 방향을 회전시킨다는 뜻이다.
X <= 10,000의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
예제 입력
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D
예제 출력
9
문제 풀이
- 2차원 배열을 만들고, 0으로 초기화 한다.
- 사과의 위치에 2을 저장한다.
- (0,0)에서 뱀은 시작하고, 뱀이 지나가는 곳은 1로 바꾼다.
- 방향의 변화가 생겼는지 체크한다.
- 뱀의 머리가 사과가 없는 위치로 가면 꼬리의 값을 0으로 수정한다.
- 뱀의 머리가 사과가 있는 위치로 가면 꼬리의 값을 수정하지 않는다.
- 벽 또는 자기자신의 몸에 부딪힐 때까지 반복한다.
방향 전환에 대해서 dx와 dy로 4가지 방향을 지정해주면 편하다.
정답
# collections 모듈에서 deque를 import
from collections import deque
# 보드의 크기를 입력 받음
n = int(input())
# 사과의 개수를 입력 받음
k = int(input())
# n x n 크기의 2차원 배열 생성
arr = [[0] * n for _ in range(n)]
# 사과의 위치를 입력 받아서 배열에 2로 표시
for _ in range(k):
a, b = map(int, input().split())
arr[a - 1][b - 1] = 2
# 방향 전환 횟수를 입력 받음
l = int(input())
# 시간과 방향 전환 정보를 저장하는 딕셔너리 생성
times = {}
for _ in range(l):
a, b = input().split()
times[int(a)] = b
# 초기 뱀은 동쪽을 보고 있으므로, 동, 남, 서, 북 순서
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
# 뱀의 머리 위치를 큐에 추가
q = deque()
x, y = 0, 0
q.append((x, y)) # 추가
arr[x][y] = 1 # 뱀의 머리 위치를 1로 표시
time, d = 0, 0 # 현재 시간과 초기 방향 설정
# 무한 루프 시작
while True:
time += 1 # 시간 증가
x, y = x + dx[d], y + dy[d] # 현재 방향으로 이동
# 보드 범위 내에 있고, 뱀의 몸통이 아닌 경우
if 0 <= x < n and 0 <= y < n and arr[x][y] != 1:
# 뱀의 몸통이 아닌 경우
if arr[x][y] == 0:
tx, ty = q.popleft() # 큐에서 꼬리 위치를 꺼내서
arr[tx][ty] = 0 # 꼬리 위치를 비움
arr[x][y] = 1 # 새로운 머리 위치를 1로 표시
q.append((x, y)) # 큐에 새로운 머리 위치 추가
else:
break # 보드를 벗어나거나 뱀의 몸통과 부딪혔을 경우 루프 종료
# 방향 전환 시간에 도달한 경우
if time in times:
if times[time] == 'L':
d = (d - 1) % 4 # 왼쪽으로 방향 전환
else:
d = (d + 1) % 4 # 오른쪽으로 방향 전환
# 루프를 빠져나온 후의 시간 출력
print(time)
6. 기둥과 보 설치
문제 설명
기본 코드가 제공되므로 해당 링크를 이용하여 풀어야 한다.
문제 풀이
설치할 때의 조건 만족 여부는 명확한 확인이 가능하지만,
삭제할 때의 조건 만족 여부는 굉장히 까다롭다.
따라서 삭제를 요구할 때마다 전체 탐색을 사용할 수 있다.
시간복잡도를 고려해보면 문제에서 제한한 전체 명령의 개수는 최대 1,000개 이다.
이 문제의 시간 제한이 5초이므로 O(M^3)까지의 알고리즘도 가능할 것이다.
기둥 설치가 가능한경우
- 맨 밑에 있는 경우
- 설치 아래 지점에 기둥이 있는 경우
- 설치 왼쪽 지점에 보가 있는 경우
- 설치 지점에 보가 있는 경우
모든 조건을 만족하지 않으면 설치 불가능
보 설치가 가능한경우
- 설치 아래 지점에 기둥이 있는 경우
- 설치 아래 오른쪽 지점에 기둥이 있는 경우
- 양 옆에 보가 있는 경우
모든 조건을 만족하지 않으면 설치 불가능
정답
def check(answer):
for x, y, stuff in answer:
if stuff == 0: #기둥 체크
#'바닥 위' or '보의 한쪽 끝 위' or '또 다른 기둥 위'
if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer or [x, y - 1, 0] in answer:
continue
return False
elif stuff == 1: #보 체크
#'한쪽 끝 부분이 기둥 위' or '양쪽 끝 부분이 다른 보와 동시 연결'
if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
continue
return False
return True
def solution(n, build_frame):
answer = []
for build in build_frame:
x, y, stuff, operation = build
if operation == 1: # 설치
answer.append([x, y, stuff])
if not check(answer):
answer.remove([x, y, stuff])
elif operation == 0: # 삭제
answer.remove([x, y, stuff])
if not check(answer):
answer.append([x, y, stuff])
answer.sort()
return answer7. 치킨 배달
문제 설명
백준 15686문제이다.
문제 풀이
m개의 치킨집을 선택하는 모든 조합에 대해 도시의 치킨 거리를 구한다.
-
치킨 거리 : abs(r1-r2) + abs(c1-c2)
-
집과 치킨집의 좌료를 각각 리스트에 저장
-
조합을 이용하여 치킨집 리스트 chick에서 m개 선택하고, 치킨 거리 구하기!
정답
import sys
from itertools import combinations
input = sys.stdin.readline
n, m = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(n))
result = 999999
house = [] # 집의 좌표
chick = [] # 치킨집의 좌표
for i in range(n):
for j in range(n):
# 집의 경우
if city[i][j] == 1:
house.append([i, j])
# 치킨의 경우
elif city[i][j] == 2:
chick.append([i, j])
for chi in combinations(chick, m): # m개의 치킨집 선택
temp = 0 # 도시의 치킨 거리
for h in house:
chi_len = 999 # 각 집마다 치킨 거리
for j in range(m):
chi_len = min(chi_len, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))
temp += chi_len
result = min(result, temp)
print(result)8. 외벽 점검
문제 설명
기본 코드가 제공되므로 해당 링크를 이용하여 풀어야 한다.
문제 풀이
취약 지점 최대 15, 친구 수 최대 8 -> 완전 탐색이 가능하다!
- 투입할 친구 순서, 점검 시작 위치를 정하기
- 친구를 투입 시작
- 마지막 투입된 친구가 끝까지 확인 가능하면 멈추기
- 마지막까지 확인이 불가능하면 점검위치를 아직 확인 못한 취약 지점 중
가장 가까운 곳으로 바꾸고 반복
정답
from itertools import permutations
def solution(n, weak, dist):
m = len(weak)
answer = len(dist)+1
# 원형을 선형으로
weak = weak + [num+n for num in weak]
# 투입될 친구 순서
for friends in permutations(dist):
# 점검 시작 위치
for idx in range(m):
new_weak = weak[idx:idx+m]
now = new_weak[0]
# 점검 시작
# 친구 수
f_cnt = 0
for f in friends:
f_cnt += 1
# 최소가 아니면 멈추기
if f_cnt >= answer:
break
now = now + f
# 끝까지 점검했는가?
if now >= new_weak[-1]:
answer = f_cnt
break
else:
# 다음 점검 위치 == 아직 확인 못한 취약 지점 중 가장 가까운 곳
for w in new_weak:
if w > now:
now = w
break
if answer > len(dist):
return -1
else:
return answer참고자료
이것이 코딩 테스트다 교재 CHAP 12 구현 문제
