[백준] 1157번 : 단어 공부 - JAVA [자바]

 

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

1157번: 단어 공부

---

• 문제

 

 

 

문자열 중 가장 중요한 것 중 하나가 바로 문자의 코드 값을 다룰 줄 아느냐다.

이 번 문제는 해당 개념을 이해하고 있다면 매우 쉬운 문제가 될 것이다.

※ 주의할 점

1. 가장 많이 반복된 문자가 2개 이상일 경우 ? 을 출력한다.
2. 대문자와 소문자의 구분은 없다.
3. 출력 문자는 대문자로 한다.

 

---

• 3가지 풀이방법을 제시한다.

 

먼저 가장 기본적인 Scanner 로 입력받아서 풀 것이다.

그리고는 BufferedReader 을 이용하여 풀 것인데 알고리즘을 Scanner 와 같은 것 하나와 다르게 구성한 것 하나. 이렇게 보여줄 것이다.

 

---

• 알고리즘

 

1. 먼저 문자열을 입력받기에 앞서 각 문자들의 빈도수를 나타내기 위한 배열을 하나 선언하고 문자열 s 를 입력받는다.

이때 배열의 0 번째 원소는 A 를 의미한다.

int[] arr = new int[26]; // 영문자의 개수는 26개임
String s = in.next();

 

2. 그리고 문자열 s 에 대하여 첫 번째 문자부터 마지막 문자까지 검사하기 위한 반복문을 작성해준다.

int[] arr = new int[26]; // 영문자의 개수는 26개임
String s = in.next();

for (int i = 0; i < s.length(); i++){}

 

 

3. 여기서 이제 중요한 포인트!

반복문을 돌면서 해당 문자가 어떤 문자냐에 따라 해당 배열 원소를 증가시켜주어야 한다.

이때 두 가지 케이스가 있는데, 대문자인 경우와 소문자인 경우가 있다.

 

하지만 문제에서 분명히 대소문자는 구분하지 않는다고 했으니 대문자로 입력 받던, 소문자로 입력받던 같은 배열 원소의 값을 증가시켜야 한다는 것이다.

 

예로들면 a 와 A 가 있을 때 배열 arr 원소 중 증가시켜야 할 인덱스는 arr[0] 으로 같다는 것이다.

 

그럼 인덱스(원소)는 어떻게 계산해야할까?

다음 표를 보자.

 

 

 

 

먼저 대문자의 범위는 십진수로 65~90 이다.

그리고 소문자의 범위는 97~122 이다.

 

즉 C 를 입력받았을 때, 배열의 세 번째 원소인 2 을 도출해내려면 C 는 67 이니 65 를 빼주면 된다.

만약 소문자 e 를 입력받았을 경우에는 다섯 번째 원소인 4 를 도출해야하니 97을 빼주면 101 - 97 = 4 로 배열의 인덱스 값을 도출할 수 있다.

 

즉, 아래와 같이 짜면 된다.

 

int[] arr = new int[26]; // 영문자의 개수는 26개임
String s = in.next();

for (int i = 0; i < s.length(); i++){

	if (65 <= s.charAt(i) && s.charAt(i) <= 90) { // 대문자 범위
		arr[s.charAt(i) - 65]++;	// 해당 인덱스의 값 1 증가
	}
    
	else {	// 소문자 범위
		arr[s.charAt(i) - 97]++;
	}

}

 

물론 65 나 97 의 숫자 대신 문자로 빼주어도 된다.

 

int[] arr = new int[26]; // 영문자의 개수는 26개임
String s = in.next();

for (int i = 0; i < s.length(); i++){

	if ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') { // 대문자 범위
		arr[s.charAt(i) - 'A']++;	// 해당 인덱스의 값 1 증가
	}
    
	else {	// 소문자 범위
		arr[s.charAt(i) - 'a']++;
	}

}

 

위와 같이 짜도 무방하다.

 

 

 

 

 

4. 모든 문자를 검사했으니 다음으로는 배열의 원소들의 값을 비교하여 가장 큰 값을 갖고있는 인덱스의 문자를 출력해야한다.

이를 위해 최댓값을 저장할 max 라는 변수를 선언하고, 출력할 문자 변수 ch 를 선언한다.

 

int[] arr = new int[26]; // 영문자의 개수는 26개임
String s = in.next();

for (int i = 0; i < s.length(); i++){

	if ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') { // 대문자 범위
		arr[s.charAt(i) - 'A']++;	// 해당 인덱스의 값 1 증가
	}
    
	else {	// 소문자 범위
		arr[s.charAt(i) - 'a']++;
	}
}


int max = -1;
char ch = '?';

 

 

5. 그리고 배열들을 순회하기 위한 반복문을 작성해준다.

int[] arr = new int[26]; // 영문자의 개수는 26개임
String s = in.next();

for (int i = 0; i < s.length(); i++){

	if ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') { // 대문자 범위
		arr[s.charAt(i) - 'A']++;	// 해당 인덱스의 값 1 증가
	}
    
	else {	// 소문자 범위
		arr[s.charAt(i) - 'a']++;
	}
}


int max = -1;
char ch = '?';

for (int i = 0; i < 26; i++) {}

 

 

6. 다음으로 조건문이 들어가야 한다.

 

해당 배열 원소 값이 max 보다 클 경우는 해당 원소값으로 max 를 대치해주고, ch 의 문자를 해당 인덱스에 대응하는 문자로 대치해야한다.

 

만약 배열 원소값이 max 값이랑 같을 경우 최대 개수의 문자가 2개 이상이라는 의미이므로 ch 를 물음표(?) 로 바꾸어 주어야 한다.

아래 코드를 보면 이해가 갈 것이다.

 

