문제 출처: 프로그래머스

문제 설명

🔎 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

시간을 고려해야 한다는 점을 제외하고는 그렇게 어려운 문제는 아니었다. 또 팰린드롬이라는 주제는 이미 다른 문제들에서도 많이 다뤘기 때문에 접근도 어렵지 않았다. 사실 문자열의 길이를 줄인다면 더 낮은 레벨을 부여 받지 않았을까 생각이 드는 문제였다.

문제를 푸는데 한 두번 밖에 시행착오를 겪지 않았지만, 다른 사람들의 풀이를 보니 내 풀이가 최적의 풀이는 아니었다.

<정답 코드>

def solution(s):
    answer = 1
    n = len(s)
    
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
            	mid = (i+j) // 2
                aft = s[j:mid:-1]
                if (i+j) % 2 == 0:
                    pre = s[i:mid]
                else: 
                    pre = s[i:mid+1]
                    
                if pre == aft:
                    answer = max(answer, j-i+1)
                        

    return answer

접근은 아래와 같다.

1. S를 구성하는 모든 문자를 점검하면서 현재 값과 같은 값을 가지는 위치를 모두 찾은 다음 비교한다.
2. 문자열을 비교할 때는 split된 문자열의 길이가 짝수일 때와 홀수일 때가 다르다.
   1. 홀수일 때는 중앙값을 제외한 나머지가 대칭을 이루면 팰린드롬이다.
   2. 짝수일 때는 중앙값이 없으므로 전체가 대칭을 이루면 팰린드롬이다.
3.  가장 큰 값을 answer로 업데이트한다. 가장 짧은 팰린드롬의 길이는 한 단어 (ex. 'a')이므로 최소값이 1이 출력될 수 있도록 수정해야한다.

시행착오 부분은 처음에 팰린드롬은 길이가 홀수여야한다는 착각과, 최소 길이가 1이라는 점을 망각했기에 틀린 답을 제출했었다. 이 부분만 제거하니 문제는 풀렸다.

다만 제출된  답안의 실행시간이 1647ms로 크게 나왔다는 점이 살짝 걸렸다.

다른 사람들의 풀이를 살펴보니 DP로 접근한 사람도 있고, early stop 조건을 삽입한 사람도 있었다. 다양한 풀이가 있는 만큼 내 코드도 개선될 부분이 있을거라 생각한다.

문제 출처: 프로그래머스

문제 설명

처음 열었을 때 아 그냥 문자열 파싱 문제인가 생각했지만 생각보다 까다로운 구현과정이 내포된 문제였다.

정말 다행스럽게도 연산자가 3개 밖에 없고, 문자열의 길이도 100이 제한이었기 때문에 시간 복잡도를 고려하지 않고 문제를 풀어나갔다.

<정답 코드>

from itertools import permutations
from collections import deque


def ex_split(ex):
    reg = []
    tmp = ''
    for i in ex:
        if i.isdigit():
            tmp += i
        else:
            reg.append(int(tmp))
            reg.append(i)
            tmp = ''

    if tmp:
        reg.append(int(tmp))
    return reg


def solution(expression):
    answer = 0
    expression = ex_split(expression)

    for case in permutations(['+', '-', '*'], 3):
        temp = deque(expression)
        for operator in case:
            ans = deque()
            while len(temp):
                cur = temp.popleft()

                if cur == operator:
                    a = ans.pop()
                    b = temp.popleft()
                    ans.append(eval(str(a)+cur+str(b)))
                else:
                    ans.append(cur)

            temp = ans

        answer = max(abs(temp[0]), answer)

    return answer

피연산자와 연산자를 구분하고 연산 자체도 구현해야하는 번거로운 문제였기에 코드도 조금 길어졌다.

접근은 아래와 같다.

1. 인자로 받은 expression 식을 숫자와 연산자로 구분한다.
2. permutation을 이용해 연산자의 계산 순서를 정의한다.
3. 하나의 연산자 순서를 순회하면서 해당 연산자가 존재하는 양옆을 연산하며 전체를 순회한다.
4. 최대값을 갱신한다.

eval을 통해서 문자열 수식을 간단하게 계산할 수 있는 점이 좋았다.

다른 사람들을 보니, 문자열 포맷팅을 통해 간단히 구현한 사람도 있고 regex를 활용해 간단히 푼 사람도 있었다. 코드를 참조해서 발전해보도록 하자..

문제 출처: 프로그래머스

문제 설명

