(JAVA) 백준 1972번 : 놀라운 문자열

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

1972번: 놀라운 문자열

 

정말 놀라운 문자열 문제이다..!

 

문제를 요약하자면

 

n개의 문자로 이루어진 문자열을 입력받았을 때

이 문자열의 문자 하나와 그 문자에서 1 ~ n-1 칸 건너 있는 문자를 합친 쌍들의 문자들 중 같은 두 문자가 있으면 놀라지 않는 문자열이고, 쌍의 종류 전부에서 같은 문자가 하나도 없으면 놀라운 문자열이다.

 

그럼 어떻게 푸느냐..

 

내가 생각한 방법과

다른 굇수님의 방법이 있다.

 

내가 생각한 방법은 하단 소스 코드를 보면 알겠지만

 

 1) 쌍의 종류마다 쌍에 해당하는 모든 문자들을 ArrayList<String>에 넣고

 2) Collections.sort() 한다. => 그러면 정렬이 되면서 만약 같은 문자가 있으면 붙어진다.

 3) 이를 이용해서 버블 정렬 처럼 근접한 두 String을 비교한다. 

 4) 혹시 하나라도 같은 String이 있으면 놀라지 않는 문자열

 4-1) 하나라도 같은 String이 없으면 놀라운 문자열

 5) 결과 StringBuilder에 넣고 한번에 출력

 

이다.

이는 적당한 메모리와 적당한 시간을 소비했지만

 

다른 굇수님의 방법은 바로

HashSet을 사용하는 것이다!

HashSet은 중복된 원소가 존재하면 중복된 원소가 몇 개든 간에 하나만 존재한다.

 

이를 이용해서

 1) 쌍에 해당하는 문자를 HashSet에 넣을 때 마다 Counting을 한다.

 2) HashSet의 Size와 Counting한 갯수를 비교한다.

  -> Size가 다르면 중복된 String이 존재하므로 놀라지 않는 문자열이 된다!

 

HashSet이 훨씬 더 간단하면서도 메모리, 시간적 측면에서도 훨씬 좋다.

 

이 문제 덕분에 하나 배워간다.

 

소스 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

// 놀라운 문자열 문제
// 문자열 처리
// **** 다른 방법(이 방법이 더 좋음)
// ==> HashSet을 사용해서 중복 체크하기 -> 중복된 문자열은 하나만 가지므로 문자 하나씩 담을 때 마다 counting해서 hashSet의 size와 count 비교하면 됨.
public class p1972 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String inputStr;	// 입력받는 줄
		StringBuilder sb = new StringBuilder();
		while(!(inputStr = br.readLine()).equals("*")) {
			ArrayList<String> list = new ArrayList<String>();	// 각 쌍 별 나올 수 있는 문자를 담는 ArrayList
			int len = inputStr.length();	// 입력받은 문자열의 길이
			boolean isSurprise = true;	// 놀라운 문자열인지 아닌지 판별하는 boolean
			
			for(int i = 1; i < len; i++) {	// 0 ~ n - 2쌍 을 나타내는 값
				list.clear(); // 초기화해야지 다음 쌍 진행 가능
				for(int j = 0; j < len - i; j++) {	// 시작 인덱스
					String str = Character.toString(inputStr.charAt(j)) + Character.toString(inputStr.charAt(j + i));
//					String str = inputStr.charAt(j) + "" + inputStr.charAt(j + i);
					list.add(str);
				}
				// 같은 문자가 있는지 확인하기 위해 정렬 후 해당하는 인덱스의 문자와 바로 다음 인덱스의 문자를 비교한다
				Collections.sort(list);	
				for(int k = 0; k < list.size() - 1; k++) {
					if(list.get(k).equals(list.get(k + 1))) {
						isSurprise = false;
						break;
					}
				}
				if(!isSurprise) 
					break;	
			}
			
			if(isSurprise) {
				sb.append(inputStr).append(" is surprising.");
			}
			else {
				sb.append(inputStr).append(" is NOT surprising.");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
}

 

 

깃으로 소스코드 보기