[이것이 취업을 위한 코딩테스트이다 with 파이썬] Ch.12 구현 문제

📌한 장으로 보는 알고리즘

구현 
 - 머릿속에 있는 알고리즘 → 프로그램으로 작성
 - 간결하고 효율적으로 작성한 코드가 중요

완전 탐색과 시뮬레이션
 - 완점 탐색 : 모든 경우의 수를 빠짐없이 다 계산하는 해결방법
     → BFS/DFS 알고리즘 이용(반복,재귀 이용한 예외 케이스 모두 활용)
 - 시뮬레이션 : 문제에서 제시하는 논리, 동작 과정을 그대로 코드로 옮기는 것
 +) 원소를 나열하는 모든 경우의 수 : 순열, 조합 라이브러리 사용

---

📌Q.7) 럭키 스트레이트

 

✔️ 문제 유형

구현, 문자열

 

✔️ 문제

18406번: 럭키 스트레이트

 

✔️ 나의 문제풀이

n = input()

left_n = sum(list(map(int,n[:len(n)//2])))
right_n = sum(list(map(int,n[len(n)//2:])))

if left_n == right_n:
    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")

---

📌Q.8) 문자열 재정렬

 

✔️문제

입력 : 알파벳 대문자와 숫자(0~9)로만 구성된 문자열

모든 알파벳을 오름차순으로 정렬하여 이어서 출력 → 모든 숫자를 더한 값을 이어서 출력

 

✔️입력 조건

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

 

✔️출력 조건

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

 

✔️입출력 예시

 

✔️나의 문제풀이

s = input()

strings = []
nums = []

for w in s:
    if ord(w) > 57:
        strings.append(w)
    else:
        nums.append(int(w))

strings.sort()
num = str(sum(nums))

print(''.join(strings)+num)

 

✔️책의 문제풀이

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

 

✔️리뷰

 - 숫자 아스키코드 값 : 숫자0~9 → 48~57

 - x.isalpha() : 숫자가 str 형태로 들어가면 x.isalpha()는 False

---

📌Q.9) 문자열 압축

 

✔️문제

프로그래머스

 

✔️나의 문제풀이

- 시간 복잡도 줄이기 위해 len(s) // 2까지만 탐색

• 문자열을 잘라서 압축하기 때문에, 2번 반복이 최대이므로 len(s) // 2 까지
  (문자 8개면, 문자열 4개 단위로 자르는게 최대)

- 변수 설명

• cut : 자르는 단위로 하나씩 증가
• b : 자른 문자 저장.
  현재 문자와 b가 같으면 num 증가, 현재 문자와 b가 다르면 new_s에 입력

- 저장 안되는 마지막 글자는 for문 끝나고 따로 저장

def solution(s):
    answer = len(s)
    cut = 1
    
    while True:
        if (len(s)//2) < cut:
            return answer
        
        new_s = ''
        b = s[:cut]
        num = 1
        for i in range(cut,len(s),cut):
            if b == s[i:i+cut]:
                num += 1
            else:
                if num == 1:
                    new_s += b
                else:
                    new_s += (str(num) + b)
                b = s[i:i+cut]
                num = 1
        if num == 1:
            new_s += b
        else:
            new_s += (str(num) + b)
            
        cut += 1
        
        if answer > len(new_s):
            answer = len(new_s)
            
    return answer

 

 

✔️책의 문제풀이

- 입력 문자열 길이 1000이하 → 완전 탐색(모든 경우의 수 탐색)

- 아이디어  : 1~n/2까지의 모든 수를 단위로 하여 문자열을 압축하는 방법 모두 확인, 가장 짧게 압축되는 길이 출력

def solution(s):
    answer = len(s)
    
    for step in range(1, len(s)//2+1):
        compressed = ""
        prev = s[0:step]
        count = 1
        
        for j in range(step, len(s), step):
            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

 

✔️리뷰

- for문의 마지막 문자가 저장 안되었다면, for문 이후에 동일한 방법으로 저장

---

📌Q.10) 자물쇠와 열쇠

 

✔️문제

프로그래머스

 

✔️나의 문제풀이

X

 

✔️ 책의 문제풀이

  - 문제에서 제안하는 연산 : 자물쇠, 열쇠 크기가 20 * 20 보다 작음 →  400만큼의 연산

  - 아이디어 : 완전탐색을 이용하여 열쇠 이동, 회전 → 자물쇠에 끼워보는 작업 전부 시도

   (수월하게 탐색하기 위해 자물쇠 리스트 크기 3배 이상으로 변경)

• 열쇠 배열을 왼쪽 위 ~ 한 칸씩 이동하는 방향 → 자물쇠에 끼워보는 작업 전부 시도
• 자물쇠 리스트 + 열쇠 리스트 = 모든 값 정확히 1인지 확

# 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):   # 0~lock_length까지는 다 0이기 때문에 탐색 안 함
        for j in range(lock_length, lock_length * 2):
            if new_lock[i][j] != 1:
                return 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):    # n*2가 시작점이어야 i,j가 n*3에서 끝남
            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

 

✔️리뷰

- 다시 풀어보기

- 90도 회전 코드는 익혀두기

# 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

---

📌Q.11) 뱀

 

✔️문제 유형

구현, 자료 구조, 시뮬레이션, 덱, 큐

 

✔️문제

3190번: 뱀

 

✔️나의 문제풀이

- 정답

• 1행1열(1,1)을 time = 0으로 두고 시작
• 뱀 머리가 먼저 움직이고, 사과에 따라 꼬리가 움직임 → 현재 (x,y)를 먼저 넣고, 뱀 위치(deque) 확인하기

from collections import deque

n = int(input())
k = int(input())
apple = []
turn_t = []
turn_p = []

for _ in range(k):
    apple.append((list(map(int,input().split()))))

l = int(input())

for _ in range(l):
    x,c = map(str,input().split())
    turn_t.append(int(x))
    turn_p.append(c)


time = 0
x,y = 1,1   # n,n 인 경우 상황 종료
now_dir = 'E'
snake_pos = deque()
direction = ['N','E','S','W']
move = [(-1, 0), (0, 1), (1, 0), (0, -1)] # N, E, S, W 순서

# x == n이거나 y == n이거나 옮긴 위치가 snake_pos에 있는 경우
while True:
    # 현재 위치 넣기
    snake_pos.append((x,y))

    if x == 0 or x == n+1 or y == 0 or y == n+1:
        break

    time += 1
    x += move[direction.index(now_dir)][0]
    y += move[direction.index(now_dir)][1]

    # turn[0]의 시간이 같을 때, direction 바뀌는 것
    if time in turn_t:
        if turn_p[turn_t.index(time)] == 'D':
            num = direction.index(now_dir) + 1
            if num < 4:
                now_dir = direction[num]
            else:
                now_dir = direction[0]
        elif turn_p[turn_t.index(time)] == 'L':
            num = direction.index(now_dir) - 1
            if num >= 0:
                now_dir = direction[num]
            else:
                now_dir = direction[3]

    if (x,y) in snake_pos:
        break

    if [x,y] not in apple:
        snake_pos.popleft()
    elif [x,y] in apple:
        apple.remove([x,y])

print(time)

 

✔️책의 문제풀이

- 유형 : 시뮬레이션, 요구하는대로 실수 없이 구현

- 아이디어 : ① 특정 위치에서 동,서,남,북의 위치로 이동하는 기능 구현 ② 뱀이 존재하는 위치 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())

 

✔️리뷰

-  '게임이 시작할때 뱀은 맨위 맨좌측에 위치, 뱀은 매 초마다 이동' = 시간은 0초에서 시작

- '먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치' = '먼저' 이동 후, 사과의 위치에 따라 deque값 빠짐 여부 결정

- '게임 시작 시간으로부터 X초가 끝난 뒤, 방향 회전' 

→ 문제 제대로 읽기, 조건 하나하나 빠뜨리지 말기

---

📌Q.12) 기둥과 보 설치

 

✔️문제

프로그래머스

 

✔️나의 문제풀이

  - 19.2 (조금만 수정하면 답 나올거 같음)

def possible(answer, del_):
    answer.remove(del_)
    
    for x,y,a in answer:
        if a == 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
            else:
                return True
        
        elif a == 1:   # 보 확인
            if ([x,y-1,0] in answer) or ([x+1,y-1,0] in answer) or ((([x,y,1] and [x+1,y,1]) in answer) and (([x,y,1] and [x-1,y,1]) in answer)):
                continue
            else:
                return True
    return False
    
    

def solution(n, build_frame):
    answer = []
    
    for x,y,a,b in build_frame:
        if a == 0 and b == 1:   # 기둥 설치
            if (y == 0) or ([x-1,y,1] in answer) or ([x,y,1] in answer) or ([x,y-1,0] in answer):
                answer.append([x,y,a])
                
        elif (a == 0 and b == 0):     # 기둥 삭제 
            ans = possible(answer, [x,y,a])
            if ans == False and [x,y,a] in answer:
                answer.remove([x,y,a])
        
        if a == 1 and b == 1:   # 보 설치
            if ([x,y-1,0] in answer) or ([x+1,y-1,0] in answer) or ((([x,y,1] and [x+1,y,1]) in answer) and (([x,y,1] and [x-1,y,1]) in answer)):
                answer.append([x,y,a])
                
        elif (a == 1 and b == 0):  # 보 삭제
            ans = possible(answer, [x,y,a])
            if ans == False and [x,y,a] in answer:
                answer.remove([x,y,a])
            
        answer.sort(key = lambda x:(x[0],x[1],x[2]))
    return answer

 

- 통과

• possible에서 answer.remove는 연결되어 있어서 성립하지 않으면 다시 append해 주어야 함

def possible(answer, del_):
    answer.remove(del_)
    
    for x,y,a in answer:
        if a == 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
            else:
                return answer.append(del_)
        
        elif a == 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
            else:
                return answer.append(del_)
    return answer
    
    

def solution(n, build_frame):
    answer = []
    
    for x,y,a,b in build_frame:
        if a == 0 and b == 1:   # 기둥 설치
            if (y == 0) or ([x-1,y,1] in answer) or ([x,y,1] in answer) or ([x,y-1,0] in answer):
                answer.append([x,y,a])
                
        elif (a == 0 and b == 0):     # 기둥 삭제 
            possible(answer, [x,y,a])
        
        if a == 1 and b == 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):
                answer.append([x,y,a])
                
        elif (a == 1 and b == 0):  # 보 삭제
            possible(answer, [x,y,a])
            
        answer.sort(key = lambda x:(x[0],x[1],x[2]))
    return answer

 

✔️책의 문제풀이

- 아이디어 : 설치 및 삭제 연산을 요구할 때마다 일일이 '전체 구조물을 확인하며' 규칙을 확인

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
        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
    return True


def solution(n, build_frame):
    answer = []
    
    for frame in build_frame:
        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)

 

 

✔️리뷰

- 시간복잡도가 충분하다면 같은 방법으로 모두 탐색하기

- 다른 함수에서 answer.remove하면 본 함수에서도 지워짐,,,

---

📌Q.13) 치킨 배달

 

