HackerRank [String] Bear and Steady Gene /알고리즘 해커랭크[미해결]

---

문제 주소 : www.hackerrank.com/challenges/bear-and-steady-gene/problem

난이도 : Medium
성공률 : 63.58%

 

 

(210505) [미해결] 7개 예제 타임아웃

 

문제 : 4의 배수의 길이를 가진 문자열을 준다
그 문자는 A, C, T, G로만 구성되어있다
substring을 수정하여 A, C, T, G가 모두 같은 개수가 나오게 해야 한다
최소한으로 수정해야하는 substring 길이 값을 리턴하라

 

풀이
1) ACTG 문자 중 초과된 문자와 각각의 수, 합산한 수(변환해야 하는 최소 개수)를 체크
2) 변환해야 하는 최소개수길이만큼 substring을 한 칸씩 이동하며 분리시켜봄
3) 분리시킨 substring에 변환해야하는 문자들이 모두 포함하는지 체크(함수 dist_check)
4) 모든 substring이 포함하지 않는다면 최소 개수 길이+1을 한 뒤 다시 처음부터 substring을 한 칸씩 이동하며 체크해봄 
4) 최종적으로 포함되었을 때 길이값을 리턴

 

답안

#!/bin/python3
import math
import os
import random
import re
import sys
import collections
import time


#0502 타임오버남 7개나... count하는건 꼭 필요한거같고 비교부분에서 dist를 최대한 없애야 할듯? 혹은 마지막 체크하는 이중 포문에서? 
#0505 다음에 다시풀어보자 2포인트로 앞뒤 맞춰가다 하는듯..


def dist_check(over_dist, temp_substr):
    # for k in over_dist:
    #     try:
    #         if over_dist[k] > temp_substr.count(k):
    #             return False
    #     except:
    #         return False
    # else:
    #     return True
    newdist_counter : dist = collections.Counter(temp_substr)
    for k in over_dist:
        if over_dist[k] > newdist_counter[k]:
            return False
    else:
        return True




def steadyGene(gene):
    start_time : time = time.time()
    gene_length : int = len(gene)
    move_count   : int = 0
    sum_count : int = 0
    dist_counter : dist = collections.Counter(gene)   
    dist_overchar: dist = {} 

    for i in dist_counter:          #초과된 문자의 수(전체길이/4)가 있는지 있다면 얼마나 초과됬는지 누적하기, 그게 변환시켜야 할 최소 개수이므로
        if gene_length/4 < dist_counter[i]:
            move_count = int(dist_counter[i] - gene_length/4)
            sum_count += move_count
            dist_overchar[i] = int(move_count)                  #초과된 애들 저장해놓기 각 문자가 얼마나 초과되었는지 저장해놓기

    if sum_count == 0:             #초과된게 없다면 정상!!!
        return 0
    temp_substr = ""
    
    # for i in range(move_count, gene_length-1):    #[변환시켜야 할 최소 개수]부터 하나씩 늘려보기 문자열 최대길이 만큼? 어짜피 최대길이 -1전엔 끝나긴함
    #     for j in range(0, gene_length-i):           #[변환시킬 시작점]  한칸씩 옆으로 이동해보며 i길이 만큼 지워본다 남은 문자열이 초과된 문자와 그 문자의 초과된 수만큼 있으면 i리턴 끝
    #         temp_substr =   gene[j:i+j]
    #         if dist_check(dist_overchar, temp_substr) == True :
    #             return i           
    for i in range(move_count, gene_length-1):    #[변환시켜야 할 최소 개수]부터 하나씩 늘려보기 문자열 최대길이 만큼? 어짜피 최대길이 -1전엔 끝나긴함
        for j in range(0, gene_length-i):           #[변환시킬 시작점]  한칸씩 옆으로 이동해보며 i길이 만큼 지워본다 남은 문자열이 초과된 문자와 그 문자의 초과된 수만큼 있으면 i리턴 끝
            temp_substr =   gene[j:i+j]
            if dist_check(dist_overchar, temp_substr) == True :
                print("time : {}", time.time()-start_time)
                return i         
                    
            

    # print(dist_overchar)

if __name__ == '__main__':
    # fptr = open(os.environ['OUTPUT_PATH'], 'w')
    fptr = sys.stdout

    n = int(input().strip())

    gene = input()    

    result = steadyGene(gene)

    fptr.write(str(result) + '\n')

    fptr.close()

 

느낀점

시간을 재보니 서브스트링을 분리하며 그걸 비교할 때 시간이 상당히 걸렸다
힌트를 찾아보니 중간까지는 다른사람들과 동일한데 투포인터를 이용해서 탐욕알고리즘을 쓰면 된다는데
한 외국인의 코드를 봤는데 봐도 잘 모르겠다.. 나중에 공부좀 더 한뒤 다시 풀 예정

정답을 하나 까봤는데 답은 맞는데 285초가 걸린다 ㅋㅋㅋㅋ 아놔

---