손가락놀이터

문제 설명

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.

제한 조건

• 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
• 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
• 곱할 수 있는 배열만 주어집니다.

입출력 예

def solution(arr1, arr2):
    # 1번째 매트릭스의 row, col
    arr1_y, arr1_x = len(arr1), len(arr1[0])
    # 2번째 매트릭스의 row, col
    arr2_y, arr2_x = len(arr2), len(arr2[0])

    # 결과 매트릭스 생성
    answer = [[0] * arr2_x for _ in range(arr1_y)]

    # 1번째 매트릭스의 row
    for y_1 in range(arr1_y):
        # 2번째 매트릭스의 col
        for x_2 in range(arr2_x):

            # 1번째 매트릭스의 col == 2번째 매트릭스의 row
            for mul in range(arr1_x):

                answer[y_1][x_2] += arr1[y_1][mul] * arr2[mul][x_2]
    # 결과 매트릭스 return
    return answer

문제 후기

처음 피보나치 수라는 것을 보자마자 재귀를 생각해서 풀었습니다.

1차로 재귀만 사용하였을때 시간초과가 발생하여 2차로 재귀 + DP로 이전에 나온 값이 있는 경우 반복하지 않고 바로 사용하게 했습니다. 제출 결과로 다시 시간초과와 런타임에러가 발생했고 최대 입력값인 100,000을 입력해보니 maximum recursion depth exceeded 에러가 발생했습니다.

알고리즘을 다시 생각해보니 단순 O(n)으로 해결가능한 문제였습니다....😢

처음 문제 파악을 할 때 확실히 파악하는 것이 중요할꺼 같습니다. 문제파악을 더 잘해야겠습니다😂😂

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

* n은 1이상, 100000이하인 자연수입니다.

입출력 예

def solution(n):

    chk = 0     # 피보나치 홀수, 짝수 판별
    fibonacci_num1 = 1  # 피보나치 홀수 번째 값(1)
    fibonacci_num2 = 1  # 피보나치 짝수 번째 값(2)

    idx = 3     # 피보나치 3부터 시작
    
    # n 번째 까지 진행
    while idx < n+1:
        if idx % 2 == 1:    # 홀수 경우
            fibonacci_num1 += fibonacci_num2    # F(n) = F(n-1) + F(n-2)
            chk = 1     # 홀수 체크
        else:               # 짝수 경우
            fibonacci_num2 += fibonacci_num1    # F(n) = F(n-1) + F(n-2)
            chk = 0     # 짝수 체크
        idx += 1    # 숫자 증가


    if chk == 1:    # 홀수면 홀수 F(n)값 리턴
        return fibonacci_num1 % 1234567
    else:           # 짝수면 짝수 F(n)값 리턴
        return fibonacci_num2 % 1234567 
        
   
   
   
   # def fibonacci(num, num_dict):
#     if num in num_dict:
#         return num_dict[num], num_dict
#     # elif num < 2:

#     #     return num
#     else:
#         res2, num_dict = fibonacci(num - 2, num_dict)
#         num_dict[num - 2] = res2
#         res1, num_dict = fibonacci(num - 1, num_dict)
#         num_dict[num - 1] = res1
#
#
#         return res1 + res2, num_dict
#
# def solution(n):
#     num_dict = {0:0,1:1}
#     result, _ = fibonacci(n, num_dict)

#     return result % 1234567

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 두번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 첫번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예시

def solution(A,B):
    answer = 0
    
    A = sorted(A)   # 오름차순으로 정렬
    B = list(reversed(sorted(B)))   #  내림차순으로 정렬
    
    # index 별로 곱하여 더하기
    for idx in range(len(A)):
        answer += A[idx] * B[idx]

    return answer

문제 후기

처음에는 단순히 층에서 가장 높은 수, 그 중에서 위의 층과 다른 칸을 선택하려했습니다. 코드를 완성하고 확인해보니 실패가 나와 문제를 다시 읽고 DP라는 것을 깨달았습니다.

문제는 DP를 이용하는 것으로 같은 층의 값은 서로 영향을 미치지 않고 오직 위의 층 값에 영향을 받습니다. 따라서 층을 기준으로 DP를 작성했습니다.

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

def solution(land):

    # 2번째 층부터 시작하므로 1로 시작
    idx = 1

    # DP 시작
    while idx < len(land):
        # 4개의 숫자 확인.
        for num in range(len(land[idx])):
            chk = []    # 임의의 배열.
            for d_num in range(len(land[idx-1])):
                if num != d_num:
                    # 위의 칸과 다를 때, 위의 층과의 합.
                    chk.append(land[idx][num]+land[idx-1][d_num])
            # 해당 칸에서 나올 수 있는 가장 높은 값.
            land[idx][num] = max(chk)
        # 층수 + 1
        idx += 1
    return max(land[len(land)-1])

문제 후기

해당 문제를 처음 접하고 문자를 list형태로 변환하여 해결하려 했습니다. 완성한 결과 배열이 계속해서 for문을 통해 탐색을 하여 시간초과가 나왔습니다. 이후 변환을 하지 않고 문자열상태에서 count와 +-를 활용하여 해결했습니다.

문자열로 나오는 경우 먼저 문자열로 해결할 수 있는지 확인하거나 시간을 확인한 이후 배열로 해결해야겠습니다.

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 c를 2진법으로 표현한 문자열로 바꿉니다.

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 1이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

코드

