그냥 코딩하는 사람의 블로그

문제 설명

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

풀이 과정

1. K가 1일때부터 쭉 나열해 본다.

   K	값
   0	A
   1	B
   2	BA
   3	BAB
   4	BABBA
   5	BABBABAB
   6	BABBABABBABBA

2. 나열해 보면.. K가 n일때는 n-1일때의 값과 n-2일때의 값을 합쳐주었다는 것을 볼 수 있다.

3. 따라서, a의 개수를 세는 dp_a, b의 개수를 세는 dp_b를 선언해 두고,

   • dp_a[n] = dp_a[n-1] + dp_a[n-2]
   • dp_b[n] = dp_b[n-1] + dp_b[n-2]
   • dp_a[0~1] = [1, 0]
   • dp_b[0~1] = [0, 1]

4. 각각의 dp[n]을 리턴해주면 된다.

소스 코드

import sys
n = int(sys.stdin.readline().rstrip())

dp_a = [0] * (n+1)
dp_b = [0] * (n+1)

dp_a[0] = 1
dp_b[0] = 0
dp_a[1] = 0
dp_b[1] = 1

for i in range(2, n+1):
    dp_a[i] = dp_a[i-1] + dp_a[i-2]
    dp_b[i] = dp_b[i-1] + dp_b[i-2]

print(dp_a[n], dp_b[n])

풀이 과정

1. 현재 자리수가 맨 앞자리라고 할때, 뒷자리 가능한 경우의 수는 (n-1)!이다.
   • 따라서, 맨 앞자리가 1일때는 0(n-1)!, 맨 앞자리가 2일때는 (n-1)!(n-2)!, ... 의 범위를 갖게 된다.
2. 따라서, 맨 앞자리부터 범위를 구한다.
   • 해당 범위라면, 현재 남아있는 경우의 수에서
     1. 범위의 최솟값을 빼주고
     2. 사용 가능한 숫자 리스트에서 제거
     3. 범위 조정
   • 범위를 조정하는 방식은 (n-1)!에서 (n-1)을 나누어주어 (n-2)!로 만들어 준다.
   • 해당 범위가 아니라면, 범위를 조정해가면서 검사한다.
3. 매 순간 범위에 해당하는 경우를 answer에 넣어주면 된다.

소스 코드

def solution(n, k):
    answer = []
    candidate = list(i+1 for i in range(n))
    # 맨 앞자리가 고정되었을때 뒷자리 가능한 경우의 수
    p = factorial(n-1) 
    div = n-1

    while div >= 0:
        fr = 0
        to = p
        for idx in range(len(candidate)):
            if fr <= k and k <= to: 
                # 현재 범위 내에 들어가는 경우
                answer.append(candidate[idx])
                # 현재 범위의 최솟값을 빼줌
                k = k - fr
                if div != 0:
                    # 맨 앞자리가 무엇이 나오는지 알음. 
                    # 따라서 다음 자리를 구해야 하므로 n-1자리를 검사했다면
                    # factorial의 결괏값에 n-1을 나누어주면 n-2!이 나옴.
                    p = p // div 
                # 자리수 조정
                div -= 1 
                del candidate[idx] # 현재 사용된 숫자는 지워줌.
                break
            else: 
                # 현재 범위 내에 들어가지 않으면 다음 범위
                fr = fr + p
                to = to + p

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 곱이 최대가 되려면 집합의 모든 수가 비슷한 값을 가질때가 최대이다
   • 예시) n = 3, s = 9라면, (3, 3, 3)이 최대값
2. 따라서.. s를 n으로 나눈 값들을 넣어 주고, 나머지값은 n+1을 넣어서 채워준다.
   • 즉, s//n을 (n - (s % n))개 넣어주고, (s//n)+1을 (s % n)개 넣어주면 된다.
3. 결과값을 오름차순으로 정렬해준다.

소스 코드

def solution(n, s):
    answer = []
    temp = s // n
    p = s

    if temp == 0:
        return [-1]

    if s % n == 0:
        answer = [temp] * n
    else:
        answer = [temp + 1] * (s % n) + [temp] * (n - (s % n))

    answer.sort()
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. works를 내림차순으로 정렬한다(작업량 순)
2. 거듭제곱의 합을 최소로 하려면 가장 큰 작업량부터 줄여야 한다.
   • 따라서, 가장 큰 작업량을 기준으로 1씩 빼주면서.
   • 각 작업들을 루프돌면서 현재 작업량보다 크다면 1을 빼주고, 작다면 바로 종료(내림차순으로 정렬하였으므로 아래는 모두 작음), 평탄화한다고 생각하면 됨.
   • 이 과정을 총 빼준 값이 n이 될때까지 하면 된다.

     