✔️문제 유형

구현, 브루트포스 알고리즘, 백트래킹

 

✔️문제

15686번: 치킨 배달

 

✔️ 나의 문제풀이

- 수정 전 

• 치킨집 기준, 거리가 같은 경우 어떤 것을 우선순위로 해야할까 고민 → 하단 코드로 수정하여 정답

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

for _ in range(n):
    city.append(list(map(int,input().split())))

house = []
chicken = []
distance = []
check = []
small = []
a = []
answer = 0

# 위치 넣어주기(집, 치킨집)
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append((i+1,j+1))
        elif city[i][j] == 2:
            chicken.append((i+1,j+1))

print(house)
print(chicken)
print()

# 도시 거리 넣어주기
for h_x, h_y in house:
    d = []
    for c_x, c_y in chicken:
        dist = abs(h_x-c_x) + abs(h_y-c_y)
        d.append(dist)
    distance.append(d)

print(distance)
print('ok')

# 오류 = 치킨집 기준 도시거리가 같으면, 어떤걸 우선순위에?....ㅠㅠㅠㅠ
# 치킨집 기준 도시거리
for j in range(len(distance[0])):
    choose = 0
    for i in range(len(distance)):
        choose += distance[i][j]
    check.append([j,choose])

check.sort(key = lambda x:x[1])
print(check)
print()

