20200404 알고리즘

1. 비밀지도

출처: https://programmers.co.kr/learn/courses/30/lessons/17681

Solution

def convertPrime(origin, target, n):
    for idx, v in enumerate(origin):
        i = 0
        while v > 0:
            target[idx][n-1-i] = v % 2
            v //= 2
            i += 1
    return target
            

def solution(n, arr1, arr2):
    a1 = [[0] * n for _ in range(n)]
    a2 = [[0] * n for _ in range(n)]
    
    a1 = convertPrime(arr1, a1, n)
    a2 = convertPrime(arr2, a2, n)
    answer = [''] * n
    for y in range(n):
        for x in range(n):
            if a1[y][x] == 1 or a2[y][x] == 1:
                answer[y] += '#'
            else:
                answer[y] += ' '
    return answer

bin 내장 함수를 이용하여 2진수를 구할 수 도 있다.

a = 30
b = bin(a)[2:]

2. 카펫

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown	red	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

출처

Solution

def solution(brown, red):
    for i in range(1, red+1):
        if red % i == 0:
            if 2 * (red // i + i) == brown -4:
                return [red//i+2, i+2]

3. 프렌즈 4블록

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

board map 만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

board map

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

board map

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다. board map

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
2 ≦ n, m ≦ 30
board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

m	n	board	answer
4	5	[CCBDE, AAADE, AAABF, CCBBF]	14
6	6	[TTTANT, RRFACC, RRRFCC, TRRRAA, TTMMMF, TMMTTJ]	15

예제에 대한 설명

입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

Solution

def solution(m, n, board):
    board = list(map(list, board))
    dx = [1, 1, 0]
    dy = [0, 1, 1]
    answer = 0
    cnt = 0
    while True:
        ch = [[0] * n for _ in range(m)]
        for y in range(m):
            for x in range(n):
                for k in range(3):
                    xx = x + dx[k]
                    yy = y + dy[k]
                    if board[y][x] == -1 or xx >= n or yy >= m or board[y][x] != board[y + dy[k]][x + dx[k]]:
                        break
                else:
                    if ch[y][x] == 0:
                        ch[y][x] = 1
                        cnt += 1
                    for k in range(3):
                        if ch[y + dy[k]][x + dx[k]] == 0:
                            ch[y + dy[k]][x + dx[k]] = 1
                            cnt += 1
        if cnt == 0:
            break
        answer += cnt
        cnt = 0

        #delete
        for y in range(m):
            for x in range(n):
                if ch[y][x] == 1:
                    now = y # 현재 처리 값
                    before = now - 1 # 위에 값
                    while before >= 0 and board[before][x] != -1:
                        board[now][x] = board[before][x]
                        now -= 1
                        before -= 1

                    board[now][x] = -1
                    
    return answer

Written by@[HongDongUk]

공부한 것을 소소하게 적는 블로그.

GitHub Facebook