3. answer 전체를 제곱후 더하면 된다.

소스 코드

from collections import deque

def solution(n, works):
    answer = 0
    cut = 0
    flag = False
    works.sort(reverse=True)
    m_height = works[0]
    for height in range(m_height, 0, -1): 
    # 작업량을 높이로 두고 한층씩 잘라가면서 생각
        for i in range(len(works)):
            if works[i] == height:
                cut += 1
                works[i] -= 1
                if cut == n: # n개 자르면 종료
                    flag = True
                    break
            else: 
                # 내림차순 정렬했으므로 높이보다 작아지면 바로 break
                break
        if flag:
            break

    for work in works:
        answer += work * work

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 현재 위치가 이미 설치된 기지국 내에 있는지 검사.
   • 있다면, 현재 위치를 설치된 기지국 밖으로 바로 점프
2. 현재 위치가 기지국 내에 있지 않다면
   • 현재 위치를 기지국의 가장 마지막 자리라고 생각하고 기지국 배치
   • w가 2라고 가정할때
   • ■□★□□ => 현재 위치가 검은상자일때 별표에 기지국을 설치한다고 생각한다.
   • 다음 위치는 현재 위치 + 2 * w + 1이 된다.

소스 코드

from collections import deque

def solution(n, stations, w):
    answer = 0
    stations = deque(stations)
    x = 1
    while x <= n:
        # deque에 없는 경우 도달 불가능한 큰 수로 임의 설정
        range_x1, range_x2 = int(10e9), int(10e9)
        if stations:
            range_x1 = stations[0]-w
            range_x2 = stations[0]+w
        if x >= range_x1 and x <= range_x2:
        # 이미 설치된 기지국 안에 있는 경우, 기지국 밖으로 점프시켜줌.
            x = range_x2 + 1
            stations.popleft()
        else: # 현재 위치에 기지국 놓아야 하는 경우
            answer += 1
            # 현재 위치가 기지국의 가장 왼쪽에 닿았을 때, 다음 위치는 2 * w + 1칸 뒤다.
            x = x + (2 * w + 1) 
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 트리를 만들어주어야 하는 문제이므로 트리를 구성할 노드 class 정의
2. 모든 노드에 인덱스 달아준 다음, 모든 노드의 좌표를 y 좌표 기준 내림차순으로 정렬
3. 가장 y좌표가 큰 케이스를 루트 노드로 지정
4. 이제 y좌표 순으로 트리에 삽입
   • 삽입하려는 노드의 x좌표가 현재 노드의 x좌표보다 작다면 왼쪽 이동
   • 삽입하려는 노드의 x좌표가 현재 노드의 x좌표보다 크다면 오른쪽 이동
   • 이동 하다가 현재 노드의 left/right가 None이라면 삽입
5. 전위순회 / 후위순회를 recursion으로 구현

트리 만드는거 연습이 필요함.. 어렵게 구현

소스 코드

import sys

sys.setrecursionlimit(10**6)

class tree:
    def __init__(self, element):
        self.left = None
        self.right = None
        self.element = element

def tree_push(root, node):
    # X좌표 비교
    if root == None:
        root = node

    if root.element[0] > node.element[0]:
        if root.left == None:
            root.left = node
        else:
            tree_push(root.left, node)

    elif root.element[0] < node.element[0]:
        if root.right == None:
            root.right = node
        else:
            tree_push(root.right, node)

def preorder(node, answer):
    if node == None:
        return
    answer.append(node.element[2])
    preorder(node.left, answer)
    preorder(node.right, answer)

def postorder(node, answer):
    if node == None:
        return
    postorder(node.left, answer)
    postorder(node.right, answer)
    answer.append(node.element[2])


def solution(nodeinfo):
    answer = [[], []]
    for idx, node in enumerate(nodeinfo):
        node.append(idx+1)
    nodeinfo.sort(key=lambda x:(-x[1], x[0]))

    root = tree(nodeinfo[0])
    for i in range(1, len(nodeinfo)):
        temp = tree(nodeinfo[i])
        tree_push(root, temp)

    preorder(root, answer[0])
    postorder(root, answer[1])
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 최소 히프, 최대 히프를 둔다.
2. 데이터 삽입 시 최소히프, 최대히프에 모두 저장하면서 동시에 index도 같이 둔다.
3. 데이터 삭제
   • 최솟값 삭제하는 경우에는 최소히프에서 삭제 및 index 저장
   • 최댓값 삭제하는 경우에는 최대히프에서 삭제 및 index 저장
   • 삭제하기 전에 히프에서 이미 삭제된 index인지 검사하는 과정 추가
