[백준] 1316번 : 그룹 단어 체커 - JAVA [자바]

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

1316번: 그룹 단어 체커

---

• 문제

 

※ 주의할 점

1. 문자열의 문자가 연속되지 않으면서 이미 앞서 해당 문자가 입력된 적이 있을 경우 그룹 단어가 아니다.
2. 그룹 단어의 개수를 출력해야한다.

---

• 2가지 입력방법을 이용하여 풀이한다.

 

알고리즘 설명에 앞서 대강 2가지 풀이 방법을 이용하여 보여주려고 한다.

 

1. 가장 기본적인 입력방법인 Scanner 방법.

2. BufferedReader 을 이용하여 풀이하는 방법.

 

이렇게 2 가지로 나눌 것이다.

---

• 알고리즘

 

이 문제는 함수를 만드는 것이 가장 보기 편할 것이다.

그래서 main 함수와 그룹 단어를 체크하는 함수를 만들 것이다.

 

그래서 크게 두 가지로 나누어서 설명하려 한다.

 

그리고 가장 중요한 점은 어디까지나 "의사코드"다. 

즉 간략화 하여 풀이하는 것이므로 이 점 유의하길 바란다.

 

 

 

 

 

[ check ]

 

1. 그룹 단어를 체크할 함수다.

단어가 입력되면 해당 문자열이 그룹 단어인지 아닌지만 따지면 되기 때문에 return 타입은 boolean 으로 한다.

 

boolean check() {

}

 

 

 

2. 그리고 26 개의 단어를 체크 할 길이 26의 boolean 배열을 선언하고 문자열을 입력받는다.

 

또한 알고리즘에서 가장 중요하게 작용할 변수 prev 를 생성한다.

prev 의 역할은 이후 반복문에서 문자를 꺼내올 때 앞선 문자와 연속되는지, 아닌지를 판별하기 위함이다.

 

즉, 아래와 같이 돌아가도록 할 것이다.

 

prev 의 문자와 해당 문자가 같다면? 

→ 해당 문자가 중복된 문자인지 여부를 검사하지 않는다. (boolean 배열)

 

prev 의 문자와 해당 문자가 다르다면? 

→ 해당 문자가 중복된 문자인지 여부를 검사한다. (boolean 배열)

 

 

위와 같은 역할을 할 수 있도록 변수들을 선언해주자.

 

boolean check() {
	boolean[] check = new boolean[26];
	int prev = 0;
	String str = input();
}

 

 

 

3. 입력받은 문자열을 이제 하나씩 꺼내서 그룹 단어인지 아닌지를 검사해야한다.

이를 위해 문자열의 길이만큼 반복문을 써주자.

 

boolean check() {
	boolean[] check = new boolean[26];
	int prev = 0;
	String str = input();
    
	for (int i = 0; i < str.length; i++) {

	}
}

 

 

 

4. 이제 반복문 안에 charAt( ) 을 통해 문자열의 문자들을 하나씩 꺼내와서 해당 단어가 prev 의 값과 같은지 판별해준다.

 

이때 앞서 설명한 것처럼 조건문을 써야한다.

 

prev 의 문자와 해당 문자가 같다면? 

→ 해당 문자가 중복된 문자인지 여부를 검사하지 않는다. (boolean 배열)

 

prev 의 문자와 해당 문자가 다르다면? 

→ 해당 문자가 중복된 문자인지 여부를 검사한다. (boolean 배열)

 

말로 설명하면 이해하기 힘드니 일단 코드를 보자.

 

boolean check() {
	boolean[] check = new boolean[26];
	int prev = 0;
	String str = input();
    
	for (int i = 0; i < str.length; i++) {
		int now = str.charAt(i); 	// i 번째 문자 저장 (현재 문자)
        
        
		// 앞선 문자와 i 번째 문자가 같지 않다면?
		if (prev != now) {		
			
			// 해당 문자가 처음 나오는 경우 (false 인 경우)
			if ( check[now - 'a'] == false ) {
				check[now - 'a'] = true;		// true 로 바꿔준다
				prev = now;					// 다음 턴을 위해 prev 도 바꿔준다 
			}
 
			// 해당 문자가 이미 나온 적이 있는 경우 (그룹단어가 아니게 됨) 
			else {
				return false;	//함수 종료
			}
		}
        
        
		// 앞선 문자와 i 번째 문자가 같다면? (연속된 문자)
		// else 문은 없어도 됨
		else {
			countinue;
		}
	}
    
    
	return true;
}

 

 

 