🔎[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
N x M 크기의 행렬 모양의 게임 맵이 있습니다.
이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다.
적은 이 건물들을 공격하여 파괴하려고 합니다.
건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다.
반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.

예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

이 문제는 22년도 카카오 블라인드 채용 당시 직접 경험했던 문제다.

당시에는 갑작스러운 취업 준비로 인해 1주일 정도 밖에 공부하지 못했었고, 그래프 탐색, 최단경로, 누적합 등의 개념을 몰랐기에 전체 배열을 탐색하는 방법으로 밖에 시도해보지 못했다.

그리고 채용과정에 불합격한 후에 꾸준하게 코딩 테스트를 준비하다가 다시 만나게 되었다.

처음에는 이 전과 같이 2차원 배열을 skill 하나씩 탐색하며 board를 탐색하는 브루트포스 코드를 작성했었다.

(그리고 마치 맞춘것 마냥 이 문제가 level 3이 맞나 생각했었다.)

아주 순조롭게 정확성 테스트 케이스를 전부 통과하고..

효율성 테스트 케이스를 전부 시간초과 해버렸다..

<틀린 코드 보기>

def solution(board, skill):
    answer = len(board) * len(board[0])

    for s in skill:
        if s[0] == 1:
            for i in range(s[1], s[3]+1):
                for j in range(s[2], s[4]+1):
                    flag = board[i][j] > 0 #원래는 정상적인 건물
                    board[i][j] -= s[5]
                    if flag and board[i][j] <= 0: # 공격받고 파괴되었는가 검사
                        answer -= 1
        else:
            for i in range(s[1], s[3]+1):
                for j in range(s[2], s[4]+1):
                    flag = board[i][j] <= 0 #원래 파괴된 건물
                    board[i][j] += s[5]
                    if flag and board[i][j] > 0: #회복받고 복구되었는가 검사
                        answer += 1
        
    
    return answer

제한 조건 중에 

• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000

라는 조건이 있었기에 board 전체를 한번 더 탐색하지 않고 flag를 통해 접근하려는 앙큼한 생각이었지만, 문제는 skill 안에 있었다.

극단적인 예시로 board가 1,000*1,000일 때 skill의 길이가 최대인 250,000이고, 모든 skill의 원소가 항상 board 전체 범위를 타격할 때, 1,000*1,000의 범위를 250,000번이나 반복해서 연산하게 되므로 시간초과가 발생했다.

(시간 복잡도 O(N * M * K))

사실 처음에는 해결 방법을 찾지 못하고 열심히 서핑하였다.

그러다 카카오 팀에서 직접 밝힌 접근법에서 O(K + N * M)의 시간에 문제를 풀 수 있다고 했고, 그 방법의 중심에는 '누적합'의 개념이 있었다.

(카카오 팀의 접근법 링크)

(누적합 개념 링크)

이 전까지는 한번도 사용해보지 않았던 알고리즘이라 생소하기도 하고 설명을 보아도 무슨 말인지 정확하게 이해 못하고 이게 왜 더 빠르지? 라는 의문도 가졌었다.

하지만 직접 작성해보고 테스트를 진행해보니 점차 이해가 갔고 결국에는 정답을 맞출 수 있었다.

<정답 코드>

def solution(board, skill):
    answer = 0
    tmp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
    
    for type, r1, c1, r2, c2, degree in skill:
        tmp[r1][c1] += degree if type == 2 else -degree
        tmp[r1][c2 + 1] += -degree if type == 2 else degree
        tmp[r2 + 1][c1] += -degree if type == 2 else degree
        tmp[r2 + 1][c2 + 1] += degree if type == 2 else -degree

    for x in range(len(tmp) - 1):
        for y in range(len(tmp[0]) - 1):
            tmp[x][y + 1] += tmp[x][y]

    for y in range(len(tmp[0]) - 1):
        for x in range(len(tmp) - 1):
            tmp[x + 1][y] += tmp[x][y]

    for x in range(len(board)):
        for y in range(len(board[0])):
            board[x][y] += tmp[x][y]
            if board[x][y] > 0: 
                answer += 1
                
    return answer

작성된 코드에 반복문이 너무 많이 보여 지저분하고 더 복잡해 보일 수 있지만, 해당 코드를 통해 문제를 접근하게 되면 항상 board 전체를 2번만 순회하게 되면 정답을 도출할 수 있다.

접근 방법은 아래와 같다.

1. board보다 행,열로 한 칸씩 더 큰 2차원 누적합 기록 배열을 생성한다.
2. skill을 순회하면서 하나의 skill이 나타내는 사각형의 꼭짓점(우측과 하단으론 한칸씩 더 증가시킨다)에 degree를 기록한다. (자세한 것은 누적합의 개념을 숙지해야 이해할 수 있다.)
3. 기록된 누적합 배열의 행, 열 기준으로 누적합을 계산한다.
4. 누적합 배열과 기존 board를 더해주면서 파괴되지 않은 건물의 수를 계산한다. 

문제를 푸는 것에만 집중하면 쉬워보일 수 있는 문제였으나, 효율성을 고려하게 되면서 굉장히 어려워졌던 문제이다.

그리고 누적합의 설명은 보통 1차원 배열을 예시로 들기 때문에 개념을 이해하는데 어려움이 있었다.

그래도 고생 끝에 문제를 해결했기 때문에 오래 기억에 남을 것 같다.

내가 이해한 2차원 누적합 개념 간단 설명

기존 배열이 5*5라고 가정하고 진행한다.

그렇게 되면 누적합 배열은 6*6이 되고 최초의 모습은 아래 사진과 같다.

이 상태에서 [0, 0]과 [1, 1]의 사각형이 들어왔다고 하자. 그렇다면 우리는 아래와 같이 기록해야한다.

우리가 원하는 것은 [0, 0]부터 [1, 1]까지 전부 1이 되는 그림이기 때문에 이렇게 기록해야 한다.

바로 누적합을 계산해서 결과를 확인해보자.

처음에는 행을 기준으로 누적합을 진행한다.

행을 기준으로 j+1번째 칸의 값이 현재 값에 j번째 칸의 값을 더한 값이 되므로 위와 같이 진행되었고, [0, 2]가 -1일 때 [0, 1]의 1과 더해지면서 0이 된 후는 전부 0+0이 된다.

(편의를 위해 0이 아닌 칸에 대해서만 진행했다.)

최종적으로 진행된 결과 값이 두 번째 사진처럼 된다.

이러한 원리로 또 열을 기준으로 합을 진행해보면,

최종적으로 이와 같이 나타나게 된다.

이렇게 되면 우리가 원했던 [0, 0], [1, 1]을 꼭짓점으로 가지는 사각형 만큼 값을 삽입하게 된 것이다.

이렇게 계산된 누적합 배열을 기존 board 배열에 더하게 되면 우리가 원하는 값이 도출될 것이다.

이렇게 문제를 푸는 것이 항상 빠르게 작용하는 것은 아니나, 브루트포스로 풀었을 때 예시를 든 것 같은 경우에는 이것이 훨씬 빨리 작동할 수 있다.

문제 출처: 프로그래머스

문제 설명

🔎철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.

예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다.
- 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다.
- 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. - 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다.
- 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다.
- 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다.
- 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다. 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다.

어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.

제한사항
- 1 ≤ topping의 길이 ≤ 1,000,000
- 1 ≤ topping의 원소 ≤ 10,000

본 문제는 아주 간단한 문제이지만 시간 복잡도를 어떻게 개선하느냐에 관한 문제였다.

topping을 1번 순회하는데만 1,000,000번의 연산이 수행되므로, 파이썬에서는 O(n)으로 구현해야 1초 안에 문제가 해결된다고 볼 수 있다.

첫 번째 시도는 set과 stack을 이용한 풀이였다.

<틀린 코드 보기>

def solution(topping):
    answer = 0
    t2 = set()
    for i in range(len(topping)):
        t2.add(topping.pop())
        if len(t2) == len(set(topping)):
            answer += 1
    
    return answer

결과는..

20개의 테스트 케이스 중에서 2개만 맞고 전부 시간초과 하였다.

일반적으로 가장 수월한 1번 테스트 케이스조차 1초가 넘는 시간이 걸린 것으로 보아, 시간 복잡도 개선에 실패한 것이 분명했다.

원인은 리스트를 set으로 변환하는 set(topping)의 시간복잡도가 O(n)이기에 반복문 안에 존재하면 O(n) << t < O(n²) 정도의 시간이 발생하기 때문이었다.

따라서 for문 안에서 타입 변환이 일어나지 않게 하는 코드를 작성하였다.

<정답 코드>

from collections import Counter
def solution(topping):
    answer = 0
    kinds = Counter(topping)
    t2 = set()
    for i in topping:
        t2.add(i)
        kinds[i] = kinds[i]-1
        if kinds[i] == 0:
            del kinds[i]
            
        if len(t2) == len(kinds.keys()):
            answer += 1
        
    
    return answer

Counter은 해당 iterator 안에서 unique한 원소가 몇개씩 존재하는지 딕셔너리 형태로 반환해주는 클래스이다.

시간복잡도는 iterator의 길이 n에 따른 O(n)이다.

접근 방법은 아래와 같다.

1. topping 안에 존재하는 각 원소들의 개수를 Counter을 이용해 구한다. (=> kinds)

2. 철수가 먹을 토핑을 set으로 정의한다. (=>t2)

3. topping을 순회하면서 t2에 토핑을 하나씩 추가하고, kinds에서 해당 토핑의 개수를 -1 해준다. 

    3-1. kinds에서 해당 토핑이 0개가 되면 삭제해 key값에 포함되지 않게 한다.

4. t2의 길이와 kinds의 key 길이가 같아지면 answer을 +1 해준다.

t2가 set이므로 같은 토핑을 반복해서 집어넣어도 set의 길이가 늘어나지 않는다는 점을 이용해 진행한 풀이다.

Counter의 존재를 몰라도, topping을 한번 순회하는 것으로 직접 구현할 수 있으므로 (몇번 틀리긴 했지만)생각보다 간단한 문제였다.

문제 출처: 백준 온라인 저지

문제 설명

🔎상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

캔디크러쉬를 구현하라는 문제였다.

사진같은 게임판이 주어졌을 때, 딱 한번 인접한 칸 끼리 교체할 수 있을 때 같은 문자가 나타나는 열 또는 행이 최대가 되는 방법을 도출하라는 것이다.

구현을 바탕으로 한 문제지만 문제 분류도 그렇고 결국은 브루트 포스로 접근해야하는 문제였다.

<정답 코드>

def candy_count(x, y):
    global n
    ea_x, ea_y = 1, 1
    cur = candy[x][y]

    for ny in range(y+1, n):
        if candy[x][ny] == cur:
            ea_y += 1
        else:
            break

    for py in range(y-1, -1, -1):
        if candy[x][py] == cur:
            ea_y += 1
        else:
            break

    for nx in range(x+1, n):
        if candy[nx][y] == cur:
            ea_x += 1
        else:
            break

    for px in range(x-1, -1, -1):
        if candy[px][y] == cur:
            ea_x += 1
        else:
            break

    return max(ea_x, ea_y)



n = int(input())
candy = [list(input()) for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
ans = 0

for x in range(n):
    for y in range(n):
        ans = max(ans, candy_count(x,y))
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0 <= nx < n) and (0 <= ny < n) and candy[x][y] != candy[nx][ny]:
                candy[x][y], candy[nx][ny] = candy[nx][ny], candy[x][y]
                ans = max(ans, candy_count(x, y))
                candy[x][y], candy[nx][ny] = candy[nx][ny], candy[x][y]

print(ans)

브루트포스 문제의 특성인건지 아니면 내가 정말 코드를 너무 못짜서 그런건지, 지저분하게 답이 나왔다.

접근 방법은 아래와 같다.

1. 입력을 2차원 리스트를 통해 게임보드처럼 생성한다.

2. 반복문을 통해 모든 칸을 순회한다.

3. 각 칸을 순회할 때 주변의 사탕 수를 count한다. 

    3-1. count는 candy_count함수를 통해 이루어진다.

    3-2. candy_count함수는 상하좌우를 모두 순회해 사탕의 행, 열 중 더 많은 사탕의 수를 반환한다.

4. 각 칸에서 인접한 모든 칸에 대해 이동할 수 있고, 원래 칸과 다른 사탕일 때만 스왑한다.

5. 스왑한 후에 candy_count를 한번 더 수행한다.

candy_count함수의 경우는 투포인터나 재귀를 통해 좀 더 간략하게 구현할 수 있었을 것 같다.

브루트포스 문제는 보통 각오로 덤빌 수 있는 문제는 아닌 것 같다. 시간 복잡도도 고려해야하고, 구현 자체도 복잡하고, 코드도 길어져서 한번 틀리면 디버깅하는게 힘든 것 같다.

문제 출처: 프로그래머스

문제 설명

🔎정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

달팽이가 삼각형을 그리면서 한칸씩 이동할 때 발자취를 남기는 문제다.

해당 문제는 어떤 특별한 자료구조를 사용하기 보다 어떻게 구현할 것이냐가 중요한 문제였다.

처음에는 새로운 삼각형 시작의 상관성을 찾아서 문제를 쉽게 해볼려고 노력했었다. (ex. n=4일 때, 다음 삼각형은 10에서 시작, n=5일 때는 13일 때 시작..)

하지만 늘 그렇듯 이렇게 생각하는게 오히려 더 복잡하게 돌아가는 방법이었고, 그냥 단순무식하게 코딩을 하는게 더 빠르게 답을 도출할 것 같다 생각이 들었고, 실제로 그랬다.

<정답 코드>

def solution(n):
    answer = [[0]*i for i in range(1, n+1)]
    dx = 0
    x, y = 0, 0
    cur = 1
    
    while n:
        if dx == 0:
            for i in range(n):
                answer[x][y] = cur
                cur += 1
                x += 1
            x, y = x-1, y+1
            dx = 1
            
        elif dx == 1:
            for i in range(n):
                answer[x][y] = cur
                cur += 1
                y += 1
            y -= 1
            dx = 2
        
        else:
            for i in range(n):
                x, y = x-1, y-1
                answer[x][y] = cur
                cur += 1
            x += 1
            dx = 0
        
        n -= 1
            
    ans = []
    for i in answer:
        ans.extend(i)
        
    return ans

결과적으로 코드가 아주 너저분하게 됐지만, 통과는 하였다.

접근 방법은 아래와 같다.

1. 피라미드 형식의 2차원 리스트를 생성한다.

2. 달팽이의 진행 방향을 결정하는 dx와 칸을 이동할 때 마다 증가하는 cur 변수를 통해 기록을 진행한다.

3. 달팽이가 한 방향으로 진행할 때 마다 전진 횟수가 줄어드는데 이는 n을 통해 기록한다.

4. 달팽이를 진행시키면서 기록한다.

5. 결과로 나온 2차원 리스트를 1차원 형식으로 변경한다.

달팽이는 사진처럼 이동한다.

dx = 0일 때 좌하향, dx = 1일 때 우향, dx = 2일 때 좌상향한다.

한 방향으로 진행이 끝나면 다음 방향으로 진행 횟수가 1 감소한다. (최초 진행횟수는 피라미드의 높이인 n과 같다.)

for문을 통해 해당 사항을 구현하면 최후의 좌표가 도착해야할 좌표보다 1 커지기 때문에 해당 진행 방향으로 1 감소시켜주는게 중요하다.

코딩 테스트는 참 컨디션에 영향을 많이 받는 것 같다. 어떤 날은 복잡한 문제가 더 잘 풀리고, 어떤 날은 간단한 문제가 잘 풀리고.. 기복이 없이 조절하는 것이 앞으로의 과제인 것 같다.

문제 출처: 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/17687)

