2-2. 구현 기출문제

Speedwell🍀·2022년 3월 17일

코딩테스트

이것이 코딩 테스트다

목록 보기

4/15

Q7. 럭키 스트레이트

난이도: ⭐
풀이 시간: 20분
시간 제한: 1초
메모리 제한: 256MB
기출: 핵심 유형
링크: https://www.acmicpc.net/problem/18406

게임의 아웃복서 캐릭터는 필살기인 '럭키 스트레이트' 기술이 있다. 이 기술은 매우 강력한 대신에 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다.

특정 조건이란 현재 캐릭터의 점수를 N이라고 할 때 자릿수를 기준으로 점수 N을 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황을 의미한다.

예를 들어 현재 점수가 123,402라면 왼쪽 부분의 각 자릿수의 합은 1+2+3, 오른쪽 부분의 각 자릿수의 합은 4+0+2이므로 두 합이 6으로 동일하여 럭키 스트레이트를 사용할 수 있다.

현재 점수 N이 주어지면 럭키 스트레이트를 사용할 수 있는 상태인지 아닌지를 알려주는 프로그램을 작성하시오.

입력 조건

첫째 줄에 N이 정수로 주어진다.(10<=N<=99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다.

출력 조건

첫째 줄에 럭키 스트레이트를 사용할 수 있다면 "LUCKY", 사용할 수 없다면 "READY"를 출력한다.

# 입력 예시 1
123402
# 출력 예시 1
LUCKY

# 입력 예시 2
7755
# 출력 예시 2
READY

<내가 푼 방식>

n = list(map(int, input()))

# sum함수 이용해서 왼쪽 부분의 합과 오른쪽 부분의 합 같은지 확인
if sum(n[:(len(n)//2)]) == sum(n[len(n)//2:]):
    print("LUCKY")
else:
    print("READY")

<해설>

정수형 데이터가 입력으로 들어왔을 때, 이를 각 자릿수로 구분하여 합을 계산한다.

파이썬의 경우 입력받은 데이터가 문자열 형태이므로, 문자열에서 각 문자를 하나씩 확인하며 정수형으로 변환한 뒤에 그 값을 합 변수에 더할 수 있다.

n = input()

length = len(n)
summary = 0

# 왼쪽 부분의 자릿수 합 더하기
for i in range(length // 2):
    summary += int(n[i])

# 오른쪽 부분의 자릿수 합 더하기
for i in range(length // 2, length):
    summary -= int(n[i])

# 왼쪽 부분과 오른쪽 부분의 자릿수 합이 동일 
if summary == 0:
    print("LUCKY")
else:
    print("READY")

Q8. 문자열 재정렬

난이도: ⭐
풀이 시간: 20분
시간 제한: 1초
메모리 제한: 128MB
기출: Facebook 인터뷰

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.

입력 조건

첫째 줄에 하나의 문자열 S가 주어진다. (1<=S의 길이<=10,000)

출력 조건

첫째 줄에 문제에서 요구하는 정답을 출력한다.

# 입력 예시 1
K1KA5CB7
# 출력 예시 1
ABCKK13

# 입력 예시 2
AJKDLSI412K4JSJ9D
# 출력 예시 2
ADDIJJKKLSS20

<내가 푼 방식>

findall 함수를 이용해 알파벳과 숫자를 분리
분리한 알파벳을 정렬한 리스트를 result에 저장한다.
반복문을 통해 모든 숫자를 더한 값을 result 리스트에 추가한다.
join함수를 이용해 리스트를 문자열로 변환 후 출력한다.

📌 sort()는 리스트만 정렬 가능하기 때문에 문자열을 넣으면 에러. sorted()는 리스트, 문자열 둘 다 정렬 가능.

import re

s = input()

# 알파벳과 숫자를 분리
numbers = re.findall(r'\d', s)
alphas = re.findall(r'[A-Z]', s)

sum_numbers = 0

# 모든 숫자를 더하기
for i in numbers:
    sum_numbers += int(i)

result = sorted(alphas) # 알파벳 오름차순 정렬
result.append(str(sum_numbers))
result = ''.join(result) # 리스트를 문자열로 변환

print(result)

<해설>

문자열이 입력되었을 때 문자를 하나씩 확인한 뒤에,

숫자인 경우 따로 합계를 계산하고
알파벳인 경우 별도의 리스트에 저장한다.

결과적으로 리스트에 저장된 알파벳들을 정렬해 출력하고, 합계를 뒤에 붙여서 출력한다.

data = input()
result = []
value = 0

# 문자를 하나씩 확인하며
for x in data:
    # 알파벳인 경우 결과 리스트에 삽입
    if x.isalpha():
        result.append(x)
    # 숫자는 따로 더하기    
    else:
        value += int(x)
        
# 알파벳을 오름차순으로 정렬
result.sort()

# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
    result.append(str(value))

# 최종 결과 출력 (리스트를 문자열로 변환하여 출력)
print(''.join(result))

Q9. 문자열 압축

난이도: 🌕🌗
풀이 시간: 30분
시간 제한: 1초
메모리 제한: 128MB
기출: 2020 카카오 신입 공채
링크: https://programmers.co.kr/learn/courses/30/lessons/60057

❗ 이 문제는 기본 코드가 제공되므로 상기 링크를 통해서 문제를 풀기

어피치는 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있다.

간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한 번만 나타난 경우 1읜 생략)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있다.
어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는 방법을 찾으려고 한다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있다.
다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법이다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 된다. 이때 3개 단위로 자르고 마지막에 남은 문자열은 그대로 붙여주면 된다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성하시오.

제한 사항

s의 길이는 1 이상 1,000 이하입니다.
s는 알파벳 소문자로만 이루어져 있다.

입출력 예시

1) s = "aabbaccc", result = 7
문자열을 1개 단위로 잘라 압축했을 때 가장 짧음

2) s = "ababcdcdababcdcd", result = 9
문자열을 8개 단위로 잘라 압축했을 때 가장 짧음

3) s = "abcabcdede", result = 8
문자열을 3개 단위로 잘라 압축했을 때 가장 짧음

4) s = "abcabcabcabcdededededede", result = 14
문자열을 6개 단위로 잘라 압축했을 때 가장 짧음

5) s = "xababcdcdababcdcd", result = 17
문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다. 따라서 주어진 문자열을 자르는 것은 불가능하기 때문에 압축 불가능

<내가 푼 방식>

문자열 길이를 소인수분해해서 약수를 구하고, 약수 리스트에 저장한다.
만약 문자열 길이가 소수라면 압축이 불가능하므로 문자열 길이 그대로 출력
약수 리스트의 원소를 하나씩 방문해서 현재 원소를 단위로 잘라 압축한다.
압축한 문자열의 길이와 answer을 비교해서 더 작은 길이를 answer로 업데이트한다.

❗완성 못함

def solution(s):
    answer = 0
    
    divisors = [] # s 길이 소인수분해해서 가능한 약수를 저장할 리스트
    same_num = 1 # 압축했을 때 반복되는 문자열의 수
    substrings = [] # 약수 단위로 자른 문자열을 저장할 리스트
    compressed = "" # 압축된 문자열 
    
    for i in range(1, len(s) + 1):
        if len(s) % i == 0: # i가 약수이면 약수 리스트에 추가
            divisors.append(i)

    if len(divisors) == 2: # s의 길이가 소수면 그대로 출력
        answer = len(s)
    
    else: # s가 소수가 아니면
        for x in divisors:
            for i in range(len(s) // x):
                # 약수 단위로 s를 잘라서 substrings 리스트에 저장
                substrings.append(s[0 + (x * i) : x + (x * i)])
                
            for j in range(len(substrings) - 1):
                if substrings[j] == substrings[j + 1]: # 반복되는 문자열이면
                    same_num += 1
                    
                else: # 반복되는 문자열이 아니면
                    if same_num != 1: # 반복되는 문자열이 있었으면
                        # compressed에 반복되는 문자열의 수 + 반복되는 문자열 추가
                        compressed += str(same_num) + substrings[j]
                    else:
                        compressed += substrings[j]
                # substrings의 마지막 원소가 반복되지 않을 때 어떻게 추가?
                        
            # answer랑 len(compressed) 중 더 작은 값을 answer에 업데이트
            answer = min(answer, len(compressed))                    

    return answer

<해설>

입력으로 주어지는 문자열의 길이가 1,000 이하이기 때문에 완전탐색(가능한 모든 경우의 수를 탐색)을 수행할 수 있다.

📌 길이가 N인 문자열이 입력되었다면 1부터 N/2까지의 모든 수를 단위로 하여 문자열을 압축하는 방법을 모두 확인하고, 가장 짧게 압축하는 길이를 출력하면 된다.

예시: "aaaabbabbabb"

1) 1개 단위
"4a2ba2ba2b"