int[] arr = new int[26]; // 영문자의 개수는 26개임
String s = in.next();

for (int i = 0; i < s.length(); i++){

	if ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') { // 대문자 범위
		arr[s.charAt(i) - 'A']++;	// 해당 인덱스의 값 1 증가
	}
    
	else {	// 소문자 범위
		arr[s.charAt(i) - 'a']++;
	}
}


int max = -1;
char ch = '?';

for (int i = 0; i < 26; i++) {
	if (arr[i] > max) {
		max = arr[i];
		ch = (char) (i + 65); // 대문자로 출력해야하므로 65를 더해준다.
	}
	else if (arr[i] == max) {
		ch = '?';
	}
}

 

 

 

이렇게 짜고 마지막으로 ch 를 출력하면 코드가 완성된다.

 

그럼 전체 코드를 한 번 보자.

 

 

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int[] arr = new int[26]; // 영문자의 개수는 26개임
		String s = in.next();

		for (int i = 0; i < s.length(); i++){

			if ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') { // 대문자 범위
				arr[s.charAt(i) - 'A']++;	// 해당 인덱스의 값 1 증가
			}
    
			else {	// 소문자 범위
				arr[s.charAt(i) - 'a']++;
			}
		}


		int max = -1;
		char ch = '?';

		for (int i = 0; i < 26; i++) {
			if (arr[i] > max) {
				max = arr[i];
				ch = (char) (i + 65); // 대문자로 출력해야하므로 65를 더해준다.
			}
			else if (arr[i] == max) {
				ch = '?';
			}
		}

		System.out.print(ch);
	}

}

 

 

 

위의 알고리즘을 그대로 반영했다.

 

그리고 char 형 타입의 변수에 int 와 char 을 연산하여 저장할 경우 반드시 캐스팅을 해주어야 한다.

즉 ch = (char) (i + 65) 이런식으로 (char) 을 붙여 캐스팅을 해주어야 한다는 의미다.

 

---

- 방법 2 

 

다음 방법은 위의 알고리즘에서 Scanner 로 입력받는 방법이 아닌 BufferedReader 로 바꾸어서 입력받아보는 방법이다.

알고리즘은 방법 1 과 동일하게 구성된다.

 

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

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int[] arr = new int[26]; // 영문자의 개수는 26개임
		String s = br.readLine();
		

		for (int i = 0; i < s.length(); i++) {
			if ('a' <= s.charAt(i) && s.charAt(i) <= 'z') {
				arr[s.charAt(i) - 97]++;
			} else {
				arr[s.charAt(i) - 65]++;
			}
		}
		int max = -1;
		char ch = '?';
		for (int i = 0; i < 26; i++) {

			if (arr[i] > max) {
				max = arr[i];
				ch = (char) (i + 65);
			} 
			else if (arr[i] == max) {
				ch = '?';
			}
		}
		System.out.print(ch);
	}

}

 

 

단순히 입력방법만 바꿨다.

 

포스팅 마지막 부분에서 성능을 비교한 이미지를 보여줄 것이지만, 미리 말하자면 Scanner 와 BufferedReader 의 성능 차이는 꽤 크다.

---

- 방법 3 

 

 

이번에는 알고리즘을 조금 다르게 구성해보려고 한다.

굳이 문자열 변수를 만들지 말고 입력과 동시에 byte 값으로 반환하여 배열의 원소를 증가시키는 방법이다.

 

그리고 문자열은 항상 영문자만 입력받기 때문에 조건문 또한 매우 간소화 시켰다.

 

또한 배열을 순회하여 max 값을 찾으면서 문자를 저장할 때 최악의 경우 캐스팅을 26번 해주어야하므로 일단 int 값으로 저장한 뒤 마지막 출력에서만 캐스팅을 해주는 것으로 바꿀 것이다.

 

그리고 문자열만 입력받기 때문에 BufferedReader 가 필요 없다.

전의 포스팅에서 얘기하던 System.in.read() 로 입력받으면 된다.

 

이에 대해 궁금하다면 아래 포스팅을 참고하시길

 

https://st-lab.tistory.com/41?category=830901

JAVA [자바] - 입력 뜯어보기 [Scanner, InputStream, BufferedReader]

 

 

 

즉 위를 토대로 수정을 한다면 다음과 같이 짜면 된다.

 

import java.io.IOException;

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

		int[] arr = new int[26]; // 영문자의 개수는 26개임

		int c = System.in.read();

		while (c > 64) {	// 공백을 입력받는 순간 종료됨 
			
			if (c < 91) {
				arr[c - 65]++;
			} else {
				arr[c - 97]++;
			}
			c = System.in.read();
		}


		int max = -1;
		int ch = -2;	// ? 는 63 이다.

		for (int i = 0; i < 26; i++) {

			if (arr[i] > max) {
				max = arr[i];
				ch = i;
			} else if (arr[i] == max) {
				ch = -2;
			}
		}
		System.out.print((char) (ch+65));
	}

}

 

 

 

---

• 성능

 

 

위에서 부터 순서대로

 

채점 번호 : 18547027  -  System.in.read() ( 방법 3 )

채점 번호 : 18547020  -  BufferedReader ( 방법 2 )

채점 번호 : 18547011  -  Scanner ( 방법 1 )

 

 

이렇게 입력 방법에 따라서 메모리 차이 및 시간 차이가 확연하게 다르다는 것을 볼 수 있다.

---

• 정리

문제가 어렵지는 않았을 것이다.

필자의 코드가 정답은 아니지만 이만큼 다양한 방법이 있다는 것을 알려주고 싶었다.

 

특히 문자의 인코딩 값에 대해 잘 파악하고 있다면 문자를 다루는데 훨씬 안정적이고 성능을 좋게 만들 수 있다.