글 작성자: ST_
728x90




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

 

1316번: 그룹 단어 체커

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

www.acmicpc.net







  • 문제





 

※ 주의할 점

  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 값으로 반환하려고 한다면 인코딩이 무엇으로 되어있는지 잘 살펴보고 유의해서 써야한다.




저작자표시 비영리 변경금지

'JAVA - 백준 [BAEK JOON] > 문자열' 카테고리의 다른 글

[백준] 2941번 : 크로아티아 알파벳 - JAVA [자바]  (31) 2020.03.25
[백준] 5622번 : 다이얼 - JAVA [자바]  (29) 2020.03.24
[백준] 2908번 : 상수 - JAVA [자바]  (12) 2020.03.20
[백준] 1152번 : 단어의 개수 - JAVA [자바]  (33) 2020.03.20
[백준] 1157번 : 단어 공부 - JAVA [자바]  (42) 2020.03.19

댓글

댓글을 사용할 수 없습니다.

티스토리툴바