사용자 도구

사이트 도구


ps:problems:boj:11328

Strfry

ps
링크acmicpc.net/…
출처BOJ
문제 번호11328
문제명Strfry
레벨브론즈 2
분류

기초

시간복잡도O(t*n)
인풋사이즈t<=1000, n<=1000
사용한 언어Python
제출기록32148KB / 136ms
최고기록84ms
해결날짜2021/12/23

풀이

  • 두 스트링이 같은 글자들을 포함하는지를 비교하면 된다.
  • 쉬운 방법은 각각 스트링을 정렬한 다음에 일치하는지 보는 것이고, 다른 방법은 글자들마다 갯수를 세어서 그것을 비교하는 것이다. 전자는 정렬을 해야 하니 O(nlogn)이 걸리지만 후자는 O(n)으로도 가능하다.

코드

"""Solution code for "BOJ 11328. Strfry".

- Problem link: https://www.acmicpc.net/problem/11328
- Solution link: http://www.teferi.net/ps/problems/boj/11328
"""

import collections
import sys


def main():
    N = int(sys.stdin.readline())
    for _ in range(N):
        str1, str2 = sys.stdin.readline().split()
        counter1 = collections.Counter(str1)
        counter2 = collections.Counter(str2)
        print('Possible' if counter1 == counter2 else 'Impossible')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I Q K D A
 
ps/problems/boj/11328.txt · 마지막으로 수정됨: 2021/12/23 12:38 저자 teferi