codility의 PrettyTiling 문제를 보며 느낀점

https://app.codility.com/programmers/challenges/carol_of_the_code2022/

Carol of the Code challenge

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import sys
sys.setrecursionlimit(10 ** 9)

answer = 987654321

def solution(A):
    # Implement your solution here
    answer = 987654321

    N = len(A)
    for i in range(4):
        rotate = i if i != 3 else 1
        prev_r = (1+i)%4
        prev_c = A[0][prev_r]
        for j in range(1, N):
            match_r = A[j].index(prev_c)
            rotate += abs(3-match_r) if match_r != 0 else 1
            prev_r = (match_r + 2) % 4
            prev_c = A[j][prev_r]
        answer = min(answer, rotate)
    return answer

 

 

이제 코테는 문제풀이용 알고리즘 찾고 하는것보단 진짜 그 문제를 풀기위한 코드를 작성하도록 바뀌는 것 같다.

그래서 문제의 본질을 파악해서 푼게 위 코드고 잘 나옴.

이게 맞는것 같은데, 내가 지금까지 하던게 대부분 쓸모없어진 것 같아 마음이 아프다.

 

 

밑에가 지금까지의 dfs네 뭐네 하며 고전적으로 푼 방법

 

import sys

sys.setrecursionlimit(10 ** 9)

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

answer = 0


def is_answer(A):
    for i in range(len(A) - 1):
        if A[i][1] != A[i + 1][3]:
            return False
    return True


def dfs(step, now, A):
    global answer
    if now == len(A):
        if is_answer(A):
            answer = min(answer, step)
        return

    # nothing
    dfs(step, now + 1, A)

    original = A[now][:]
    # clock
    A[now] = original[3] + original[:3]
    dfs(step + 1, now + 1, A)

    # clockwise
    A[now] = original[1:4] + original[0]
    dfs(step + 1, now + 1, A)

    # opposite
    A[now] = original[2:] + original[:2]
    dfs(step + 2, now + 1, A)

    A[now] = original


def solution(A):
    global answer
    # Implement your solution here
    # print(A)
    answer = 987654321
    dfs(0, 0, A)
    return answer

문제에 대한 답은 정확하지만 효율성(속도)에서 개쳐발린걸 볼 수 있다.

진짜 그 문제만을 위한 풀이를 해야된다.