4. 히프가 비어있다면 [0, 0]을, 히프가 비어있지 않다면 [최대히프의 맨 위, 최소히프의 맨 위] 출력

소스 코드

import heapq
def solution(operations):
    answer = []
    max_heap = []
    min_heap = []
    remove_set = set()
    index = 0
    for op in operations:
        temp = op.split()
        operation = temp[0]
        number = int(temp[1])
        if operation == 'I':
            heapq.heappush(min_heap, [number, index])
            heapq.heappush(max_heap, [-number, index])
            index += 1
        elif operation == 'D':
            if number == -1:
                while min_heap:
                    number, idx = heapq.heappop(min_heap)
                    if idx not in remove_set:
                        remove_set.add(idx)
                        break

            elif number == 1:
                while max_heap:
                    number, idx = heapq.heappop(max_heap)
                    if idx not in remove_set:
                        remove_set.add(idx)
                        break

    while min_heap:
        if min_heap[0][1] in remove_set:
            heapq.heappop(min_heap)
        else:
            break

    while max_heap:
        if max_heap[0][1] in remove_set:
            heapq.heappop(max_heap)
        else:
            break

    if len(min_heap) == 0:
        return [0, 0]
    else:
        return [-max_heap[0][0], min_heap[0][0]]
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

• 너무 어려워서 다른 사람들이 풀이한 것들을 참고함.. 동적 계획법이 약함.

풀이 과정

1. 각 단계에서 나올수 있는 수를 따로 table에 저장해 둠.
2. 현재 단계로 도달할 수 있는 모든 케이스에 대하여 set으로 저장한 후 table에 저장
   • 현재 단계가 4단계라면, 1단계 + 3단계, 2단계 + 2단계, 3단계 + 1단계로 4단계로 도달 가능하다.
   • 각각의 케이스에 대해 덧셈, 뺄셈, 곱셈, 나눗셈 검사
3. 현재 단계에서 number이 있는지 검사하고 있다면 바로 return

소스 코드

from collections import deque

def solution(N, number):
    answer = -1
    table = []
    for i in range(1, 9):
        middle_set = set()
        middle_set.add(int(str(N) * i)) # 쭉 붙인거는 따로 추가
        for j in range(0, i-1):
            for k in table[j]:
                for l in table[-j-1]:
                    middle_set.add(k + l)
                    middle_set.add(k - l)
                    middle_set.add(k * l)
                    if l != 0:
                        middle_set.add(k // l)
        if number in middle_set:
            return i
        table.append(middle_set)


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 현재 위치를 도달하기 위해서는 n-1cm에서 1cm 뛰거나 n-2cm에서 2cm 뛰어야 함.
   • 따라서, dp[i] = dp[i-1] + dp[i-2]
2. 위 과정을 1~n까지 아래에서 위로 진행하면 된다.
3. dp[n] 리턴

소스 코드

    def solution(n):
    answer = 0
    dp = [1] + [0] * n
    for i in range(1, n+1):
        if i-1 >= 0:
            dp[i] += dp[i-1]
        if i-2 >= 0:
            dp[i] += dp[i-2]
    answer = dp[n] % 1234567

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. DP를 사용하는 문제일 거 같아서 처음에는 현재 금액 기준으로 도달할 수 있는 모든 경우의 수를 계산하였음.
   • dp[i] = dp[i] + dp[i-coin[j]] if (i - coin[j] >= 0)
   • dp[0] = 0
2. 위와 같은 방법으로 하게 되면 중복에 대한 처리가 전혀 되지 않아서 안되는 것 같았음.
   • (1, 2, 2)랑 (2, 1, 1)은 같은 방법
3. 고민하다 다른 사람들의 풀이를 보니 동전별로 dp 적용
   • 동전 단위로 DP 적용
   • dp[i] = dp[i] + dp[coin], 루프를 돌면서 하나의 동전만
4. 위처럼 하면 항상 새로운 방식으로만 개수가 세어짐.
   • 4라고 가정하고, 동전이 (1,2,4)일 때 위 방식으로 한다면..
   • 1, 1, 1, 1
   • 1, 1, 2
   • 2, 2
   • 4

소스 코드

    def solution(n, money):
    answer = 0

    dp = [0] * (n+1)
    dp[0] = 1

    for m in money:
        for i in range(1, n+1):
            if i - m >= 0:
                dp[i] += dp[i-m]
            print(dp, m)
    answer = dp[n] % 1000000007

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges