대기업 코딩테스트 준비 3 : 구현

python-for-coding-test/8.py at master · ndb796/python-for-coding-test (github.com)

ndb796/python-for-coding-test

구현

• 완전 탐색

  • 모든 경우 다 계산
    • DFS/BFS
    • itertools
      • 순열/조합

• 시뮬레이션

  • 문제에서 시키는 대로 한다

• 시간을 초로

  • column = int(ord(inputData[0]))-int(ord('a'))+1

• 방향

  • dx, dy
    • dxy = [(1,2),(2,1),(1,-2),(2,-1)]
  • 공간 제한
    • if 1<=nr<=8 and 1<=nc<=8:
    • 꼭 맵이 없어도 돤디.
      • 인덱스만으로 범위 제한

d = [ [0] * col for _ in range(row)]

• 글로벌 변수
  • 리스트는 상관 없음
  • 전역 변수는 global 선언 필요

direction = 3

def turn_left():
    global direction
    direction -=1
    if direction == -1:
        direction = 3

• 탐색
  • 꼭 필요한 자료 구조 찾기
  • 큐
    • 파이썬 큐는 디큐 쓰기
    • list(deque())
  • 스택
    • 리스트 활용
    • 재귀
      • 종료 조건 반드시 설정0
  • 반복 vs 재귀
    • 꼬리재귀가 더 간결함.

# 꼬리재귀가 더 간결함.
def fatorial(n):
    if n == 1:
        return n
    return factorial(n-1)* n
# dfs 재귀 스택. 가장 먼곳부너
def dfs(graph,v,visited):
    visited[v]=True # 방문 처리 여기에서
    for    (...) :
        if not visited[v]:
            dfs(graph,nextIndex,visited)
# bfs 큐, 가장 가까운 곳 부터. 
# 시작 노드 방문 처리
# 큐 넣기 전 방문 처리
def bfs(graph,v,visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[v]:
                queue.append(i)
                visited[i]=True

• 배열을 그래프로 모델링
  • 묶음 찾기

def dfs(x,y):
  if not 0<=x<=xLimit and 0<=y<=yLimit:
    return False 
    # 방문하지 않았다면
  if graph[x][y] == 0:
        graph[x][y] =1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
  return False

• 미로 탈출
  • bfs가 유리함
  • 한칸 한칸 전진하기 때문
    • guard 조건
      • 시작 점
      • 범위 조건
      • 방문 여부

실전 문제 풀이

1. 럭키 스트레이트

• 시뮬레이션
  • 시키는 대로 한다...

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")

2. 문자열 재정렬

• 시뮬레이션
  • 시키는 대로 한다...

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))

3.문자열 압축

• 시뮬레이션
  • 시키는 대로 한다...
  • 문자열 길이가 1000이하임
    • 1초 1억 이하...
    • 1초 2천만에서 1억 이하

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

4.자물쇠와 열쇠

시뮬레이션

• 시키는 대로 한다...

• ​ 완전 탐색을 수월하기 위해 자물쇠에 패딩을 대줌

from typing import *


# 2차원 리스트 90도 회전
def rotate_a_matrix_by_90_degree(arr: List[List[int]]):
    rowlen = len(arr)
    collen = len(arr[0])
    result = [[0] * collen for _ in range(rowlen)]
    for r in range(rowlen):
        for c in range(collen):
            result[c][rowlen - r - 1] = arr[r][c]
    return result


# 자물쇠 중간이 모두 1인지 확인
def check(new_lock: List[List[int]]):
    lock_length = len(new_lock) // 3
    for r in range(lock_length, lock_length * 2):
        for c in range(lock_length, lock_length * 2):
            if new_lock[r][c] != 1:
                return False
    return True


def solution(key, lock):
    lock_size = len(lock)
    key_size = len(key)
    # 자물쇠의 크기를 기존의 3배로 변환
    new_lock = [[0] * (lock_size * 3) for _ in range(lock_size * 3)]
    # 새로운 자물쇠 중앙 부분에 기존 자물쇠 삽입
    for r in range(lock_size):
        for c in range(lock_size):
            new_lock[r + lock_size][c + lock_size] = lock[r][c]

    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key)  # 열쇠 회전
        for row_of_lock in range(lock_size * 2):
            for col_of_lock in range(lock_size * 2):
                # 자물쇠에 열쇠를 끼워넣기
                for r in range(key_size):
                    for c in range(key_size):
                        new_lock[row_of_lock + r][col_of_lock + c] += key[r][c]
                # 자물쉐에 맞는지 검사
                if check(new_lock):
                    return True
                for r in range(key_size):
                    for c in range(key_size):
                        new_lock[row_of_lock + r][col_of_lock + c] -= key[r][c]
    return False

5.뱀

• 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝남
• 사과를 먹으면 몸이 늘어남
• 방형전환 L(왼) D(오른쪽)

매 시점 뱀의 위치를 항상 2차원 리스트에 기록

• 뱀의 전체 몸은 큐로 기록

뱀이 처음에 동쪽을 바라보고 있음

종이에 그림을 그려보기

• 8초에 벽에 닿아 게임 종료

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())

6. 기둥과 보 설치

- 기둥
  - 바닥 위 or
  - 보의 한쪽 위 or
  - 다른 기둥 위 or
- 보
  - 한쪽 끝이 기둥 or
  - 양쪽 끝이 다른  보와 동시 연결

- O(N^3)으로 모든 조건 확인

# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer: # x,y는 설치 교차점. 보는 오른쪽으로 기둥은 위쪽으로 설치. 가로, 세로
        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) # 정렬된 결과를 반환

7. 치킨 배달

• 치킨집을 줄여서 최대 M개
• M개의 치킨집까지의 거리를 줄이는 것
• 이후 도신의 치킨 거리의 최솟갑
  • 치킨집의 갯수 M<=치킨집의갯수<=13
  • 13Cm 조합

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)

8. 외벽 점검

• 주어지는 데이터가 적을 경우 완전 탐색
• 모든 친구 무작위 나열
• 원형을 길이 2배로 늘려 일자 형태

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