백준(12891번) - DNA 비밀번호 문제풀이

접근

• 슬라이싱윈도우 이용해서 O(n) 시간복잡도로 계산

설계

• 슬라이싱 윈도우로 문자열 왼쪽 빼고 오른쪽 더해서 문자열 정의하기
• 정의한 문자열에 DNA 문자 개수 세서 stat 리스트에 저장하기
• ‘A’,’C’,’G’,’T’ 최솟값 minDNA 리스트와 stat 에 저장된 수 비교해서 DNA비밀번호 되는지 확인

lens, lenp = map(int,input().split())
st = input()
minDNA = list(map(int,input().split()))
DNAlst = ['A','C','G','T']
password = str()
stat = [0,0,0,0]
cnt = 0
for i in range(lenp): ## 초기 p만큼 문자 설정
    password += st[i]

for i in range(4):  ##   초기 상태 설정
    stat[i] += st.count(DNAlst[i])
flag = 1    
for i in range(4):
    if stat[i] < minDNA[i]:
        flag = 0
        break
if flag:
    cnt += 1

flag = 1
for i in range(lens-lenp):  ## 한칸씩 옮기면서 상태 업데이트
    password -= password[i]
    if password[i] == 'A':
        stat[0] -= 1
    elif password[i] == 'C':
        stat[1] -= 1
    elif password[i] == 'G':
        stat[2] -= 1
    else:
        stat[3] -= 1
    
    password += password[i+lenp]
    if password[i+lenp] == 'A':
        stat[0] += 1
    elif password[i+lenp] == 'C':
        stat[1] += 1
    elif password[i+lenp] == 'G':
        stat[2] += 1
    else:
        stat[3] += 1
    
    for i in range(4):
        if stat[i] < minDNA[i]:
            flag = 0
            break
    
    if flag:
        cnt += 1
        
print(cnt)

실패한이유:

• 처음 설계를 str로 한점
  • • 연산은 먹히지만 왼쪽값 뺄때 - 연산자 안먹혀서 실패
• 입력값을 list로 바꿔서 해보려고 했지만, 그러면 append 와 remove 함수를 사용해야 할 것 같았다.
  • for 문안에 함수쓰면 시간복잡도 O(n^2)로 늘어날 것 같아서 포기함. (아닌가?)

2번째 설계

 💡 처음 설계때는 슬라이싱 윈도우를 통해 직접 문자열을 뽑아 문자열끼리 비교하려고 했었기 때문에 연산이 많이 들어갔고, for문을 다시 사용하는 데에 겁먹음

 💡 두 번째 설계에는 굳이 문자열을 눈으로 확인하지 않고 ‘A’,’C’,’G’,’T’ 를 세는 배열을 만들어 적절한 인덱스에 +- 1 씩 해주면서 문자의 변화를 기록하는 방식을 사용했음

def check(a,b):      ## 문자열의 'A','C','G','T' 개수를 비교해 DNA 숫자인지 확인하는 함수
    cnt = 0
    for i in range(4):
        if a[i] >= b[i]:   ## a = ACGT_cnt, b = min_ACGT
            cnt += 1
    if cnt == 4:
        return 1
    return 0
    
    
ll, lp = map(int,input().split())
DNAst = input()
min_ACGT = list(map(int,input().split()))  ## 인풋

ACGT_cnt = [0] * 4
result = 0

for i in range(lp):                        ##맨처음 문자열 ACGT_cnt 배열에 저장
    if DNAst[i] == 'A':
        ACGT_cnt[0] += 1
    elif DNAst[i] == 'C':
        ACGT_cnt[1] += 1
    elif DNAst[i] == 'G':
        ACGT_cnt[2] += 1
    else:
        ACGT_cnt[3] += 1
result += check(ACGT_cnt,min_ACGT)  ## 체크

for i in range(ll-lp):  ##슬라이싱 윈도우 
    # 왼쪽 값 빼기
    if DNAst[i] == 'A':
        ACGT_cnt[0] -= 1
    elif DNAst[i] == 'C':
        ACGT_cnt[1] -= 1
    elif DNAst[i] == 'G':
        ACGT_cnt[2] -= 1
    else:
        ACGT_cnt[3] -= 1
    # 오른쪽값 더하기
    if DNAst[i+lp] == 'A':
        ACGT_cnt[0] += 1
    elif DNAst[i+lp] == 'C':
        ACGT_cnt[1] += 1
    elif DNAst[i+lp] == 'G':
        ACGT_cnt[2] += 1
    else:
        ACGT_cnt[3] += 1

    result += check(ACGT_cnt,min_ACGT)  ## 양쪽 다 옮기면 체크

print(result)

결과 : 성공!

느낀 점 : 코드를 어떻게 짤지 접근하고 , 설계할 때 위의 코드처럼 if문을 4 줄씩 쓰면서 직접 A,C,G,T 를 적어주고 이런 과정이 굉장히 무식해 보이고 지저분한 과정이라고 생각한다.

그런 생각 때문에 코드를 더 복잡하게 설계하려고 하고(for 문을 써서 자동화 하는 척 한다 든 지) , 더 불필요한 과정을 만들어 내기도 하는 것 같다.

그리고 이 문제를 풀 때 문자열끼리 비교해야 한다는 생각에 사로잡혀서 첫 번째 같은 코드를 짰다.

시간복잡도 계산도 어려웠고, 코드도 돌아가지 않았다. (이건 내 실력문제)

좀 더 컴퓨터처럼 생각하는 습관을 들여야겠다.