(Hard) Sherlock and Anagrams

아나그램이란?

아나그램이란 한 단어의 철자를 분해해 다른 단어, 혹은 다른 문장으로 바꾸는 놀이

 

약간 수학적인 요소가 있어서 어렵지만 재미있는 훈련이 될 것이다.

 

문제:

https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem

 

설계:

1. 애너그램 처럼 실제로 문자를 뒤집고 하려면 복잡하다. 어떻게 단순화 할 수 있을까?

    -> 문자열 정렬

2. 문자열에 대한 모든 케이스를 조사해야되는데 삼중 포문이 필요하려나?

    -> 이중 포문만 있어도 된다

       ㄴ 역할 1: 문자열 시작위치를 한칸씩 이동

       ㄴ 역할 2: 자르는 범위를 한칸씩 또 늘려야한다.

3. 반복되는 문자가 나오면 count 를 증가시킨다.

4. 같은 문자가 여러번 반복되면 시그마 합을 구해야한다 (ㄷㄷㄷㄷ)

 

나의 풀이:

1)

    TOTAL = 0
    dic = {}    
    for i in range(len(s)): #0, 1, 2, 3
        for j in range(?): #0, 1, 2, 3
            sub = ''.join(s[:]) #0~1, 1~2, 2~3, 3~4 이렇게 움직이면서 잘라야한다

 

2)

    TOTAL = 0
    dic = {}    
    for i in range(1, len(s)): #1, 2, 3
        for j in range(?): #0, 1, 2, 3
            sub = ''.join(s[j:j+i]) #0~1, 1~2, 2~3, 3~4
            # j는 한개씩 느는데 그다음 사이클에서는 점차 간격을 늘려야하니 j:j+i로 잘라야겠네
            # j:j+i를 하자니 i가 overflow날 수 있으니 첫번째 조건에 +1을 해버리자

 

3)

    TOTAL = 0
    dic = {}    
    for i in range(1, len(s)): #1, 2, 3
        for j in range(len(s)-i+1): #0, 1, 2, 3
            sub = ''.join(s[j:j+i]) #0~1, 1~2, 2~3, 3~4
            # 프로그램을 실행하면 아래처럼 잘리긴 하겠는데
            # 0-1, 1-2, 2-3, 3-4 -> k, k, k, k
            # 0-2, 1-3, 2-4 -> kk, kk, kk 
            # 두번째 사이클에서는 3-5가 나오면 안되.. 반복할때마다 j 범위가 줄어야겠네 (-i+1)

 

4)

    TOTAL = 0
    dic = {}    
    for i in range(1, len(s)): #1, 2, 3
        for j in range(len(s)-i+1): #0, 1, 2, 3
            sub = ''.join(s[j:j+i]) #0~1, 1~2, 2~3, 3~4
            if sub in ana_dict.keys() :
                ana_dict[sub] += 1
            else :
                ana_dict[sub] = 1
    return TOTAL

 

5) 왜 안되지?
함정 1 : 스키마 합을 빼먹음

    TOTAL = 0
    dic = {}    
    for i in range(1, len(s)):
        for j in range(len(s)-i+1):
            sub = ''.join(s[j:j+i])
            if sub in ana_dict.keys() :
 	            TOTAL += ana_dict[sub] #k,k,k,k 인 경우 총 3+2+1 = 7번이다.
                ana_dict[sub] += 1
            else :
                ana_dict[sub] = 1
    return TOTAL

 

6) 왜 안되지?
함정 2: 문자열 정렬을 빼먹음

    TOTAL = 0
    ana_dict = {}    
    for i in range(1, len(s)):
        for j in range(len(s)-i+1):
            sub = ''.join(sorted(s[j:j+i]))
            if sub in ana_dict.keys() :
 	            TOTAL += ana_dict[sub]
                ana_dict[sub] += 1
            else :
                ana_dict[sub] = 1
    return TOTAL

 

완료!