2) 2개 단위
"2aabbabbabb"

3) 3개 단위
"aaa3abb"

4개, 5개, 6개 단위에서도 마찬가지로 진행해보면 3개 단위로 잘랐을 때가 문자열 길이 7로 가장 많이 압축되는 것을 알 수 있다.

# 상기 프로그래머스 링크에서 테스트하기
def solution(s):
    answer = len(s)
    # 1개 단위(step)부터 압축 단위를 늘려가며 확인
    for step in range(1, len(s) // 2 + 1):
        compressed = ""
        prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출
        count = 1
        # 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
        for j in range(step, len(s), step):
            # 이전 상태와 동일하다면 압축 횟수(count) 증가
            if prev == s[j:j + step]:
                count += 1
            # 다른 문자열이 나왔다면(더 이상 압축하지 못하는 경우라면)
            else:
                compressed += str(count) + prev if count >= 2 else prev
                prev = s[j:j + step] # 다시 상태 초기화
                count = 1
        # 남아있는 문자열에 대해서 처리
        compressed += str(count) + prev if count >= 2 else prev
        # 만들어지는 압축 문자열이 가장 짧은 것이 정답
        answer = min(answer, len(compressed))
    return answer

Q10. 자물쇠와 열쇠

난이도: 🌕🌗
풀이 시간: 40분
시간 제한: 1초
메모리 제한: 128MB
기출: 2020 카카오 신입 공채
링크: https://programmers.co.kr/learn/courses/30/lessons/60059

❗ 이 문제는 기본 코드가 제공되므로 상기 링크를 통해서 문제를 풀기

튜브가 문을 열려고 보니 특이한 형태의 자물쇠로 잠겨 있었고, 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 적혀있었다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1x1인 NxN 크기의 정사각 격자 형태
특이한 모양의 열쇠는 MxM 크기의 정사각 격자 형태

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있다.
열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조이다.
자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나면 안 된다.
자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열 수 있으면 true, 열 수 없으면 false를 return 하도록 solution 함수를 환성하시오.

제한 사항

key는 M x M(3<=M<=20, M은 자연수) 크기 2차원 배열
lock은 N x N(3<=N<=20, N은 자연수) 크기 2차원 배열
M은 항상 N 이하
key와 lock의 원소는 0 또는 1로 이루어짐. 이때 0은 홈 부분, 1은 돌기 부분

입출력 예시

key	lock	result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있다.

<해설>

자물쇠와 열쇠의 크기는 20 x 20보다 작다. 크기가 20 x 20인 2차원 리스트에 있는 모든 원소에 접근할 때는 400만큼의 연산이 필요하다.

➡️ 파이썬의 경우 일반적인 코딩테스트 채점 환경에서 1초에 2,000만~1억 연산을 처리할 수 있기 때문에 완전 탐색을 이용해 열쇠를 이동이나 회전시켜서 자물쇠에 끼워보는 작업을 전부 시도해볼 수 있다.

완전 탐색을 수월하게 하기 위해 자물쇠 리스트의 크기를 3배 이상으로 변경! 자물쇠 리스트는 중앙에 배치한다.

✔️ 이제 열쇠 배열을 왼쪽 위부터 시작해서 한 칸씩 이동하는 방식으로 차례대로 자물쇠의 모든 홈을 채울 수 있는지 확인하면 된다.

➡️ 자물쇠 리스트에 열쇠 리스트의 값을 더한 뒤, 더한 결과를 확인했을 때 자물쇠 부분의 모든 값이 정확히 1인지를 확인하면 된다. 만약 모든 값이 정확히 1이라면 자물쇠의 홈 부분을 정확히 채운 것이라고 할 수 있다.

효율적인 문제 풀이를 위해 '2차원 리스트를 90도 회전한 결과를 반환하는 함수'인 rotate_a_matrix_by_90_degree() 함수 구현

➡️ 2차원 리스트를 다룰 때 가끔식 사용되므로 팀 노트에 적어두고 활용하기!

# 2차원 리스트 90도 회전
def rotate_a_matrix_by_90_degree(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0] * n for _ in range(m)] # 결과 리스트
    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_length = len(new_lock) // 3
    for i in range(lock_length, lock_length * 2):
        for j in range(lock_length, lock_length * 2):
            if new_lock[i][j] != 1:
                reurn False
    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):
            new_lock[i + n][j + n] = lock[i][j]
    
    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
        for x in range(n * 2):
            for y in range(n * 2):
                # 자물쇠에 열쇠를 끼워 넣기
                for i in range(m):
                    for j in range(m):
                        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]
    return False

