스타 수열 (월간코드 챌린지1)

[sghong977]

#시도 1

• 점수: 57.1
• 오답은 없는데 모두 시간초과

현재 풀이 (예시: [5,2,3,3,5,3])

• input array 원소 하나씩 조사함
• 예를 들어, 첫 원소는 5니까 이거랑 값이 같은지 다른지를 bool연산으로 저장함. [1,0,0,0,1,0])
• 인덱스 t, t+1이 다르면 +2 위치로 넘어가서 조사. 같으면 스타수열 길이에서 1을 빼고, +1 위치로 넘어가서 조사.
• 끝나면 남은 스타수열 길이가 나옴.
• 원소 돌아가면서 (중복인건 패스하고) 다 돌면 최대값이 나옴.

미리 제거할수 있는 경우가 또 없을까?
예를들어, 현재 스타수열 최대 길이 값이 2k라고 하면, 해당 원소 (예시:3)가 배열에 있는 개수가 k 미만이면 체크할 필요가 없다거나.

`

    def solution(a):
        checked_num = []
        max_len = -1
        # check one number
        for i in range(len(a)):
            if a[i] in checked_num:
                continue
            tmp_len = len(a)
            tmp = [j == a[i] for j in a]
            idx = 0
            for t in range(len(tmp)):
                if idx != t:
                    continue
                if (t+1) >= len(tmp):
                    tmp_len -= 1
                    break
                if (tmp[t] != tmp[t+1]):
                    idx += 2
                    continue
                else:
                    idx += 1
                    tmp_len -= 1
            if tmp_len > max_len:
                max_len = tmp_len
            checked_num.append(a[i])    
        answer = max_len
        return answer

`

[sghong977]

시도 2

• 위에서 말한 예외를 추가해서 걸렀지만 점수는 오르지 않음

• 추가로 자잘한걸 고쳤지만 실행속도가 1/3~1/4수준으로 줄어든거같긴 한데 점수가 똑같음

• 숫자가 크면 문제인건가? 굳이 bool 배열을 만들지 말까?

• 배열 안 만들고 조건문을 비트연산으로 걸어뒀으나 실패

• 뭔가 근본적인 문제가 있는 듯. 방법 없나?

`

    def solution(a):
        checked_num = set()
        max_len = -1
        # check one number
        for i in range(len(a)):
            if a[i] in checked_num:
                continue
            tmp_len = len(a)
            tmp = [j == a[i] for j in a]
            
            # exceptional case added
            if (sum(tmp)*2 < max_len) or (len(a) - i < max_len):
                checked_num.add(a[i])
                continue
            
            # start checking
            idx = 0
            for t in range(len(tmp)):
                if idx != t:
                    continue
                if (t+1) >= len(tmp):
                    tmp_len -= 1
                    break
                if (tmp[t] != tmp[t+1]):
                    idx += 2
                    continue
                else:
                    idx += 1
                    tmp_len -= 1
            if tmp_len > max_len:
                max_len = tmp_len
            checked_num.add(a[i])    
        answer = max_len
        return answer

`