[백준알고리즘/문자열] 10809번 문제 : 알파벳 찾기(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 7단계 문자열의 알파벳 찾기를 풀어봤습니다

이번 문제는 아스키코드를 응용하면 어렵지 않게 풀 수 있는 문제입니다

제가 푼 방법에 대해서 알아보겠습니다!

 

---

문제 링크입니다

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

10809번: 알파벳 찾기

 

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

 

출력

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.

만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.

 

 

---

문제 풀이

문제는 세 가지 방법으로 풀었습니다

 

1. indexOf() 사용

indexOf를 사용한 방법입니다

알파벳 a ~ z까지 아스키코드로 가져와서 반복문을 실행 indexOf를 사용하여 몇 번째 자릿수에 있는지 찾아냅니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader, BufferedWrite 변수 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// String 입력
		String a = br.readLine();
		
		// 알파벳 갯수만큼 반복문 실행
		for(int i = 97; i < 123; i++)
		{
			// 아스키코드를 문자열로 전환해서 indexOf를 사용하여 몇 번째에 알파벳이 있는지 구함
			char ch = (char) i;
			String str = String.valueOf(ch);
			bw.write(a.indexOf(str) + " ");			
		}
		
		// 결과 출력
		bw.flush();
		br.close();
		bw.close();
	}
}

 

2. indexOf() 사용

첫 번째와 마찬가지로 indexOf를 사용하지만 조금 더 속도가 빠르도록 다듬었습니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader, StringBuilder 변수 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		// String 입력
		String a = br.readLine();

		// 알파벳 갯수만큼 반복문 실행
		for(int i = 97; i < 123; i++)
		{
			// 아스키코드를 문자열로 전환해서 indexOf를 사용하여 몇 번째에 알파벳이 있는지 구함
			sb.append(a.indexOf( Character.toString((char) i))).append(" ");			
		}

		// 결과 출력
		System.out.print(sb);
	}
}

 

3. 알파벳을 배열로 선언하여 문자열과 비교

이 방법은 이 코드를 참고하여 구현하였습니다

참고 : https://www.acmicpc.net/source/26869870

알파벳 갯수만큼 배열로 선언하여 문자열이 존재하는 경우 자릿수를 업데이트하는 방식입니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader, StringBuilder 변수 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// 알파벳 배열 선언 및 -1로 초기화
		int[] alphabet = new int[26];
		Arrays.fill(alphabet, -1);

		// String 입력
		String str = br.readLine();

		// String 갯수만큼 반복
		for(int i = 0; i < str.length(); i++)
		{
			// String의 문자열 index를 구함
			int index = str.charAt(i) - 97;
			
			// -1인 경우 업데이트
			if(alphabet[index] == -1) 
				alphabet[index] = i;
		}

		// 알파벳 갯수만큼 반복문 실행
		for(int i = 0; i < 26; i++)
		{
			// 결과 입력
			sb.append(alphabet[i]).append(" ");
		}
		
		// 결과 출력
		System.out.print(sb);
	}
}

 

여기까지 제가 풀은 세 가지 방법에 대해서 알아봤습니다

이제 속도 비교를 해보겠습니다

 

---

속도 비교

1. indexOf 방식

2. indeOf 방식(개선)

3. 알파벳 배열 방식

속도는 2번, 3번이 같게 나옵니다

하지만 메모리는 3번 방식이 더 적게 나오는 것을 볼 수 있습니다!

 

이상 백준 알고리즘 10809번 알파벳 찾기를 풀은 내용이었습니다!

 

다음 문제 : 2021.05.15 - [알고리즘/알고리즘JAVA] - [백준알고리즘/문자열] 2675번 문제 : 문자열 반복(자바/JAVA)

이전 문제 : 2021.05.13 - [알고리즘/알고리즘JAVA] - [백준알고리즘/문자열] 11720번 문제 : 숫자의 합(자바/JAVA)