11328 Strfry

1차 시도

import sys
n = int(input())

lst = [0] * n
idx = 0
b = True
for _ in range(n):
  i, j = sys.stdin.readline().rstrip().split()
  for k in i:
    if k not in j:
      lst[idx] = -1
      idx += 1
      b = False
      break
  if b:
    b = True
    idx += 1


for i in lst:
  if i == -1:
    print("Impossible")
  else:
    print("Possible")

not in을 사용해서 첫번째 문자열을 하나씩 뜯어서 두번째 문자열에 문자가 포함되는지 확인. 

포함 안되면 lst에 테스트 케이스대로 인덱스를 설정(테스트 케이스가 첫번째이면 idx=0)해서 -1을 넣어주고 포함되면 0.

 

틀려서 질문 게시판을 봤는데...

내가 생각해도 내 코드는 무식함. 해당 문자열이 같으면 문자열 정렬해서 동일한 문자열로 만들고 동일하지 않은 것만 찾으면 더 편할 것을...

 

2차 시도 (정답)

#1번째 문자열에 있는 문자가 2번째 문자열에도 있는가?
# 결국 모든 문자가 동일해야함 -> 입력받은 문자열을 정력해서 동일하면 됨.
import sys
n = int(input())
first = []
sec = []

for _ in range(n):
  i, j = sys.stdin.readline().rstrip().split()
  first.append("".join(sorted(i)))
  sec.append("".join(sorted(j)))


for i, k in zip(first, sec):
  if i != k:
    print("Impossible")
  else:
    print("Possible")

 

첫번째 문자열과 두번째 문자열을 정렬해서 각각 리스트에 넣음

그후 zip으로 튜플을 만들어서 비교

 

시간 복잡도와 공간 복잡도

시간 제한: 2초, 메모리 제한: 256MB

0 < n < 1001 이므로 

 

시간 복잡도: O(n)

공간 복잡도: 최대 1001개 요소를 포함한 문자열 리스트 가 2개있는 셈임.

int 기준으로 일반적으로 데이터의 개수가 1000만 단위가 넘어가지 않으면 됌.