3085번 사탕 게임에서 제 풀이가 왜 틀린걸로 처리되는지 잘 모... - 인프런

세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)

BOJ 2580

3085번 사탕 게임에서 제 풀이가 왜 틀린걸로 처리되는지 잘 모르겠습니다.

해결된 질문

작성

안녕하세요 선생님. 백준 3085번 풀이2와 제 풀이가 비슷한 것 같은데 제 풀이는 틀린 것으로 나오는데 어떤 부분이 잘못됐는지 잘 모르겠습니다. 제가 어떤 부분을 놓치고 있는지 알려주시면 감사하겠습니다!

import sys
from itertools import combinations

def input():
    return sys.stdin.readline().rstrip()

def get_max(i,j):
    global data, n
    ser1 = data[i]
    ser2 = [data[k][j] for k in range(n)]
    return max(count_max(ser1), count_max(ser2))

def count_max(ser):
    count = 0
    bef = '.'
    for idx in range(len(ser)):
        if bef != ser[idx]:
            count = 1
        else:
            count += 1
        bef = ser[idx]
    return count


n = int(input())

data = []
for _ in range(n):
    data.append(list(input()))

dx = [0,1,-1,0]
dy = [1,0,0,-1]

cur_max = 0
for i in range(n):
    for j in range(n):
        if i == j:
            cur_max = max(cur_max, get_max(i, j))
        for di, dj in zip(dx,dy):
            ni = i + di
            nj = j + dj
            if not ((0 <= ni < n) & (0 <= nj < n)):
                continue
            if (data[ni][nj] == data[i][j]):
                continue
            
            data[i][j], data[ni][nj] = data[ni][nj], data[i][j]
            
            cur_max = max(cur_max, get_max(i, j))
            data[i][j], data[ni][nj] = data[ni][nj], data[i][j]
print(cur_max)

python 코딩-테스트 알고리즘

답변 2

알리 Ally

지식공유자

안녕하세요, 최재원님!

count_max(ser) 에서 가장 긴 부분의 길이를 반환해야 하므로 아래와 같이 고쳐 주시면 될 것 같습니다!

def count_max(ser):
    best = 0
    count = 0
    bef = '.'
    for idx in range(len(ser)):
        if bef != ser[idx]:
            count = 1
        else:
            count += 1
        best = max(best, count)
        bef = ser[idx]
    return best

또 궁금하신 점 있으시면 질문해주세요. :)

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 최재원님.

백준 3085 “사탕 게임” 문제에서 실제로 사탕들의 위치를 교환하고, 교환 이후 가장 긴 연속된 사탕의 개수를 계산하는 것이 핵심입니다. 주신 코드에서 몇 가지 점검해볼 부분을 설명드리겠습니다:

사탕의 교환과 탐색: 코드를 보면 data[i][j]와 data[ni][nj]를 교환한 후, get_max 함수를 호출하여 사탕 배열의 변경된 상태에서 연속 사탕의 최대 길이를 계산하고 있습니다. 그러나 get_max 함수는 단순히 열과 행에 대한 연속된 부분만을 검사하고 있어서, 정확한 부분이 누락될 수 있습니다.
전체 배열 탐색: 교환이 발생하면, 이후의 배열에 대해 전체적으로 탐색하여 모든 상황을 고려해야 합니다. 동일한 방식으로는 배열의 모든 부분을 검사할 수 없으므로, 교환 후에 전체 배열을 다시 탐색해야 하는 점을 놓치기 쉽습니다. get_max를 호출하는 부분을 확장하여 모든 가능한 경우를 탐색하는 코드를 작성하는 것이 중요합니다.
방향 변경 실수: for di, dj in zip(dx, dy): 부분에서 인덱스를 변경할 때 dx, dy 배열이 올바르게 사용되고 있는지 확인해 봐야 합니다. 잘못된 방향으로 인덱스를 이동시키는 경우가 없도록 꼼꼼히 검토하세요.
비교 조건: 두 개의 사탕이 다를 때에만 교환이 이루어지는지도 확인이 필요합니다. 경우에 따라 이미 같은 색의 사탕을 비교함으로써 불필요한 교환이 이루어지지 않도록 체크하는 것이 좋습니다.

유사한 문제에 대한 기존의 답변을 살펴보면 더 많은 인사이트를 얻을 수 있습니다. 예를 들어, 비슷한 문제가 있는 게시글에서는 이런 알고리즘적 접근 방법에 대한 여러 팁과 사례가 제공되고 있으니 살펴보세요.

더 나은 이해를 위해 몬테카를로 방법이나 다양한 시뮬레이션 방법 등을 적용하여 직접 테스트 환경에서 다양한 전략을 시험해보는 것도 추천드립니다. 다양한 풀이 방법과 최적화를 통해서 보다 깊이 있는 학습이 가능하며, 이러한 시행착오는 알고리즘 문제 해결의 큰 자산이 될 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

3085번 사탕 게임에서 제 풀이가 왜 틀린걸로 처리되는지 잘 모르겠습니다.