Q11. 뱀

난이도: 🌕🌕
풀이 시간: 40분
시간 제한: 1초
메모리 제한: 128MB
기출: 삼성전자 SW 역량테스트
링크: https://www.acmicpc.net/problem/3190

게임에서 뱀이 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이동하다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝난다.

게임은 N x N 정사각 보드 위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에는 벽이 있다. 게임을 시작할 때 뱀은 맨 위 맨 좌측에 위치하고 뱀의 길이는 1이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

먼저 뱀은 몸길이를 늘려 다음 칸에 위치시킨다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동 경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하시오.

입력 조건

첫째 줄에 보드의 크기 N(2<=N<=100)이 주어진다. 다음 줄에 사과의 개수 K(0<=K<=100)가 주어진다.
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 좌측(1행 1열)에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L(1<=L<=100)이 주어진다.
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며, 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')으로 90도 방향을 회전시킨다는 뜻이다. X는 10,000이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력 조건

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

# 입력예시 1
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D
# 출력예시 1
9

# 입력예시 2
10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L
# 출력예시 2
21

# 입력예시 3
10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L
# 출력예시 3
13

뱀의 몸길이가 늘어나는 게 중요한가...?
사과가 2x2 연속으로 있어서 자기 몸과 부딪힐 수 있어서...?

<해설>

시뮬레이션(Simulation) 유형 문제

📌 2차원 배열상의 특정 위치에서 동서남북 위치로 이동하는 기능 구현
📌 매 시점마다 뱀이 존재하는 위치를 항상 2차원 리스트에 기록 (뱀의 머리가 몸에 닿을 경우 고려)

n = int(input())
k = int(input())
data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보
info = [] # 방향 회전 정보

# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
    a, b = map(int, input().split())
    data[a][b] = 1

# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
    x, c = input().split()
    info.append((int(x), c))

# 처음에는 오른쪽을 보고 있으므로(동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn(direction, c):
    if c == "L":
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4
    return direction