for i in range(m):
    small.append(check[i][0])

print(small)
print()

for i in range(len(distance)):
    ans = []
    for j in small:
        ans.append(distance[i][j])
    a.append(ans)

print(a)
print()

for k in range(len(a)):
    answer += min(a[k])

print(answer)

- 정답

• 집,치킨집 위치 넣기 / 계산된 도시 거리 넣기
• m개의 치킨집을 선택하기 위해 치킨집 개수에서 m개 선택하는 조합 이용 (combi)
• 조합으로 나온 인덱스로 모든 치킨거리 계산 (best_check)
• best_check 중 가장 작은 값을 정답 

from itertools import combinations

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

for _ in range(n):
    city.append(list(map(int,input().split())))

house = []
chicken = []
distance = []

answer  = []

# 위치 넣어주기(집, 치킨집)
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append((i+1,j+1))
        elif city[i][j] == 2:
            chicken.append((i+1,j+1))

# 도시 거리 넣어주기
for h_x, h_y in house:
    d = []
    for c_x, c_y in chicken:
        dist = abs(h_x-c_x) + abs(h_y-c_y)
        d.append(dist)
    distance.append(d)

# 치킨집 모든 경우의 수
combi = list(combinations([i for i in range(len(chicken))], m))

# m개의 모든 치킨집의 '치킨거리' 리턴
def best_check(distance,idx):
    small_num = 0

    for h in range(len(distance)):
        tmp = []
        for id in idx:
            tmp.append(distance[h][id])
        small_num += min(tmp)

    return small_num

