풍선 터뜨리기 - 프로그래머스

풍선 터뜨리기 - 프로그래머스

• 풍선이 끝까지 남기 위해서는 이 풍선보다 작은 풍선이 없거나, 풍선의 왼쪽 오른쪽에 해당 풍선보다 큰 풍선이 존재해야함.
• 반대로 생각했을 때 양끝에서 시작했을 때 자기보다 작은 숫자의 풍선이 있다면 해당 풍선은 남을 수 있는 풍선
• 위와 같이 생각했을 때 양쪽 끝값은 무조건 남길 수 있다.
• 즉, left와 right는 자기보다 작은 숫자가 나타날 때 갱신됨
• 남는 풍선 = left에 갱신된 횟수 + right에 갱신된 횟수 + 양끝값 개수(2) - 1(중복일 경우)

def solution(a):
    ret = 2
    if 0 <= len(a) <= 2:
        return len(a)
    left = a[0]
    right = a[-1]

    for i in range(1, len(a) - 1):
        if left > a[i]:
            left = a[i]
            ret += 1
        if right > a[-1 - i]:
            right = a[-1 - i]
            ret += 1
    if left == right:
        return ret - 1
    else:
        return ret

삼각 달팽이 - 프로그래머스

삼각 달팽이 - 프로그래머스

def solution(n):

    li = [[0] * n for _ in range(n)]

    ret = []

    x, y = -1, 0

    num = 1

    for i in range(n):

        for j in range(i, n):

            if i % 3 == 0:

                x += 1

            elif i % 3 == 1:

                y += 1

            elif i % 3 == 2:

                x -= 1

                y -= 1

            li[x][y] = num

            num += 1

    for i in li:

        for j in i:

            if j != 0:

                ret.append(j)

    return ret

프렌즈4블록 - 프로그래머스

프렌즈4블록 - 프로그래머스

def dfs(m, n, a):
    global cnt, flag
    li = []
    d = dict()
    for i in range(m - 1):
        for j in range(n - 1):
            if a[i][j] == '0': # 비어 있는 칸이면 pass
                continue
            if a[i][j] == a[i + 1][j] == a[i][j + 1] == a[i + 1][j + 1]: # 2 x 2 블록의 모양이 모두 같다면
                li += [(i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)]
    if not li: # 같은 블록이 하나도 존재하지 않는다면 재귀함수 탈출
        flag = True
        return
    s = set(li)
    cnt += len(s)
    for ele in s:
        d[ele[1]] = d.get(ele[1], []) + [ele[0]] # 열 별로 사라지는 블록의 index를 넣어둠

    tmp_a = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            tmp_a[j][i] = a[i][j]  # 행-열을 열-행 배열로 전환 

    tmp = [i for i in range(m)]
    # 같은 블록 지우고 떨어뜨리기
    for k in d: 
        ret = ""
        ts = "".join(tmp_a[k])
        remain = set(tmp) - set(d[k])
        for r in remain:
            ret += ts[r]
        tcnt = len(tmp) - len(ret)
        ret = '0' * tcnt + ret
        tmp_a[k] = list(ret)

    for i in range(m):
        for j in range(n):
            a[i][j] = tmp_a[j][i]
    if not flag:
        dfs(m, n, a)

cnt = 0
flag = False
def solution(m, n, board):
    a = [list(i) for i in board]
    dfs(m, n, a)
    return cnt