설명을 조금 더 해보자면

 

일단 prev 문자와 검사할 문자인 now 가 다른 경우 (비연속 문자인 경우),

즉 이전의 문자와 현재 문자가 다른 경우에 check 배열에서 해당 문자가 중복되는지를 살펴보는 것이다.

 

예로들어 a a b a 라는 문자를 입력받아고 생각해보자.

 

맨 처음 'a' 는 int 값으로 97 이니 처음 prev 초기값 0 하고는 다르므로 check[0] 배열에 true 로 바뀌게 된다.

( 참고로 boolean 배열은 디폴트 값(초기값)이 false 다. )

또한 prev 도 97 ('a') 로 바뀐다.

 

 

그리고 다음문자는 'a' 다.

이 때 prev 와 'a' 는 97 로 같기 때문에 아무 일도 없이 건너뛴다.

 

 

다음 문자는 'b' 다.

이 때 prev 와 'b' 는 서로 다른 값이므로 조건문을 실행하게 된다.

check[1] 은 false 이므로 해당 원소를 true 로 바꾸어 주고, prev 또한 98 ('b') 로 바뀌게 된다.

 

마지막 문자는 'a' 다.

prev 에는 98 이 저장되어 있고, 'a' 는 97 이므로 서로 다른 값을 갖고 있기에 조건문을 실행시키게 된다.

이 때 check[0] 은 이미 true 다. 즉, 앞서 이미 나온 적이 있는 문자이기 때문에 그룹 단어가 아니므로 바로 함수를 종료시키고 false 를 return 하는 것이다.

---

[ main ]

 

1. 메인에서는 먼저 그룹단어 개수를 셀 count 변수를 생성한다.

또한 N 을 받고 그룹 단어 체크 함수를 N 번 돌릴 것이기 때문에 반복문을 써줄 것이다.

 

main() {
	int count = 0;
	int N = input();
	for (int i = 0; i < N; i++) {
	}
}

 

 

 

2. 그리고 check 메소드를 호출하여 만약 check 메소드가 true 라면 count 를 1 증가시킨다.

그리고 반복문이 끝나면 count 변수를 출력한다.

 

main() {
	int count = 0;
	int N = input();
	for (int i = 0; i < N; i++) {
		if (check() == true) {
			count++;
		}
	}
    
	print(count);
}

 

 

이렇게 하면 알고리즘이 완성된다.

 

아무래도 의사코드로 작성되다보니 이해가 안될 것이다.

아래 완성된 코드를 보자.

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {

	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {

		int count = 0;
		int N = in.nextInt();

		for (int i = 0; i < N; i++) {
			if (check() == true) {
				count++;
			}
		}
		System.out.println(count);
	}

	public static boolean check() {
		boolean[] check = new boolean[26];
		int prev = 0;
		String str = in.next();
		
		for(int i = 0; i < str.length(); i++) {
			int now = str.charAt(i);	// i 번째 문자 저장 (현재 문자)
			
			
			// 앞선 문자와 i 번째 문자가 같지 않다면?
			if (prev != now) {		
				
				// 해당 문자가 처음 나오는 경우 (false 인 경우)
				if ( check[now - 'a'] == false ) {
					check[now - 'a'] = true;		// true 로 바꿔준다
					prev = now;					// 다음 턴을 위해 prev 도 바꿔준다 
				}
	 
				// 해당 문자가 이미 나온 적이 있는 경우 (그룹단어가 아니게 됨) 
				else {
					return false;	//함수 종료
				}
			}
	        
	        
			// 앞선 문자와 i 번째 문자가 같다면? (연속된 문자)
			// else 문은 없어도 됨
			else {
				continue;
			}
		}    
		return true;
	}
}

 

 

가장 기본적인 방법이다.

 

그리고 주의할 점!

