[Python] BOJ 11328 : Strfry

요구사항

• 시간 제한 2초 : 넉넉할 것이라 생각했다.. N**2 이면 10,000,000 이면 괜찮은 거 같은데 
• 메모리제한 256MB 항상 넉넉하다.
• strfry 함수를 적용하여 얻어질 수 있는 지 판단. 

설계 1

• 두 문자열을 입력받는다. 
• 이중 for문을 돌려 두 문자열을 비교한다. 
• 같으면 count += 1 
• 문자열의 길이와 count 가 같다면 둘은 같다. 

구현 1

def is_same(a, b):
    len_a = len(a)
    count = 0


    for alpha in b:
        for i in range(len_a):
            if a[i] == alpha:
                count += 1
    
    if count == len_a:
        return "Possible"
    else:
        return "Impossible"

N = int(input())

for _ in range(N):
    a, b = input(). split()
    print(is_same(a, b))

• 백준에서 시간 초과가 나버렸다
• 로직을 저장하는 거로 바꾸자. 
• 각 문자의 빈도 수를 저장함. 
• 그리고 그 빈도 수가 같으면 가능, 불가능 출력

구현 2

def is_same(a, b):
    if len(a) != len(b):
        return "Impossible"

    # 각 문자의 개수를 세기 위한 딕셔너리
    count_a = {}
    count_b = {}

    # 문자열 a에 대해 각 문자 빈도 계산
    for char in a:
        if char in count_a:
            count_a[char] += 1
        else:
            count_a[char] = 1

    # 문자열 b에 대해 각 문자 빈도 계산
    for char in b:
        if char in count_b:
            count_b[char] += 1
        else:
            count_b[char] = 1

    # 두 문자열의 문자 빈도표 비교
    if count_a == count_b:
        return "Possible"
    else:
        return "Impossible"


import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

for _ in range(N):
    a, b = input().split()
    print(is_same(a, b))

 

구현 3 

from collections import Counter

def is_same(a, b):
    if Counter(a) == Counter(b):
        return "Possible"
    else:
        return "Impossible"

N = int(input())

for _ in range(N):
    a, b = input().split()
    print(is_same(a, b))

• counter 모듈을 불러와서 구현 2의 코드를 쉽게 만들 수 있음.