1116: 짝궁 문자열

Link : judge.koreatech.ac.kr/problem.php?id=1116

---

1. 문제

• 영어 단어들을 보던 당신은 비슷한 영어 단어들이 있다는 사실을 깨닫게 되었습니다. 너무 비슷하여서 두 개의 알파벳을 서로 바꾸면 같은 단어가 되는 단어들이 있다는 것들도 알게 되었죠. 예를 들어 cat과 act는 a와 c의 자리만 바꾸면 서로 같은 단어가 됩니다.
  이런 단어들, 즉 반드시 한 쌍을 교환 했을 때 같아지는 문자열을 짝궁 문자열이라고 이름을 붙이게 되었습니다. 아래와 같은 단어들이 짝궁 단어들의 예제입니다.
  ab, ba
  cat, act
  aa, aa
  abcdef, abcdfe
  
  하지만 아래와 같은 쌍은 짝궁 단어들이 아닙니다.
  abc, cab
  a, abc
  입력으로 주어진 단어 쌍이 짝궁 문자열인지 아닌지를 출력하는 함수를 만들어 주세요.

 

---

2. 문제의 조건

• 1 <= T <= 100
• 1 <= A, B <= 2000

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 대략 200,000의 문자열이니 약 O(N)에 풀어야한다고 생각하였습니다.

 

• 아이디어
  
   "한쌍"만 바꾸면 값이 같아지는 "짝"이 되므로 서로 다른 값에 대해서만 추출을 하고, 그 값만을 비교하면 알게 됩니다.
  
  

  예시로 abcdef와 afcdeb는

  a	b	c	d	e	f
  a	f	c	d	e	b

  빨간색 부분만 다르므로 (b, f), (f, b)를 추가한 다음

  	0	1
  0	b	f
  1	f	b

  같은 색깔끼리 비교하여 같으면 yes 다르면 no가 되는 것입니다.
  
  즉, O(N) 이내의 시간에 해결할 수 있습니다.

 

---

4. 풀이 방법

• A와 B가 길이가 같은지 확인한다.(다르면 no)
• A[idx] 와 B[idx]가 다르다면 리스트에 추가해줍니다.
• 만약 리스트의 크기가 0이라면 (모두 다 같다는 의미) yes를 출력하고
         리스트의 크기가 2라면 (2개만 다르다는 의미) -> 다음으로
         리스트의 크기가 0도, 2도 아니라면 틀린게 1개 or 3~ 이므로 한쌍만 바꿔선 짝이 될 수 없으므로 no를 출력합니다.
• 리스트의 크기가 2라면 원소 [0][0]과 [1][1] 와 같고 [0][1]과 [1][1]이 같으면 yes를 반환하고 다르다면 짝이 될 수 없으므로 no를 반환합니다.
  
  
  

 

 

---

5. 소스코드

• cjw-git.tistory.com/63

 

---

 

cjw.git@gmail.com