def solution(s):

    change_transform = 0    # 변환 횟수
    remove_zero = 0         # 0 제거 횟수
    sentence = s            # input 값. 알고리즘 활용 문자

    # 2진수가 3자리 이상인 경우에 반복문 진행.
    while len(sentence) > 2:

        new_sentence = ""   # 변환한 문자
        chk_one = sentence.count("1")   # 1의 갯수, 다음 계산하는 이진수
        remove_zero += sentence.count("0")  # 제거한 0을 더해줌.
        len_next = chk_one  # 1의 갯수, 아래 while문에서 활용하는 변수

        # 1의 갯수를 다시 2진수로 변환. 
        while len_next > 1:

            new_sentence = str(len_next % 2) + new_sentence
            len_next = len_next // 2
        
        # 2진수가 3자리 이상인 경우 1을 추가.
        if chk_one != 2 and chk_one != 3:
            new_sentence = "1" + new_sentence
            change_transform += 1
        
        # 2진수가 "11" 인 경우 3번 변환과 0을 한번 제거
        elif chk_one == 3:
            change_transform += 3
            remove_zero += 1
            return [change_transform, remove_zero]
        
        # 2진수가 "10"인 경우 2번 변환과 0을 한번 제거
        else:
            change_transform += 2
            remove_zero += 1
            return [change_transform, remove_zero]

        sentence = new_sentence
    # 2진수가 "1"로 끝난 경우
    return [change_transform, remove_zero]

문제 후기

문제를 보고 가장 먼저 고민한 것은 15(1111)과 30(11110)과 같이 다음 오는 숫자가 자릿수가 증가하는 경우였습니다.

다른 것은 어떻게 하면 쉽게 숫자를 넘겨줄 수 있을까라는 생각을 했고 Queue와 배열을 고민하다 문제를 풀면서 queue의 의미가 없다고 생각하여 배열을 사용했습니다. 

해결 방식은 위에서부터 1인경우 pass하고 0이 나왔다면 0과 1의 자리를 바꾸고 뒤는 가장 작은 수를 배치하는 것입니다.

1001110 에서 1001110 -> 1010110로 바꾸고 뒤의 110은 가장 작은 수로 변경해야하므로 0의 갯수만큼 먼저 합치고, 그 이후 1을 합쳐서 1010011이 되는 방식입니다.

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

Python 코드

def solution(n):
    arr = [] # n을 2진수로 변환
    res = [] # n 다음 숫자의 2진수

    # n 숫자를 2진수로 변환
    while n >= 2:
        if n % 2 == 0:
            arr.append(0)
        else:
            arr.append(1)
        n = n // 2
    arr.append(1)



    tmp = [] # 임의의 배열
    zero, one = 0,0 #
    val = 1 #
    result = 0 # 결과값.

    # n의 2진수로부터 시작
    for idx in range(len(arr)-1):
        k = arr[idx]

        # 만약 해당 값이 1이고 그 다음 값이 0인 경우 서로 변경.
        if k == 1 and arr[idx+1] == 0:
            # zero와 one을 이용하여 바꾼 부분 뒤를 가장 작은 수로 만듬.
            for i in range(one):
                res.append(1)
            for j in range(zero):
                res.append(0)

            res.append(arr[idx+1]) # 1과 0을 서로 변경.
            res.append(1)

            # 나머지 부분을 합침.
            res.extend(arr[idx+2:])

            # 2진수 -> 10진수
            for x in res:
                result += val * x
                val *= 2
            return result

        # 바꾸기 전의 1의 갯수
        elif k == 1:
            one += 1

        # 바꾸기 전의 0의 갯수
        elif k == 0:
           zero += 1

    # 만약 위에서 return이 안된 경우, 더이상 바꾸는 것으로 증가 안되는 경우
    for j in range(one):
        tmp.append(1)
    for i in range(zero):
        tmp.append(0)

    # 2번째에 0을 추가하여 1의 갯수도 같으면서 다음 큰 수
    tmp.append(0)
    tmp.append(1)

    for x in tmp:
        result += val * x
        val *= 2
    return result

문제 요약

해당 문제는 2019 카카오 겨울 인턴쉽 코딩테스트 문제입니다.

집합의 크기 순으로 튜플을 정리하는 문제입니다. 먼저 문자열을 분리하여 배열형태로 변형을 하고 각 집합의 크기를 활용하여 정렬하고 차례대로 뽑아냅니다.

문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 5 이상 1,000,000 이하입니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
• 숫자가 0으로 시작하는 경우는 없습니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다

from itertools import chain

def solution(s):
    answer = [] # 결과값
    arr = []    # 문자를 배열로 변환

    k = []      # 숫자를 임시로 저장
    tmp = ""    # 숫자값


    # 문자 입력값을 배열로 변환
    for i in s:

        if i.isnumeric():   # 값이 숫자인지 확인하여 숫자값 저장
            tmp += i
        elif i == "," and tmp != "":    # 숫자값 배열에 입력
            k.append(int(tmp))
            tmp = ""
        elif i == "}"and tmp != "":     # } 값을 기준으로 집합 분리
            k.append(int(tmp))
            arr.append([len(k),k])      # 집합의 크기와 집합 저장

            tmp = ""
            k = []


    for x in sorted(arr):       # 집합의 크기로 정렬
        answer.append(x[1])
    answer = list(chain(*answer))   # 1차원 배열로 변형

    res = []
    for x in answer:
        if x not in res:
            res.append(x)

    return res

a = "{{2},{2,1},{2,1,3},{2,1,3,4}}"
print(solution(a))

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• ()() 또는 (())() 는 올바른 괄호입니다.
• )()( 또는 (()( 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

def solution(s):
    answer = True
    arr = list(str(s))
    chk = 0
    for x in arr:
        if x == "(":
            chk += 1
        else:
            chk -= 1
        if chk < 0:
            return False
    if chk != 0:
        return False

    return True