문제
크로아티아 알파벳에는 c=, c-, dz=, d-, lj, nj, s=, z= 등 여러 문자로 하나의 알파벳을 표현하는 경우가 있다. 입력 문자열이 크로아티아 알파벳으로 몇 글자인지 구하라.
입력
첫째 줄에 알파벳 소문자와 =, -로 이루어진 문자열이 주어진다 (길이 100 이하).
출력
크로아티아 알파벳의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
ljes=njansen= | 6 |
풀이
문자열을 앞에서부터 순회하며, 크로아티아 알파벳 패턴을 탐지하면 해당 글자 수만큼 건너뛴다.
- 현재 문자와 다음 1~2 문자를 확인하여 크로아티아 알파벳 패턴인지 검사한다
- dz= (3글자), c=, c-, d-, lj, nj, s=, z= (2글자) 패턴이 매칭되면 해당 길이만큼 인덱스를 전진시킨다
- 매칭되지 않으면 일반 알파벳 1글자로 처리한다
- 각 단계마다 글자 수를 1 증가시킨다
핵심 아이디어: 가장 긴 패턴(dz=, 3글자)부터 먼저 매칭을 시도해야 정확하다. isCroatia 함수에서 d 다음에 z=를 먼저 확인하고, d- 를 그 다음에 확인하는 방식으로 처리한다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day10BOJ2941크로아티아알파벳 { // 2941
static String str;
static int tmp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
str = sc.nextLine();
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
tmp = 0;
if (isCroatia(i)) {
i += tmp; // boolean에서 확인한 글자수 만큼 전진
}
cnt++;
}
System.out.println(cnt);
sc.close();
} // 이게.... 맞아?
private static boolean isCroatia(int i) {
char c1 = str.charAt(i);
char c2 = ' ';
char c3 = ' ';
if (i + 1 < str.length())
c2 = str.charAt(i + 1);
else
return false;
if (i + 2 < str.length())
c3 = str.charAt(i + 2);
if (c1 == 'c') {
if (c2 == '=' || c2 == '-') {
tmp = 1;
return true;
}
} else if (c1 == 'd') {
if (c2 == '-') {
tmp = 1;
return true;
} else if (c2 == 'z') {
if (c3 == '=') {
tmp = 2;
return true;
}
}
} else if (c1 == 'l') {
if (c2 == 'j') {
tmp = 1;
return true;
}
} else if (c1 == 'n') {
if(c2 == 'j') {
tmp = 1;
return true;
}
} else if(c1 == 's') {
if(c2 == '=') {
tmp = 1;
return true;
}
} else if(c1 == 'z') {
if(c2 == '=') {
tmp = 1;
return true;
}
}
return false;
}
}복잡도
- 시간: O(N) — 문자열 한 번 순회
- 공간: O(N) — 입력 문자열 저장