# 선택한 치킨집의 '치킨거리' answer 저장
for idx in combi:
    num = best_check(distance,idx)
    answer.append(num)

print(min(answer))

 

✔️책의 문제풀이 

- 아이디어 : 조합(100,000으로 시간초과 안걸림)으로 모든 경우의 치킨 거리의 합 계산(완전탐색) → 치킨거리의 최솟값

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

# m개의 모든 치킨집의 '치킨거리' 리턴
def get_sum(candidates):
    result = 0

    # 모든 집에 대하여
    for hx,hy in house:
        # 가장 가까운 치킨집을 찾기
        temp = 1e9
        for cx, cy in candidates:
            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)

 

✔️리뷰

- 시간복잡도가 크지 않으면, 조합을 이용하여 완전탐색 생각해보기 

---

📌Q.14) 외벽 점검

 

✔️ 문제

프로그래머스

 

✔️ 나의 문제풀이

X

 

✔️ 책의 문제풀이

- 아이디어 : 완전탐색, 친구를 나열하는 모든 경우의 수를 각각 확인하여 친구를 최소 몇 명 배치하면 되는지 계산

• 원형으로 나열된 데이터 처리 → 길이를 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

 

✔️ 리뷰

- 원형으로 나열되는 데이터처리는 2배로 늘려서 생각하기

- 다시 풀어보기