운동하는 개발자/알고리즘, 코딩테스트

HackerRank [Strings] Sherlock and Anagrams /알고리즘 해커랭크

우용현 2021. 4. 25. 20:44
728x90

문제 주소 : www.hackerrank.com/challenges/sherlock-and-anagrams/problem

이도 : Medium
성공률 : 87.92%

 

문제 : 주어진 문자열에서 에너그램인 하위 문자열이 몇 쌍인지 구하시오

 

풀이 : 글자수를 늘려주며 하위 문자열을 비교 

 

답안

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'sherlockAndAnagrams' function below.
#
# The function is expected to return an INTEGER.
# The function accepts STRING s as parameter.
#

def sherlockAndAnagrams(s):
    tempStr1 : str = ''
    tempStr2 : str = ''  
    count : int = 0
    lenS : int = len(s)

    #한글자씩 탐색, 두글자씩 탐색 , 3개씩 탐색 루프를 만들어야함 3중루프여야할듯
    for strlen in range(1, lenS+1):  			#글자 길이 수 
        for i in range(0, lenS-strlen):     	#앞문자 시작위치
            for j in range(i+1, lenS-strlen+1): #뒷문자 시작위치
                tempStr1 = s[i:i+strlen]              
                tempStr2 = s[j:j+strlen]
                if sorted(tempSet1) == sorted(tempSet2):
                    print(tempSet1, tempSet2)
                    count+=1              
    return count


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

    q = int(input().strip())

    for q_itr in range(q):
        s = input()

        result = sherlockAndAnagrams(s)

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

    fptr.close()

 

느낀점

더보기
빠른 문자열 처리를 두고 처음엔 고유 문자만 비교하려고 set에 넣었으나 고유문자만 비교하면 안되는 케이스를 발견 문자열을 정렬시키는 방식으로 변경
문자열 처리가 상당히 빠르다는걸 알고 있음에도 굳이 힘들게 가려고 했었다

 

728x90