Funcia
Lv.1hashstring

글자 바꿔 치기 암호

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

어떤 암호는 원문의 글자마다 정해진 다른 글자로 바꿔서 만듭니다. 규칙은 다음과 같습니다.

  • 같은 글자는 언제나 같은 글자로 바뀝니다.
  • 서로 다른 두 글자가 같은 글자로 바뀔 수는 없습니다.
  • 글자가 자기 자신으로 바뀌어도 됩니다.

같은 길이의 문자열 s와 t가 주어질 때, 이런 규칙으로 s를 바꿔서 t를 만들 수 있으면 true, 없으면 false를 반환하세요.

입출력 예

stresult
"egg""add"true
"foo""bar"false
"badc""baba"false

입출력 예 설명

예 1 — e → a, g → d로 바꾸면 됩니다.

예 2 — o가 한 번은 a, 한 번은 r로 바뀌어야 하므로 불가능합니다.

예 3 — b → b, d → b처럼 서로 다른 두 글자 b와 d가 모두 b로 바뀌어야 하므로 불가능합니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(s: string, t: string) → bool

제한 사항

  • 1≤1 \le s.length == t.length ≤200,000\le 200{,}000
  • s와 t는 영어 대소문자와 숫자로만 이루어져 있습니다. 대문자와 소문자는 다른 글자입니다.

기대 복잡도

시간
O(N)
공간
O(alphabet)

입출력 예

st기대 출력
"egg""add"true
"foo""bar"false
"badc""baba"false

힌트

힌트

두 방향의 대응표를 만드세요.

  • fwd[x]: s의 글자 x가 바뀌는 글자
  • back[y]: t의 글자 y가 되기 전의 글자

i를 앞에서부터 보면서 fwd[s[i]]가 비어 있으면 t[i]로 정하고, 이미 정해져 있는데 t[i]와 다르면 false입니다. back도 같은 방식으로 검사합니다. 한 방향만 검사하면 예 3처럼 두 글자가 한 글자로 합쳐지는 경우를 놓칩니다.

글자 종류가 많지 않으므로 크기 128(ASCII)인 배열을 대응표로 쓰면 충분합니다.

복잡도 목표

모든 위치 쌍 (i, j)에 대해 "s에서 같으면 t에서도 같은지" 확인하면 O(N2)O(N^2)으로 시간 초과입니다. 대응표를 쓰면 O(N)O(N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.