[백준] 10809번 : 알파벳 찾기 - JAVA [자바]

 

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

10809번: 알파벳 찾기

---

• 문제

 

 

 

문제의 난이도는 어렵지 않다.

※ 주의할 점

1. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있다.
2. a ~ z 를 모두 출력하여 주어진 문자열에 대해 해당 문자가 처음으로 나오는 위치를 출력한다.
3. 위치는 0 부터 시작한다. 즉 문자열 첫 단어는 위치가 0 이다. 

 

 

 

---

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

 

먼저 Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

 

 

---

• 알고리즘

1. 먼저 int 형 배열을 하나 생성하여 모두 -1 로 초기화 시킨다.

이 배열은 문자열 S 에 각 문자의 위치를 가리킬 배열이다.

 

int[] arr = new int[26];

for(int i = 0; i < arr.length; i++){
	arr[i] = -1;
}

 

 

 

 

2. S 이라는 문자열이 주어진다.

 

int[] arr; // -1 로 초기화 된 배열

String S = in.nextLine();

 

 

 

 

3. 그리고 반목문을 통해 문자열의 각 문자를 검사하여야 한다. 즉, charAt() 이라는 메소드를 사용하여 문자를 추출한 뒤 ch 라는 변수에 저장해준다.

 

int[] arr; // -1 로 초기화 된 배열

String S = in.nextLine();

for(int i = 0; i < S.length(); i++){
	char ch = S.charAt(i);
}

 

 

5.  그리고 ch 의 문자의 위치를 우리가 앞서 만든 arr 배열의 값으로 바꿔준다.

이때 문제에서 위치는 0 부터 시작한다고 했으니 ch 의 문자의 위치는 i 가 되는 것을 알 수 있다.

또한 arr 배열의 인덱스(원소 위치)는 ch 가 갖고 있는 문자 인코딩 값(=아스키코드 값과 동일)에 'a' 또는 97 을 빼주면 된다.

( a 는 10진수로 97 이라는 값에 대응된다.)

 

만약 b 라는 문자가 ch 에 담겨있을 경우 b - 'a' 또는 b - 97 을 하면 1 이 되고, arr[1] 은 문자 b를 가리키는 것을 의미한다.

 

즉 아래와 같이 짜면 된다.

 

int[] arr; // -1 로 초기화 된 배열

String S = in.nextLine();

for(int i = 0; i < S.length(); i++){
	char ch = S.charAt(i);
    
	arr[ch - 'a'] = i;
}

 

 

 

6. 근데 문제가 있다. 문제를 잘 보면 동일 문자가 포함되어있는 경우 처음 나타난 위치로 나타내야한다.

즉, 문자열을 앞에서부터 검사할 때, 앞선 동일문자가 존재하여 arr 에 위치를 변경했을 경우는 arr 의 값을 변경하지 않으면 된다.

 

이 의미는 결국 -1 인 경우에는 배열의 원소 값을 변경하고 -1 이 아닌 경우 배열의 원소 값을 변경하지 않는다.

 

즉, 조건문을 추가하여 아래와 같이 짜면 된다.

 

int[] arr; // -1 로 초기화 된 배열

String S = in.nextLine();

for(int i = 0; i < S.length(); i++) {
	char ch = S.charAt(i);
    
	if(arr[ch - 'a'] == -1) {	// arr 원소 값이 -1 인 경우에만 초기화
		arr[ch - 'a'] = i;
	}
}

 

이런식으로 구조를 짜면 된다.

 

 

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

 

 

---

• 풀이

- 방법 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];
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = -1;
		}

		String S = in.nextLine();

		for(int i = 0; i < S.length(); i++) {
			char ch = S.charAt(i);
    
			if(arr[ch - 'a'] == -1) {	// arr 원소 값이 -1 인 경우에만 초기화
				arr[ch - 'a'] = i;
			}
		}

		for(int val : arr) {	// 배열 출력
			System.out.print(val + " ");
		}
	}
}

 

 

위의 알고리즘을 토대로 그대로 구현한 코드다.

그리고 한 줄에 한 원소와 한 공백씩 출력해야한다는 거 유의하자.

 

---

 

- 방법 2 

 

 

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];
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = -1;
		}

		String S = br.readLine();

		for(int i = 0; i < S.length(); i++) {
			char ch = S.charAt(i);
    
			if(arr[ch - 'a'] == -1) {	// arr 원소 값이 -1 인 경우에만 초기화
				arr[ch - 'a'] = i;
			}
		}

		for(int val : arr) {	// 배열 출력
			System.out.print(val + " ");
		}
	}
}

 

 

 

 

---

• 성능 차이

 

위에서 부터 순서대로

 

채점 번호 : 18519553 -  BufferedReader 

채점 번호 : 18519538 -  Scanner

 

 

알고리즘의 수행시간은 O(N) 이다. 나름 빠른 알고리즘에 속하지 않을까 싶다만.. 더 좋은 코드드도 많을테니 한 번 직접 구상해보시는 걸 추천한다. 시간을 보면 BufferedReader 와 Scanner 의 성능차이를 볼 수 있다.

 

 

 

 

 

---

• 정리

 

보면 아주 단순한 문제다.

 

다만 보면 가끔 이중 for문을 취하는 분들도 많이 계신데, 나쁜 방법은 아니나 수행시간에 있어 그다지 좋지 못하다.

최대한 가능하다면 반복수행을 최소화 하는 방향으로 구성하는게 가장 좋은 방법이다.