빙글빙글

https://www.acmicpc.net/problem/17998

1. 문자열의 아무 곳에나 문자를 추가.
2. 문자열 내 어느 곳에서든 문자를 제거.
3. 문자열의 문자를 다른 문자로 변경.

3가지 방법에서 만들어진 문자열을 사전순으로 출력하면 되는 문제이다.

중복 없이 출력해야하므로 Set을 이용하는 것이 좋아보인다.

하지만 틀렸대요!!!!!!! 왜?

for(int j=0;j<a.length();j++) {
		for(int i=0;i<b.length();i++) {
			StringBuilder sb = new StringBuilder();
            //끼워 넣기
			sb.append(b.substring(0, i)+a.charAt(j)+b.substring(i,b.length()));
			aa.add(sb.toString());
			sb= new StringBuilder();
            //변경 하기
			sb.append(b.substring(0, i)+a.charAt(j)+b.substring(i+1,b.length()));
			aa.add(sb.toString());
		}
	}

위 코드 때문이다.

끼워 넣기 부분 무언가 수상한 것이 보이지 않나요...

맞습니다 바로 맨마지막에 끼워넣기를 하는 경우가 더해지지 않았던 것..!!

예) ab

cde

를 입력하면 cdea 혹은 cdeb가 나오지 않았다는 점.

aa.add(b+a.charAt(j));

반복문 끝에 맨 마지막에 문자열을 끼워넣는 경우를 추가하여 통과하였다.

트리맵으로 하면 시간이 너무 오래걸릴까봐 그냥 Set으로 진행하였는데 문제의 조건을 보니 TreeSet을 이용해도 충분했을 것 같다.

Ğ̎ĭ̎t̆̎H̆̎ŭ̎b̆̎ :  https://github.com/YunYunYY/Algorithm/tree/eb566eb18e5d769019db9e0a0406a3fd856b5a68/%EB%B0%B1%EC%A4%80/Silver/17998.%E2%80%85Levenshtein%E2%80%85Distance

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;


public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String a = bf.readLine();
		String b = bf.readLine();
		HashSet<String> aa = new HashSet<String>();
		for(int j=0;j<a.length();j++) {
			for(int i=0;i<b.length();i++) {
				StringBuilder sb = new StringBuilder();
				sb.append(b.substring(0, i)+a.charAt(j)+b.substring(i,b.length()));
				aa.add(sb.toString());
				
				sb= new StringBuilder();
				sb.append(b.substring(0, i)+a.charAt(j)+b.substring(i+1,b.length()));
				aa.add(sb.toString());
			}
			aa.add(b+a.charAt(j));
		}
		for(int i=0;i<b.length();i++) {
			StringBuilder sb = new StringBuilder();
			sb.append(b.substring(0, i)+b.substring(i+1,b.length()));
			aa.add(sb.toString());
		}
		if (aa.contains(b))
			aa.remove(b);
		Object[] bb = aa.toArray();
		Arrays.sort(bb);
		
		for(Object i : bb)
			System.out.println(i);

	}
	
}