11328번 -Strfry

💡 시간복잡도와 공간복잡도를 시작전에 확인 후 설계를 짜자

<오답 코드>

from itertools import permutations

N = int(input())

for _ in range(N):
    
    flag = 0
    
    first, second = input().split(' ')
        
    result = permutations(first, len(first))
    
    for val in result:
        if second == ''.join(val):
            flag = 1
    
    if flag == 0:
        print("Impossible")
    else:
        print("Possible")

• 이런 문제를 보면 왜이렇게 조합,순열으로 풀고싶은지..ㅎ 뭔가 배운 걸 써먹고 싶다..ㅋㅋㅋ
• 가능한 모든 경우의 수에서 비교해야 하다보니 순열을 사용해서 풀었고, 제출해보니 시간초과가 발생했다 (사실 그럴 수 밖에 없다.. 시간 제한은 2초 즉 2억번 정도 돌 수 있는데 0 < N < 1001 이므로 최악의 경우는 N이 1000일 때인데, 1000!이니 2억번은 어림도 없었다..ㅎ)

<정답 코드>

N = int(input())

for _ in range(N):
    
    first, second = input().split(' ')

    if sorted(first) == sorted(second):
        print("Possible")
    else:
        print("Impossible")

• 곰곰히 생각해보니, 굳이 어렵게 접근할 필요가 없었다
• 결국 문제에서는 2번째로 들어오는 것을 1번째 들어오는 str의 요소들로 만들 수 있냐??를 물어보는 것이였다.
• 결국은 first와 second의 구성 요소가 동일하면 항상 만들 수 있었다.
• 그래서 sorted()함수를 사용해서 정렬 후 두 리스트를 비교하여 해답을 얻을 수 있었다.👍🏻

💡 코딩스터디 중 기발한 접근 방법

• 우진님
  sorted()는 O(nlon)이므로, 통구현 or Counter()를 사용하면 O(n)이기 때문에 이거를 이용하는 방식이 좋다.
  Counter()를 사용하면, 내부의 모든 요소를 1번만 순회하면서 갯수를 세어주니 sorted()보다는 훨씬 빠르다.

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input().strip())
for _ in range(n):
    str1, str2 = input().split()
    # Counter 객체로 각 문자의 빈도수를 한 번에 계산
    print("Possible" if Counter(str1) == Counter(str2) else "Impossible")