백준 10809번 알파벳 찾기 - 자바

728x90

www.acmicpc.net/problem/10809

 

10809번: 알파벳 찾기

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출

www.acmicpc.net

! 알고리즘 풀이는 정답이 없습니다. 이런 방법도 있구나 하고 봐주시면 감사하겠습니다. - 알고리즘 초보 - 


 

1. 문제는 첫 째 줄에 S라는 문자열이 주어집니다.

 

2. 그 문자열에 a부터 z까지 0~25 인데 그 중 주어진 S라는 문자열에 해당하는 알파벳이 몇 번째 순서에 있는지 찾는 알고리즘 입니다.

 

3. 출력은 알파벳이 몇번 째로 나오는지와 존재하지 않는 알파벳 위치에는 -1이 출력되면 되겠습니다.

 

 

----------------------------------------------------------전체코드-----------------------------------------------------------

import java.util.Scanner;
class Main {  
  public static void main(String args[]) { 
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int result[] = new int[26];
    int tmp[] = new int[s.length()];
    for(int i=0; i<result.length; i++){
      result[i] = -1;
    }

    for(int i=0; i<s.length(); i++){
      tmp[i] = s.charAt(i)-'a';
    }
    for(int i=0; i<s.length(); i++){
       for(int j=0; j<result.length; j++){
           if(tmp[i]==j&&result[j]==-1){
             result[j]=i;
         }
       }
    }
    for(int i=0; i<result.length; i++){
      System.out.printf("%d ",result[i]);
    }
  }
}

 

입력은 Scanner와 BufferedReader를 사용해서 입력받으시면 되겠습니다. 

저는 Scanner를 사용해 입력받았습니다.

 

Scanner를 사용하여 String s를 입력받았습니다.

위에 예제처럼 baekjoon 문자열을 입력받았으면 s에 baekjoon이 입력됩니다.

 

a~z까지 출력할 수 있도록 26가지 배열 result를 만듭니다.

그리고 입력받은 문자열의 길이만큼 tmp 배열을 만듭니다. - 이 배열은 입력된 문자열 중에 첫 번째 부터 a~z중 어느것이 입력됬는지 비교하기 위함입니다.

 

배열 result를 모두 -1로 초기화 해줍니다.

그럼 result의 모든 인덱스에는 -1이 되었습니다.

 

s의 문자열의 길이만큼 반복해줍니다.

tmp에 인덱스에는 charAt()를 사용하여 첫 s문자열의 첫 번째 문자부터 접근합니다.

만약 baekjoon이라는 문자열이 s라면 i가 0일 경우에 b 를 접근하고 1일 경우에 a를 접근합니다.

접근한 문자에 - 'a'를 해줍니다. 

'a'는 아스키 코드 값으로 97입니다. 해당 문자의 97를 빼주어도 됩니다.

 

접근한 문자가 a이면 'a'-'a' (97-97)로 0이 됩니다. 

b라면 'b'-'a' (98-97)로 1이 됩니다.

 

baekjoon이라는 문자열이 입력되었다면 tmp 배열에는 1 0 4 10 9 14 14 13 이 입력됩니다.

그럼 이제 다시 s 문자열의 길이만큼 반복해줍니다. tmp길이 만큼 반복해도 똑같습니다.

그 후 2중 반복문을 통해 a-z까지 길이만큼 반복해줍니다. 미리 길이만큼 만들어놓은 result배열의 길이만큼 반복하도록 사용했습니다.

 

설명을 해드리면 tmp에 배열 첫 번째 인자가 0이면 'a' 이므로 result배열의 a알파벳 위치인 0번 째에 들어가야합니다.

그래서 tmp[i] 번째가 result[j] 와 같다면 result[j]에 i를 넣는 방법입니다.

tmp[i]가 0부터 시작합니다. 그럼 tmp[0] = 1이므로 'b'입니다.

i가 0인 상태에서 j가 0부터 25까지 반복됩니다. result배열 위치에서 'b'의 위치는 1입니다. 

그러니 tmp[i]에 있는 값과 j의 값이 같다면 result[j] 위치에 i 값을 넣어줍니다. 

이 때 i는 알파벳이 몇번 째로 등장하는지 숫자입니다.

 

* &&result[j]==-1을 해주는 이유는 입력값이 baekjoon일 경우 o가 두번 나옵니다. 같은 알파벳인 경우에는 먼저 나온 알파벳의 순서로 결정됩니다. 그러니 처음에 -1로 초기화 시켰으니 모두 -1인 상태에서 순서대로 값이 들어가게 되면 -1이 아닌 값으로 변하게되며 o가 5번째로 들어가게 되는데 result의 알파벳 o의 위치값이 -1이 아닌 5가 들어가게 되므로 다음 o를 찾았을 경우 값이 바뀌지 않게 됩니다. 

 

마지막 출력입니다.

result배열을 출력해줍니다. 인덱스마다 " " (공백)을 넣어야하므로 printf로 공백을 만들어 출력해줍니다.

'baekjoon'을 입력하였을 경우 실행 결과 

출력 순서

문자열 s 

tmp 배열

result 배열

 

 

-------------------------------------------

indexOf() 를 사용한 풀이법

특정 문자, 문자열을 앞에서부터 처음으로 발견되는 index를 반환하고 찾지 못했을 경우 -1을 반환합니다.

이 문제를 풀기에 딱 적당한 api입니다.

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

public class Main {
   public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String s =  br.readLine();
        for(char a = 'a'; a <= 'z'; a++) {
            sb.append(s.indexOf(a)).append(" ");
        }
       System.out.println(sb.toString());
    }
}

입력은 BufferedReader로 받았고, 출력은 StringBuilder를 통해 출력합니다.

문자열 s를 입력받았고, 

반복문을 통해 'a'부터 'z'까지 반복하며 

s.indexOf(a)를 통해 문자열 s에 'a'-'z' 까지 의 문자가 있는지 확인하고 있다면 몇 번째 인덱스인지 반환하고 문자가 없다면 -1을 반환합니다. 

그 후 " " (공백)을 넣어줍니다.

출력해줍니다.

반응형