메인 함수와 check 함수에서도 Scanner 을 쓰므로 반드시 main 함수 밖에 전역 변수로 static 을 붙여 Scanner 을 생성해주어야 한다.

 

또한 문자열을 입력받을 때 nextLine() 을 쓰면 에러 난다. (개행이 버퍼에 남아있어서 다음 입력때 개행이 str 에 저장된다.)

---

- 방법 2 

 

 

BufferedReader 을 쓰는 방식이다.

 

그리고 반드시 자료형 타입을 잘 보아야 한다.

br.readLine() 은 문자열로 데이터를 읽으니 반드시 꺼내서 쓸 때 int 형으로 쓰고자 한다면 Integer.parseInt()로 String 을 int 형으로 변환시켜준다.

 

또한 BufferedReader 은 예외로 IOException 을 던지므로 반드시 입력이 들어가는 함수 ( main, check ) 옆에 throws IOException 을 써주어야 한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException{

		int count = 0;
		int N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			if (check() == true) {
				count++;
			}
		}
		System.out.println(count);
	}

	public static boolean check() throws IOException {
		boolean[] check = new boolean[26];
		int prev = 0;
		String str = br.readLine();
		
		for(int i = 0; i < str.length(); i++) {
			int now = str.charAt(i);	// i 번째 문자 저장 (현재 문자)
			
			
			// 앞선 문자와 i 번째 문자가 같지 않다면?
			if (prev != now) {		
				
				// 해당 문자가 처음 나오는 경우 (false 인 경우)
				if ( check[now - 'a'] == false ) {
					check[now - 'a'] = true;		// true 로 바꿔준다
					prev = now;					// 다음 턴을 위해 prev 도 바꿔준다 
				}
	 
				// 해당 문자가 이미 나온 적이 있는 경우 (그룹단어가 아니게 됨) 
				else {
					return false;	//함수 종료
				}
			}
	        
	        
			// 앞선 문자와 i 번째 문자가 같다면? (연속된 문자)
			// else 문은 없어도 됨
			else {
				continue;
			}
		}    
		return true;
	}
}

 

 

위 코드를 실행하면 Scanner 보다 BufferedReader 가 속도가 빠르다.

 

그리고 코드를 조금 가다듬는다면 아래와 같이 쓸 수 있겠다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		int count = 0;
		int N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			if (check()) {
				count++;
			}
		}
		System.out.print(count);
	}

	public static boolean check() throws IOException {
		boolean[] check = new boolean[26];
		int prev = 0;
		String str = br.readLine();
		
		for(int i = 0; i < str.length(); i++) {
			int now = str.charAt(i);
			
			
			if (prev != now) {		
				if (!check[now - 'a']) {
					check[now - 'a'] = true;
					prev = now;	
				}
				else {
					return false;	
				}
			}
		}    
		return true;
	}
}

 

---

• 성능 차이

 

위에서 부터 순서대로

 

채점 번호 : 18703404  -  BufferedReader

채점 번호 : 18703394  -  Scanner

 

확실히 Scanner 와 BufferedReader 의 차이는 어마어마하다.

 

또한 메모리도 아낄 수 있어 여러모로 좋다.

 

---

• 정리

 

이로써 백준의 문자열 카테고리는 끝이다.

 

아마 이 파트를 배우면서 가장 많이 배울 수 있는 점이라면

BufferedReader 와 문자의 값일 것이다.

 

흔히들 문자의 값을 아스키코드값이라고 하는데, 정확하게 말하자면 0 ~ 127 번까지는 거의 같을 뿐 아스키 코드 값은 아니다.

UTF-8, UTF-16, MS949 등 각자 시스템에서 설정되어있는 인코딩의 값이다.

 

그러나 흔히 쓰는 숫자와 영어는 코드 값이 같아서 흔히 아스키코드라고 대치해서 부르는 것 같다.

 

 

아무래도 개발 언어들은 영어권 문화에 가깝다보니 영어권 사람들은 딱히 불편할 일은 없지만, 한글을 쓰는 우리나라는 그 입장이 완전히 다르니 만약에 한글을 int 값으로 반환하려고 한다면 인코딩이 무엇으로 되어있는지 잘 살펴보고 유의해서 써야한다.