1018: 문자열 거리 최소화 하기

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

---

1. 문제

• N의 두 문자열 X, Y 가 주어졌을 때 두 문자열의 거리는, 같은 위치의 서로 다른 문자의 수로 정의한다.
  즉, Distance(X, Y) = Sum(f(i)) (i = 0..N-1)
          f(i) = 1,  if X[i] != Y[i]
          f(i) = 0,  if X[i] == Y[i]
  예를 들어, "ant" 와 "art" 의 거리는 1 이다.
  
  두 문자열 A, B가 주어진다고 하자. 이 때, A의 길이는 B보다 짧거나 같다.
  당신은 A의 길이가 B와 같아질 때까지 다음 동작을 수행할 수 있다.
  
      - 임의의 문자 C를 선택하여 A의 앞에 붙인다.
      - 임의의 문자 C를 선택하여 A의 뒤에 붙인다.
  
  위의 연산을 적용하여 A의 길이를 B와 같게 만들고자 하는데 이 때,두 문자열의 거리를 최소화 하고자 한다.

 

---

2. 문제의 조건

• A <= B <= 50 (각 문자열의 길이)

 

---

3. 문제 접근

•  시간 복잡도
  
  시간제한 1초에 각 문자열의 길이는 50이하이므로 O(N^4)이내의 시간에 해결하면 된다고 생각합니다.

 

• 아이디어
  
  아래의 표를 보시면됩니다.

0	1	2	3	4	5	6	7
k	o	d	e	r
t	o	p	c	o	d	e	r
	k	o	d	e	r
t	o	p	c	o	d	e	r
		k	o	d	e	r
t	o	p	c	o	d	e	r
			k	o	d	e	r
t	o	p	c	o	d	e	r

A의 첫 idx 0인 "k"는 B의 "t" "o" "p" "c"와 비교를하고 A의 idx 1인 "o"는 B의 "o", "p", "c", 'o" 와 비교를합니다.
이런식으로 총 len(B) - len(A) + 1 만큼 탐색을 진행합니다. 이 때, 같으면 서로의 위치 차이 번째의 배열을 1 증가시키면 됩니다.

즉, len(A) ^ 2 + (len(B) - len(A) + 1) 만큼 수행하므로 O(N^2)의 시간복잡도가 됩니다.

 

---

4. 풀이 방법

• len(B) - len(A) + 1 크기의 배열을 만들어줍니다.
• len(A)를 기준으로 B[idx:A] 시작으로 len(B) - len(A) + 1 만큼 탐색을 합니다.
• 만약 같은 문자열이 존재하면 해당 위치 차이에 해당하는 배열을 arr[distance]++ 합니다.
• len(A) - max(arr) 가 곧 전체적인 문자열의 위치 차이가 됩니다.

 

---

5. 소스코드

• cjw-git.tistory.com/26

 

---

 

cjw.git@gmail.com