02-6. 구현 복습

구현에는 완전 탐색 유형과 시뮬레이션 유형이 있다.
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.

이번주 구현 복습은 난이도가 좀 어렵게 느껴져 문제를 푸는 것을 목표로 하는 것이 아니라 코드를 이해하는 것을 목표로 했습니다..! 😥😥

---

📝문제1. 프로그래머스 60057번(문자열 압축)

- 문제

https://programmers.co.kr/learn/courses/30/lessons/60057

- 코드💻

def solution(s):
    least_length = len(s)
    temp = 0
    # 문자열의 길이를 반으로 자름
    # 길이의 반을 넘어서면 어차피 두 문자열로 나뉘기 때문.
    for i in range(1, len(s)//2 + 1):
        # zip 함수에 문자열, n 전달
        temp = zip(i, s)
        if temp < least_length:
            least_length = temp
        
    return least_length     
        

# 문자열을 n개 단위로 잘라 압축하고, 압축된 문자열의 길이를 반환해주는 함수
def zip(num, s):
    i = 0
    zip_list = []
    while True:
        if i+num > len(s):
            zip_list.append(s[i:])
            break
        else:
            zip_list.append(s[i:i+num])
        i = i+num
    
    my_zip = ""
    before = zip_list[0]
    count = 1
    for i in range(1, len(zip_list)):
        curr = zip_list[i]
        # 앞에 나온 것과 계속 같은 것이 나온다면 
        if curr == before:
            # 나온 횟수 저장
            count += 1
        # 앞에 나온 것과 다른 것이 나온다면
        # 저장된 횟수만큼 압축 문자열에 추가
        else:
            if count == 1:
                my_zip = my_zip + before
            else:
                my_zip = my_zip + str(count) + before
            count = 1
        before = curr
    my_zip = my_zip + before
        
    return len(my_zip)

---

📝문제2. 프로그래머스 60061번(기둥과 보 설치)

- 문제

https://programmers.co.kr/learn/courses/30/lessons/60061

- 코드💻

def isValid(answer):
    for x,y,a in answer:
        if a==0:
            if (x,y-1,0) in answer or (x-1,y,1) in answer or (x,y,1) in answer or y==0:
                continue
            else:
                return False
        if 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 False
    return True

def solution(n, build_frame):
    answer = set()
    for x,y,a,b in build_frame:
        if b==0:
            answer.remove((x,y,a))
            if not isValid(answer):
                answer.add((x,y,a))
        else:
            answer.add((x,y,a))
            if not isValid(answer):
                answer.remove((x,y,a))

    answer = [list(i) for i in answer]
    answer.sort(key=lambda x:(x[0],x[1],x[2]))
    return answer

---

📝문제3. 백준 3190번(뱀)

- 문제

https://www.acmicpc.net/problem/3190

- 코드💻

# 끝을 만났을 때는 die
# apple -> 몸길이 +1,
# (0,0)부터 시작

def Solution():
    time = 0
    # 북동남서
    snake_array = []
    direction = {0:(0,1), 1:(1,0),2:(0,-1),3:(-1,0)}
    dir = 0 # 동쪽

    # empty:0, 사과:1, 뱀:2
    nx,ny = 0,0
    board[0][0] = 2 # start
    snake_array.append([0,0])

    # 끝날때까지 돌기
    while(1):
        time += 1
        nx = nx + direction[dir][0]
        ny = ny + direction[dir][1]
  
        if not 0<= nx <N or not 0<= ny <N:
             break
	
    	# apple
        if board[nx][ny] == 1:
            board[nx][ny] = 2 # 머리 이동
            snake_array.append([nx,ny])

        # empty
        elif board[nx][ny] == 0:
            board[nx][ny] = 2
            snake_array.append([nx,ny])
            del_x, del_y = snake_array.pop(0)
            board[del_x][del_y] = 0

        # snake 몸통
        elif board[nx][ny] == 2:
            break

        if len(snake_dir) != 0 and time == snake_dir[0][0]:
                time, new_dir = snake_dir.pop(0)
                if new_dir == 'L': # 왼쪽
                    dir = (dir + 3) % 4
                elif new_dir == 'D':
                    dir = (dir + 1) % 4

    return time

# 오른쪽/ 왼쪽 방향 바꾸는 건 % 연산자 이용하여 쉽게 할 수 있음
# 왼쪽으로 돌리기 = (현재 방향 + 3) % 4
# 오른쪽으로 돌리기 = (현재 방향 + 1) % 4
# board
N = int(input())
board = [[0 for i in range(N)] for j in range(N)]

# apple 넣기
k = int(input())
apple_locs = []
for _ in range(k):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1

# snake 시간, 방향
l = int(input())
# (sec, c(left) or d(right))
snake_dir = list(map(lambda x:[int(x[0]),str(x[1])],\
                     [input().split() for _ in range(l)])) 
print(Solution())

---

📝문제4. 백준 15686번(치킨 배달)

- 문제

https://www.acmicpc.net/problem/15686

- 코드💻

from itertools import combinations

n,m=map(int, input().split())
maps=[]
for i in range(n):
  maps.append(list(map(int, input().split())))

home=[]
chicken=[]
for i in range(n):
  for j in range(n):
    if maps[i][j]==1:
      home.append((i,j))
    elif maps[i][j]==2:
      chicken.append((i,j))

pick_chicken=list(combinations(chicken,m))
result=[0]*len(pick_chicken)

for i in home:
  for j in range(len(pick_chicken)):
    a=100
    for k in pick_chicken[j]:
      temp=abs(i[0]-k[0])+abs(i[1]-k[1])
      a=min(a,temp)
    result[j]+=a

print(min(result))

---

📝문제5. 프로그래머스 60059번(자물쇠와 열쇠)

- 문제

https://programmers.co.kr/learn/courses/30/lessons/60059

- 코드💻

def attach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] += key[i][j]

