[코드트리] 시뮬레이션 - 행복한 수열의 개수

코드트리 학습하기 - 알고리즘 입문 : 시뮬레이션

• 행복한 수열의 개수 (Python)
  https://www.codetree.ai/missions/2/problems/number-of-happy-sequence/description

Code

n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

happy = 0

# 행복한 수열인지 확인하는 함수
def check_happy(arr):
    max_cnt = 1
    cnt = 1
    for k in range(len(arr)-1):
        if(arr[k] == arr[k+1]):
            cnt += 1
        elif(arr[k] != arr[k+1]):     # 연속하여 동일한 원소가 나오지 않고 끊긴 구간에서 최대로 동일한 원소가 나온 횟수 업데이트
            if (max_cnt < cnt):
                max_cnt = cnt
            cnt = 1
    if (max_cnt < cnt):     # 한번 더 확인해서 최대 카운트로 업데이트
        max_cnt = cnt
    if(max_cnt >= m):
        return True
    else:
        return False

# 각 행, 각 열 담기
for i in range(n):
    sub1 = []
    sub2 = []
    for j in range(n):
        if(len(sub1) <= n):
            sub1.append(matrix[i][j])       # 행
        if(len(sub2) <= n):
            sub2.append((matrix[j][i]))     # 열

    # print(sub1)
    # print(sub2)

    # 행복한 수열인지 확인
    ck_1 = check_happy(sub1)
    ck_2 = check_happy(sub2)

    # 행복한 수열이라면 정답에 +1
    if(ck_1):
        happy += 1
    if(ck_2):
        happy += 1

    # print(happy)
    # print("==")

print(happy)

풀이 및 해설

• 테스트케이스 6번에서 계속 틀렸음
  • 행복한 수열인지 확인하는 과정에서 앞 뒤 원소만 비교해서 카운트하고 m보다 크면 연속하여 m개 이상의 동일한 원소가 나오는 순간이 존재한다고 판단해버려서 틀림 !!
  • 반례 ) 1 1 2 2 3 3 → 이걸 입력했을 때 cnt값 (연속하여 같은 수가 몇개 있는지 세는 변수) 4로 나와버림 … 2가 나와야하는데 !!
    
  • 이걸 걸러내는 if문 추가 중간에 한번 연속하지않고 끊겼을 때, 지금까지 셌던 값 업데이트 + 다음 구간을 위해서 cnt 초기화 다 돌고나서 최대로 연속한 수 업데이트 → m이랑 값 비교