문제 설명

🔎튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.

숫자를 0부터 시작해서 차례대로 말한다.
첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.
10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다.
이렇게 게임을 진행할 경우,0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, …순으로 숫자를 말하면 된다.

한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, …순으로 숫자를 말하면 된다.

이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.

(별 희한한 동아리가 다 있다.)

나는 진법 변환을 남들보다 어렵게 푸는 경향이 있어 어렵게 느껴졌던 문제였다.

처음 접근 방식은 전체 사람 수 만큼 돌 때 진행되는 길이에서 p번째 수를 추출하는 방법이었다.

이런 접근은 진법이 고정되어있으면 해볼만한 시도였지만, n에 따라 전체 사람 수 만큼 돌 때 진행되는 수(10진수)가 달랐기 때문에 구현을 제대로 해보지도 못했다.

정답률이 56%나 되고, 질문도 별로 없었던 문제인데 고집 때문에 차마 구글에 검색하지는 못하고 그나마 있는 질문들에서 정보를 캐내 다음과 같은 풀이 방법으로 문제를 해결할 수 있었다.

<정답코드>

# 진법 변환기
def change(n: int, num: int) -> str:
    result = ''
    while num:
        num, mod = num//n, num%n
        if 9 < mod:
            mod = chr(mod+ord('A')-10)
        result += str(mod)
    
    return result[-1::-1]

def solution(n, t, m, p):
    total = t*m
    cur = '0'
    nx = 1
    
    while len(cur) < total:
        cur += change(n, nx)
        nx += 1
    
    return cur[p-1:(t-1)*m+p:m]

접근은 처음 생각했던 것과 크게 다르진 않다.

1. 숫자를 말하는 전체 횟수는 t*m이다.

2. 따라서, 현재 진행되고 있는 숫자를 문자열로 치환한 것을 현재까지 얘기한 숫자(문자형)에 더한다.

3. 해당 숫자(문자형)의 길이가 t*m이 되면 반복문을 탈출한다.

4. 발표 순서와 순환 수에 따라 문자열 slicing을 통해 정답을 도출한다.

처음 생각한 것과 가장 큰 차이점은 매번 p번째를 도출할 필요가 없어, 매번 문자열을 잘라 생각할 필요가 없다는 것이다. (해당 문제는 문자열 slicing을 통해 해결이 가능했다.)

그리고 while을 탈출할 기준을 진법에 따라 정할 필요가 없고 길이로 보면 간단한 것을 너무 어렵게 생각했던게 이번 문제에 고전했던 이유였던 것 같다.