[SWEA] 7853. 오타

문제

방송사에서 생방송 자막 송출을 담당하고 있는 재경이는 한글 타자가 무려 1000에 육박한다.

누구보다 빠른 한글 타자를 보유하고 있지만 치명적인 단점이 있다. 영어 타자의 오타가 극심하게 발생한다.

재경이는 어떤 단어를 쓸 때에 오타를 특정한 방법으로 발생시킨다.

치고자 하는 단어와 길이는 동일한 단어를 쓰지만, i번째 문자에다가 원래 단어의 (i-1) 번째, i 번째, (i+1) 번째 문자 중 무엇이든 쳐버린다.

특히 제일 첫 문자는 첫 문자와 그 다음 문자 중 하나를 쓸 수 있고, 마지막 문자는 마지막과 그 앞의 문자를 쓸 수 있다.

예를 들어서, apa 라는 단어에서 재경이가 낼 수 있는 오타는 aaa, aap, apa, app, paa, pap, ppa, ppp 중 하나를 칠 수 있는 것이다.

단어가 주어졌을 때에 재경이가 칠 수 있는 서로 다른 단어의 개수를 구하여라.

 

풀이방법

DFS(깊이 우선 탐색)으로 모든 경우의 수를 구했다가 시간초과가 발생했다.

 

요즘들어서 문제를 제대로 읽지도 않고, DFS, BFS, DP를 우선적으로 사용할 생각을 하는 것 같다.

 

친한 친구가 매번 해주었던 말이 생각났다.

 

"Simple is best!"

 

문제가 주어졌을 때 가장 간단하면서도 최적의 알고리즘을 선택하는 능력이 필요하다.

 

DFS를 사용해 시간초과가 발생하고 나서 문제를 제대로 읽어볼 수 있었다.

 

반복문을 한 번 돌려 각 문자에서 존재할 수 있는 모든 경우의 수를 곱해주기만 하면 되는 문제였다.

 

단, 각 문자에서 발생하는 경우의 수는 조건이 따른다.

 

주어진 문자열을 a[i]라고 했을 때, 각 경우의 수는

 

i=0일 때,

a[i] != a[i+1] 일 경우 : 2

a[i] == a[i+1] 일 경우 : 1

 

i=n-1일 때,

a[i-1] != a[i] 일 경우 : 2

a[i-1] == a[i] 일 경우 : 1

 

나머지

a[i-1] == a[i+1]이면서 a[i] != a[i-1]일 경우 2

a[i-1] != a[i+1]이면서 a[i-1] == a[i] 또는 a[i+1] == a[i]일 경우 2

a[i-1] != a[i] != a[i+1]일 경우 3

a[i-1] == a[i] == a[i+1]일 경우 1 

 

소스코드

package samsung;

import java.util.*;

public class s_7853 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			String s = sc.next();
			long cnt = 1;
			int n = s.length();
			
			for(int i = 0; i < n; i++) {
				int r = 1;
				if(i == 0) {
					if(s.charAt(i) != s.charAt(i + 1)) r++;
				}
				else if(i == n - 1) {
					if(s.charAt(i - 1) != s.charAt(i)) r++;
				}
				else {
					if(s.charAt(i - 1) != s.charAt(i)) r++;
					if(s.charAt(i) != s.charAt(i + 1)) r++;
					if(r > 1 && s.charAt(i - 1) == s.charAt(i + 1)) r--;
				}
				cnt *= r;
				cnt %= 1000000007;
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}