def detach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] -= key[i][j]

def rotate90(arr):
    return list(zip(*arr[::-1]))

def check(board, M, N):
    for i in range(N):
        for j in range(N):
            if board[M+i][M+j] != 1:
                return False;
    return True

def solution(key, lock):
    M, N = len(key), len(lock)

    board = [[0] * (M*2 + N) for _ in range(M*2 + N)]
    # 자물쇠 중앙 배치
    for i in range(N):
        for j in range(N):
            board[M+i][M+j] = lock[i][j]

    rotated_key = key
    # 모든 방향 (4번 루프)
    for _ in range(4):
        rotated_key = rotate90(rotated_key)
        for x in range(1, M+N):
            for y in range(1, M+N):
                # 열쇠 넣어보기
                attach(x, y, M, rotated_key, board)
                # lock 가능 check
                if(check(board, M, N)):
                    return True
                # 열쇠 빼기
                detach(x, y, M, rotated_key, board)
                
    return False

---

📝문제6. 프로그래머스 60062번(외벽점검)

- 문제

https://programmers.co.kr/learn/courses/30/lessons/60062

- 코드💻

from itertools import permutations
def solution(n, weak, dist):
    L = len(weak)
    cand = []
    weak_point = weak + [w+n for w in weak]  # 선형으로

    for i, start in enumerate(weak):
        for friends in permutations(dist):  # 순열 이용
            count = 1
            position = start
            # 친구 조합 배치
            for friend in friends:
                position += friend
                # 끝 포인트까지 도달 못했을 때
                if position < weak_point[i+L-1]:
                    count += 1  # 친구 더 투입
                    # 현재 위치보다 멀리 있는 취약지점 중 가장 가까운 위치로
                    position = [w for w in weak_point[i+1:i+L]
                                if w > position][0]
                else:  # 끝 포인트까지 도달
                    cand.append(count)
                    break

    return min(cand) if cand else -1

---

사실 이 중 일부 문제들은 아직도 이해가 안가는 부분들이 있다.. 문자열 압축 문제와 치킨 문제만 그나마 제일 이해한듯,,!! 다행인지,, 불행인지,,,, 문제 자체가 이해가 잘 안가기도 하고, 정답 코드를 봐도 아직 알고리즘 문제에 서툴러 이해하기 쉽지 않다.. 다음주에는 좀 더 열심히 해야겠다!