손가락놀이터

문제 후기

처음에는 단순히 층에서 가장 높은 수, 그 중에서 위의 층과 다른 칸을 선택하려했습니다. 코드를 완성하고 확인해보니 실패가 나와 문제를 다시 읽고 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))