def simulate():
    x, y = 1, 1 # 뱀의 머리 위치
    data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
    direction = 0 # 처음에는 동쪽을 보고 있음
    time = 0 # 시작한 뒤에 지난 '초' 시간
    index = 0 # 다음에 회전할 정보
    q = [(x, y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)

    while True:
        nx = x + dx[direction]
        ny = y + dy[direction]
        # 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
        if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
            # 사과가 없다면 이동 후에 꼬리 제거
            if data[nx][ny] == 0:
                data[nx][ny] = 2
                q.append((nx, ny))
                px, py = q.pop(0)
                data[px][py] = 0
            # 사과가 있다면 이동 후에 꼬리 그대로 두기
            if data[nx][ny] == 1:
                data[nx][ny] = 2
                q.append((nx, ny))
        # 벽이나 뱀의 몸통과 부딪혔다면
        else:
            time += 1
            break
        x, y = nx, ny # 다음 위치로 머리를 이동
        time += 1
        if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
            direction = turn(direction, info[index][1])
            index += 1
    return time

print(simulate())

Q12. 기둥과 보 설치

난이도: 🌕🌗
풀이 시간: 50분
시간 제한: 5초
메모리 제한: 128MB
기출: 2020 카카오 신입 공채
링크: https://programmers.co.kr/learn/courses/30/lessons/60061

❗ 이 문제는 기본 코드가 제공되므로 상기 링크를 통해서 문제를 풀기

죠르디는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있다.

프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있다.

기둥은 바닥 위에 있거나 보의 한 쪽 끝부붙 위에 있거나, 또는 다른 기둥 위에 있어야 한다.
보는 한쪽 끝부분이 기둥 위에 있거나, 또는 양쪽 끝부분이 다른 보와 동시에 연결되어 있어야 한다.

단, 바닥은 벽면의 맨 아래 지면을 뜻한다.

2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1x1 크기이다. 맨 처음 벽면은 비어있는 상태이다. 기둥과 보는 격자 선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있다.

기둥과 보를 삭제하는 기능도 있는데 기능과 보를 삭제한 후에 남은 기둥과 보 또한 위 규칙을 만족해야 한다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시된다.

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성하시오.

제한 사항

5 ≤ n ≤ 100, n은 자연수
1 ≤ build_frame의 세로(행) 길이 ≤ 1,000
build_frame의 가로(열) 길이 = 4
build_frame의 원소는 [x, y, a, b] 형태
- x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태
- a는 설치 또는 삭제할 구조물의 종류, 0은 기둥, 1은 보
- b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치
- 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없다.
- 바닥에 보를 설치하는 경우는 없다.
구조물을 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제한다.
구조물이 겹치도록 설치하는 경우와 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않는다.
최종 구조물의 상태는 아래 규칙에 맞춰 return 한다.
- return하는 배열은 가로(열) 길이가 3인 2차원 배열로, 각 구조물의 좌표를 담고 있어야 한다.
- return하는 배열의 원소는 [x, y, a] 형식
- x, y는 기둥, 보의 교차점 좌표이며, [가로 좌표, 세로 좌표] 형태
- 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음을 나타낸다.
- a는 구조물의 종류, 0은 기둥, 1은 보
- return하는 배열은 x 좌표 기준으로 오름차순 정렬. x 좌표가 같을 경우 y 좌표 기준으로 오름차순 정렬.
- x, y 좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 된다.

입출력 예시

n	build_frame	result
5	[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]]	[[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]
5	[[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]]	[[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]

입출력 예시 #1 설명

(1,0)에서 위쪽으로 기둥을 하나 설치 후, (1,1)에서 오른쪽으로 보를 하나 만든다.
(2,1)에서 위쪽으로 기둥을 하나 설치 후, (2,2)에서 오른쪽으로 보를 하나 만든다.
(5,0)에서 위쪽으로 기둥을 하나 설치 후, (5,1)에서 위쪽으로 기둥을 하나 더 설치한다.
(4,2)에서 오른쪽으로 보를 설치 후, (3,2)에서 오른쪽으로 보를 설치한다.

만약 (4,2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3,2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않는다.

입출력 예시 #2 설명

아홉 번째 작업의 경우, (1,1)에서 오른쪽에 있는 보를 삭제하면 (2,1)에서 오른쪽에 있는 보는 조건을 만족하지 않으므로 무시된다.
열 번째 작업의 경우, (2,2)에서 위쪽 방향으로 기둥을 세울 경우 조건을 만족하지 않으므로 무시된다.

<해설>

시뮬레이션 유형

일단 요구사항을 확인해보면, 전체 명령의 개수는 총 1,000개 이하이다. 전체 명령의 개수를 M이라고 할 때, 시간 복잡도 O(M^2)으로 해결하는 것이 이상적이지만, 본 문제의 시간 제한은 5초로 넉넉하기 때문에 O(M^3) 알고리즘을 이용해도 정답 판정을 받을 수 있다.

O(M^3)의 시간 복잡도로 해결하는 가장 간단한 방법은, 설치 및 삭제 연산을 요구할 때마다 일일이 '전체 구조물을 확인하며' 규칙을 확인하는 것!

possible() 메서드를 이용하여 현재의 구조물이 정상인지를 체크할 수 있도록 했다. 그래서 매번 연산이 발생할 때마다 possible() 함수를 호출하여 현재 구조물이 정상인지 체크하고, 정상이 아니라면 현재의 연산을 무시한다.

# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0: # 설치된 것이 '기둥'인 경우
            # '바닥 위' 혹은 '보의 한쪽 끝 부분 위' 혹은 '다른 기둥 위'라면 정상
            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 # 아니라면 거짓(False) 반환
        elif stuff == 1: # 설치된 것이 '보'인 경우
            # '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
            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 # 아니라면 거짓(False) 반환
    return True

def solution(n, build_frame):
    answer = []
    for frame in build_frame: # 작업(frame)의 개수는 최대 1,000개
        x, y, stuff, operate = frame
        if operate == 0: # 삭제하는 경우
            answer.remove([x, y, stuff]) # 일단 삭제를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.append([x, y, stuff]) # 가능한 구조물이 아니라면 다시 설치
        if operate == 1: # 설치하는 경우
            answer.append([x, y, stuff]) # 일단 설치를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.remove([x, y, stuff]) # 가능한 구조물이 아니라면 다시 제거
    return sorted(answer) # 정렬된 결과를 반환

Q13. 치킨 배달

난이도: 🌕🌕
풀이 시간: 40분
시간 제한: 1초
메모리 제한: 512MB
기출: 삼성전자 SW 역량테스트
링크: https://www.acmicpc.net/problem/15686

크기가 N x N인 도시가 있다. 도시는 1x1 크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r,c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 "치킨 거리"라는 말을 주로 사용하는데, 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리를 뜻한다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1,c1)과 (r2,c2) 사이의 거리는 |r1 - r2| + |c1 - c2|로 구한다.

도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개이다. 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 도시의 치킨 거리가 가장 작게 되도록 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력 조건

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

<해설>

📌 기존에 존재하는 치킨집을 줄여서 최대 M개로 유지하면서, 일반 집들로부터 M개의 치킨집까지의 거리를 줄이는 것이 목표! ➡️ 이후에 도시의 치킨 거리 합의 최솟값을 계산!

입력으로 들어오는 치킨집의 개수 범위는 M ≤ 치킨 집의 개수 ≤ 13

만약에 치킨집 중에서 M개를 고르는 조합을 고려한다면 최대 13개에서 M개를 선택하는 조합과 동일하다.

조합(Combinations) 라이브러리 사용

➡️ 치킨집 중에서 M개를 고르는 모든 경우에 대해서 치킨 거리의 합을 계산하여(완전 탐색), 치킨 거리의 최솟값을 구해 출력

from itertools import combinations

n, m = map(int, input().split())
chicken, house = [], []

for r in range(n):
    data = list(map(int, input().split()))
    for c in range(n):
        if data[c] == 1:
            house.append((r, c)) # 일반 집
        elif data[c] == 2:
            chicken.append((r, c)) # 치킨집

# 모든 치킨 집 중에서 m개의 치킨 집을 뽑는 조합 계산
candidates = list(combinations(chicken, m))

# 치킨 거리의 합을 계산하는 함수
def get_sum(candidate):
    result = 0
    # 모든 집에 대하여
    for hx, hy in house:
        # 가장 가까운 치킨 집을 찾기
        temp = 1e9
        for cx, cy in candidate:
            temp = min(temp, abs(hx - cx) + abs(hy - cy))
        # 가장 가까운 치킨 집까지의 거리를 더하기
        result += temp
    # 치킨 거리의 합 반환
    return result

# 치킨 거리의 합의 최소를 찾아 출력
result = 1e9
for candidate in candidates:
    result = min(result, get_sum(candidate))

print(result)

Q14. 외벽 점검

난이도: 🌕🌕🌕
풀이 시간: 50분
시간 제한: 1초
메모리 제한: 128MB
기출: 2020 카카오 신입 공채 1차
링크: https://programmers.co.kr/learn/courses/30/lessons/60062

❗ 이 문제는 기본 코드가 제공되므로 상기 링크를 통해서 문제를 풀기

레스토랑을 리모델링하려고 하는데, 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 한다.

레스토랑의 구조는 완전히 동그란 모양이고, 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있다. 따라서 주기적으로 친구들을 보내서 외벽의 취약 지점들이 손상되지 않았는지 점검하기로 했다. 다만, 점검 시간을 1시간으로 제한했다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하려고 한다.

레스토랑의 정북 방향 지점을 0으로 하고, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리를 나타낸다. 또, 친구들은 출발 지점부터 시계/반시계 방향으로 외벽을 따라서만 이동한다.

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최솟값을 return 하도록 solution 함수를 완성하시오.

제한 조건

n은 1 이상 200 이하인 자연수
weak의 길이는 1 이상 15 이하
- 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않는다.
- 취약 지점의 위치는 오름차순으로 정렬되어 주어진다.
- weak의 원소는 0 이상 n-1 이하인 정수
dist이 길이는 1 이상 8 이하
- dist의 원소는 1 이상 100 이하인 자연수
친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return

입출력 예시

n	weak	dist	Result
12	[1,5,6,10]	[1,2,3,4]	2
12	[1,3,4,9,10]	[3,5,7]	1

입출력 예시 #1 설명

아래 그림은 외벽의 취약 지점의 위치를 표시한 것이다.

친구들의 투입하는 예시 중 하나는 다음과 같다.

4m을 이동할 수 있는 친구는 10m 지점에서 출발해 시계방향으로 돌아 1m 위치에 있는 취약 지점에서 외벽 점검을 마친다.
2m을 이동할 수 있는 친구는 4.5m 지점에서 출발해 6.5m 지점에서 외벽 점검을 마친다.

그 외에 여러 방법들이 있지만, 두 명보다 적은 친구를 투입하는 방법은 없다. 따라서 친구를 최소 두 명 투입해야 한다.

입출력 예시 #2 설명

아래 그림은 외벽의 취약 지점의 위치를 표시한 것이다.

7m을 이동할 수 있는 친구가 4m 지점에서 출발해 반시계 방향으로 점검을 돌면 모든 취약 지점을 점검할 수 있다. 따라서 친구를 최소 한 명 투입하면 된다.

<해설>

📌 주어지는 데이터의 개수가 적을 때는 완전 탐색으로 접근 가능!

이 문제의 제한 조건에서 weak 리스트와 dist 리스트의 길이가 매우 작으므로 완전 탐색으로 해결 가능!

✔️ '투입해야 하는 친구 수의 최솟값'을 찾아야 한다.

전체 친구의 수(dist 길이)는 최대 8이다.
➡️ 모든 친구룰 무작위로 나열하는 모든 순열의 개수는 ₈P₈ = 8! = 40,320으로 충분히 계산 가능한 경우의 수이다. 따라서 친구를 나열하는 모든 경우의 수를 각각 확인하여 문제 해결!

📌 원형으로 나열된 데이터를 처리하는 경우에는, 문제 풀이를 간단히 하기 위하여 길이를 2배로 늘려서 원형을 일자 형태로 만드는 작업을 해주면 유리!!

입력예시 2에서 취약한 지점을 2번 나열해서 원형을 일자 형태로 만들면 다음과 같다.

취약한 지점: 1, 3, 4, 9, 10, 13, 15, 16, 21, 22

각 친구를 나열하는 모든 경우의 수는 3! = 6가지로 다음과 같다.

[3m, 5m, 7m]
[3m, 7m, 5m]
[5m, 3m, 7m]
[5m, 7m, 3m]
[7m, 3m, 5m]
[7m, 5m, 3m]

➡️ 각각의 경우에 대해 4개의 취약 지점을 모두 검사할 수 있는지 확인하기

예를 들어 [7m, 3m, 5m]인 경우, 7m를 이동할 수 있는 친구가 9m 지점에서 출발하여 5곳을 방문한다면 7m만 이동해도 모든 취약 지점을 점검할 수 있다.

from itertools import permutations

def solution(n, weak, dist):
    # 길이를 2배로 늘려서 '원형'을 일자 형태로 변형
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
    answer = len(dist) + 1 # 투입할 친구 수의 최솟값을 찾아야 하므로 len(dist) + 1로 초기화
    # 0부터 length - 1까지의 위치를 각각 시작점으로 설정
    for start in range(length):
        # 친구를 나열하는 모든 경우 각각에 대하여 확인
        for friends in list(permutations(dist, len(dist))):
            count = 1 # 투입할 친구의 수
            # 해당 친구가 점검할 수 있는 마지막 위치
            position = weak[start] + friends[count - 1]
            # 시작점부터 모든 취약한 지점을 확인
            for index in range(start, start + length):
                # 점검할 수 있는 위치를 벗어나는 경우
                if position < weak[index]:
                    count += 1 # 새로운 친구를 투입
                    if count > len(dist): # 더 투입이 불가능하다면 종료
                        break
                    position = weak[index] + friends[count - 1]
            answer = min(answer, count) # 최솟값 계산
    if answer > len(dist):
        return -1
    return answer

Speedwell🍀

이전 포스트

2-1. 구현 개념 & 실전 문제

다음 포스트

2-2. 구현 기출문제

이것이 코딩 테스트다

Q7. 럭키 스트레이트

Q8. 문자열 재정렬

Q9. 문자열 압축

Q10. 자물쇠와 열쇠

Q11. 뱀

Q12. 기둥과 보 설치

Q13. 치킨 배달

Q14. 외벽 점검

2-1. 구현 개념 & 실전 문제

3-1. DFS/BFS 개념 & 실전 문제

0개의 댓글