[JAVA] 놀라운 문자열_1972

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

1972번: 놀라운 문자열

 

 

 

 

놀라운 문자열 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

1359

771

633

58.665%

문제

대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문자열의 D-쌍이라고 한다. 예를 들어 문자열이 ZGBG라고 하자. 이 문자열의 0-쌍은 ZG, GB, BG가 되고, 이 문자열의 1-쌍은 ZB, GG가 되며, 이 문자열의 2-쌍은 ZG가 된다. 문자열의 길이가 N이라고 할 때, 0-쌍부터 (N-2)-쌍까지가 정의됨을 알 수 있다.

만일 정의되는 D에 대해, 어떤 문자열의 모든 D-쌍들이 서로 다를 때, 이 문자열을 D-유일하다고 한다. 위의 예를 보면, 0-쌍들은 ZG, GB, BG로 모두 다르다. 따라서 이 문자열은 0-유일하며, 마찬가지로 1-유일하고, 2-유일하다. 하지만 만일 문자열이 AAA라고 하자. 이 문자열은 0-유일하지 않으며, 다만 1-유일하다.

만일 어떤 문자열이 정의되는 모든 D에 대해 D-유일하면, 이 문자열을 정말이지 ‘놀라운 문자열’이라고 한다. 문자열이 주어질 때, 이 문자열이 놀라운 문자열인지 아닌지를 구하는 프로그램을 작성하시오.

입력

입력의 각 줄에는 알파벳 대문자로만 구성된 문자열이 주어진다. 모든 문자열의 길이는 80을 넘지 않으며, 입력의 마지막 줄에는 마지막을 나타내는 *가 주어진다. 입력은 마지막 줄을 포함해서 101줄을 넘지 않는다.

출력

각 줄에 이 문자열이 놀라운(surprising) 문자열인지 아닌지를 아래의 예제와 같이 출력한다.

예제 입력 1 복사

ZGBG
X
EE
AAB
AABA
AABB
BCBABCC
*

예제 출력 1 복사

ZGBG is surprising.
X is surprising.
EE is surprising.
AAB is surprising.
AABA is surprising.
AABB is NOT surprising.
BCBABCC is NOT surprising.

출처

ICPC > Regionals > North America > Mid-Central Regional > 2006 Mid-Central Regional Programming Contest C번

알고리즘 분류

• 구현
• 자료 구조
• 문자열
• 해시를 사용한 집합과 맵

 

 

 

---

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main
{
    private static Scanner s = new Scanner(System.in);
    
    // 공통 변수 선언
    private static String SURPRISE = "is surprising.";
    private static String NOT_SURPRISE = "is NOT surprising.";
    private static String SPACE = " ";
    
    public static void main(String[] args) {
    	
    	// 출력할 결과물 리스트
    	List<String> output = new LinkedList<>();
    	
    	while(true) {
    		// *이 나올 떄까지 계속 입력
    		String input = s.next();
    		if("*".equals(input)) {
    			break;
    		}
    		
    		Set<String> dArrList;
    		Boolean isSurprise = true;
    		for(int i=0; i<=input.length()-2; i++) {
    			dArrList = new HashSet<String>();
    			for(int j=0; j<input.length()-i-1; j++) {
    				int tmpSize = dArrList.size();
    				String str = input.charAt(j) + "" + input.charAt(j+i+1);
    				dArrList.add(str);
    				
    				// SET의 사이즈가 동일하면 (같은 문자가 입력되었으면) 종료
    				if(dArrList.size() != tmpSize+1) {
    					isSurprise = false;
    					break;
    				}
    				
    			}
    			if(!isSurprise) break;
    		}

    		// 연산 결과에 따른 결과값 저장
			StringBuffer str = new StringBuffer();
    		if(isSurprise) {
    			str.append(input).append(SPACE).append(SURPRISE);
    		}
    		else {
    			str.append(input).append(SPACE).append(NOT_SURPRISE);
    		}
    		output.add(str.toString());
    	}
    	
    	// 결과 출력
    	for(String str : output) {
    		System.out.println(str);
    	}
    	
    }
}