[codetree] 행복한 수열

| 문제

1이상 100이하의 숫자로만 이루어져 있는 n * n 크기의 격자 정보가 주어집니다.

이때 행복한 수열이라는 것은 다음과 같이 정의됩니다.

• 행복한 수열 = 연속하여 m개 이상의 동일한 원소가 나오는 순간이 존재하는 수열

n * n 크기의 격자 정보가 주어졌을 때 각 행마다 봤을 때 나오는 n개의 수열과, 각 열마다 봤을 때 나올 수 있는 n개의 수열을 포함하여 총 2n개의 수열 중 행복한 수열의 개수를 세서 출력하는 프로그램을 작성해보세요.

예를 들어, 다음과 같은 경우라면, 첫 번째 행을 골랐을 경우와 첫 번째 열을 골랐을 경우에만 행복한 수열이 되므로, 총 행복한 수열의 수는 2개가 됩니다.

 

첫번째 풀이

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



def check_row(input_lst):
    global result
    cnt = 0
    rst = 0
    for i in range(n):
        first = True
        for j in range(n):
            if first:
                rst = input_lst[i][j]
                cnt = 1
                first = False
                continue

            if input_lst[i][j] == rst:
                cnt += 1
            else:
                cnt = 1
                rst = input_lst[i][j]

            if cnt == m:
                result += 1
                break


def check_column(input_lst):
    global result
    cnt = 0
    rst = 0
    for j in range(n):
        first = True
        for i in range(n):
            if first:
                rst = input_lst[i][j]
                cnt = 1
                first = False
                continue

            if input_lst[i][j] == rst:
                cnt += 1
            else:
                cnt = 1
                rst = input_lst[i][j]

            if cnt == m:
                result += 1
                break

if m == 1:
    print(n*2)
    quit()
check_row(lst)
check_column(lst)
print(result)

• 레지스터를 두어 현재 i와 레지스터를 비교하는 로직
• 첫번째 i면 i를 rst에 넣어두고 first를 false로 바꾸고 다음으로 넘어간다.
• 그리고 다음이 rst와 같다면 cnt를 1추가해주고, 아니라면 cnt를 1로 초기화, 그리고 해당 순번의 요소를 rst에 넣는다.
• 마지막으로 cnt가 m과 같아지면 최종 결과를 +1해주고 해당 임시 배열을 break 하고 다음으로 간다.

최대한 함수로 짜보려고 노력했지만.. 하나로 합치면 깔끔할 것 같다. 그렇지만 밑에 보는 m이 1일 때를 해결하지 못했고 if문이 많아 좋은 알고리즘은 아닌 것 같다.

 

두번째 풀이

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

happy = 0
part = [0 for _ in range(n)]

def check_happy(target):
    global happy
    continuous_cnt = 1
    max_cnt = 1
    for i in range(n-1):
        if target[i] == target[i+1]:
            continuous_cnt += 1
        else:
            continuous_cnt = 1
        max_cnt = max(max_cnt, continuous_cnt)
    if max_cnt >= m:
        happy += 1


def make_row(input_list):
    global part
    for i in range(n):
        for j in range(n):
            part[j] = lst[i][j]
        check_happy(part)

def make_column(input_list):
    global part
    for j in range(n):
        for i in range(n):
            part[i] = lst[i][j]
        check_happy(part)

make_row(lst)
make_column(lst)
print(happy)

• 행, 렬을 임시의 하나의 리스트로 만들어서 행복한 수열인지 아닌지 테스트하는 함수로 넘겨준다.
• 판별기에서는 연속이면 증가하는 continuous_cnt와 max_cnt를 두어서 연속이 아닐 경우에 continuous_cnt가 1이 되어버리기 때문에 사라지는 것을 방지한다. 동시에 max 함수를 써서 현재 가장 긴 연속을 갱신해준다.
• 마지막에 해당 배열을 다 검사한 후, max가 m보다 크거나 같으면 happy 수열 개수를 증가시켜준다.

해설을 보고 이해한 뒤 다시 작성해본 코드. 훨씬 깔끔하다. 이런 연속되는 수열의 알고리즘 유형이 나온다면 배열을 만들어서 함수에 넣은 뒤, [i] == [i+1]읆 통해서 전과 비교하고, 연속되는 횟수를 담은 변수와 현재까지 가장 큰 연속되는 횟수를 담은 변수를 비교하여 더 큰 것을 저장하는 알고리즘으로 진행해야겠다.