[Python 파이썬] 백준 2941번 - 크로아티아 알파벳

2023년 4월 30일

문제 링크 : 백준 2941 - 크로아티아 알파벳

문제

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다.

크로아티아 알파벳변경

č	c=
ć	c-
dž	dz=
đ	d-
lj	lj
nj	nj
š	s=
ž	z=

예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.

dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다.

입력

첫째 줄에 최대 100글자의 단어가 주어진다. 알파벳 소문자와 '-', '='로만 이루어져 있다.

단어는 크로아티아 알파벳으로 이루어져 있다. 문제 설명의 표에 나와있는 알파벳은 변경된 형태로 입력된다.

출력

입력으로 주어진 단어가 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.

알고리즘 분류

• 구현
• 문자열

 

---

문제 접근

문자열 주어졌을 때, 해당 문자열에서 ‘알파벳 개수 + 크로아티아 알파벳 개수 ’ 가 얼마나 되는지 묻는 문제다.

주어진 문자열은 다음과 같은 조합으로 구성된다.

1. 일반 알파벳
2. 일반 알파벳과 구분되는 ‘크로아티아 알파벳’

아무생각 없이 문제에 접근했을 땐, 크로아티아 알파벳으로만 구성된 문자열이 주어지는 줄 알고 방심했다가 예제 입력한데 혼났다.

 

---

순서도

1. 문자열 s를 입력 받음

2. 크로아티아 알파벳의 '부분 알파벳'을 _pattern에 따로 담음 : 문자열 s를 앞에서부터 한 문자 씩 탐색할 텐데,
	탐색중인 문자가 “크로아티아 알파벳일 가능성”이 있는지 없는지를 판단하기 위함.

3. 크로아티아 알파벳을 pattern에 담음

4. 변수 선언
    4-1. idx : 입력받은 문자열 s를 탐색할 때 사용할 인덱스 변수
    4-2. cnt : 알파벳 개수를 담을 변수
    
5. while문을 통해 반복문 수행. idx가 입력받은 문자열의 길이보다 크거나 같으면 종료

6. 임시 문자열 변수 temp에 s[idx] 담아놓고, 해당 문자가 _pattern에 존재하는지 검사

7. 존재하는지 존재하지 않는지에 따라 조건문 분기
	7-1. 존재함  :  temp에 s[idx+1]을 추가로 담음
		7-1-1. temp가 pattern에 존재함. 만약 dz라면 추가로 s[idx+2] 또한 더해서, dz= 인지 검사
		7-1-2. temp가 pattern에 존재하지 않음 : s[idx]은 일반 알파벳으로 취급. idx와 cnt를 1 증가시키고 다시 반복문 수행
	7-2. 존재하지 않음 :  해당 문자는 일반 알파벳과 같으니, idx, cnt를 1 증가시키고 다시 반복문 수행
   
8. 최종 cnt 출력

---

입력 예제

ljes=njak

위 예제에서 1순위 : 크로아티아 알파벳, 2순위 : 일반 알파벳 우선순위 순으로 단위문자로 나눈다면 다음과 같다.

lj, e, s=, nj, a, k ( 크로아티아 알파벳 : 빨간색 , 일반 알파벳 : 파란색)

문자열의 처음부터 탐색을 진행해보자.

일단 temp라는 임시 변수에 l을 담아놓자.

l은 크로아티아 알파벳의 일부일수도 있고, 그저 일반 알파벳일 수도 있다. 이런 가능성이 있는 친구들은 ‘그 다음 문자’까지 고려해보면 된다. 그 다음 문자인 j까지 temp에 합쳐 lj로 고려해보자. 해당 문자는 크로아티아 알파벳이다. 이와 같이 크로아티아 알파벳 조합이 가능하면 cnt를 1증가시킨다. lj까지 묶어서 탐색을 진행했으니 idx는 2만큼 뭉텅이로 증가시켜 다음 반복문을 수행한다.

그 다음 문자인 e를 보자. e는 애초에 크로아티아 알파벳의 일부로도 불가능한 알파벳이다. cnt를 1 증가시키고 idx도 1 증가시켜 다음 문자를 확인한다.

해당 과정을 반복하면최종적으로 단위 문자를 lj, e, s=, nj, a, k 로 쪼갤 수 있다.

위 예제는 적어놓은 바와 같이, 모든 노드의 색이 0(하얀색)인 상태에서, (1) 5번 노드에 1(ex. 빨간색)을 칠하고, (2) 3번 노드에 2(ex. 파란색)을 칠하면 최종 트리 모양이 완성된다.

출력 예제

6

 

 

---

주의할 점

1. 크로아티아 알파벳 중, ‘dz=’ 문자가 존재한다. 위의 과정을 그대로 밟으면 dz까지만 확인하고 “엥? dz는 pattern에 없으니(크로아티아 알파벳 아니니까) 패스할게요~” 가 되어버린다. 나는 특이케이스인 dz=를 위해 temp == ‘dz’인 경우 그 다음 문자까지 합쳐서 고려해보도록 하였다.
   temp == ‘dz=’라면 크로아티아 알파벳으로 분류, temp == ‘dza’ 등 끝내 ‘dz=’가 아님을 밝혔다면 d를 일반 알파벳으로 취급하여 반복문을 수행하였다.
2. 위의 순서도를 보면, 현재 탐색중인 문자가 ‘크로아티아 알파벳’이면 idx를 임의로 1 증가시키는 방식으로 다음 문자를 탐색한다. 만약 idx가 문자열 s의 마지막 위치를 가리키고 있으면 idx+1번째 인덱스를 참조하려 할 때, index out of range를 당하게 될 것.
   다음 문자도 같이 묶어서 탐색을 시도하려 할 때마다, idx를 1씩 임의로 증가시키면 문자열 s의 범위를 벗어나는지 매번 조건문을 통해 확인해주었다.

---

전체 코드

# 2941

'''
1. 입력 받음
2. 크로아티아 알파벳의 '부분 알파벳'을 _pattern에 따로 담음
2-1. 크로아티아 알파벳 pattern에 담음
3. 반복문 수행. idx가 입력받은 문자열의 길이보다 크거나 같으면 종료
    1. temp에 s[idx] 담아놓고, 해당 문자가 _pattern에 존재하는지 검사
    1-1. 존재함 : temp에 s[idx+1]을 추가로 담음
    1-1-1. temp가 존재함. 만약 dz라면 추가로 s[idx+2] 또한 더해서, dz= 인지 검사
    1-1-2. temp가 존재하지 않음 : s[idx]은 일반 알파벳으로 취급. idx와 cnt를 1 증가시키고 다시 반복문 수행
    1-2 존재하지 않음: 해당 문자는 일반 알파벳과 같으니, idx, cnt를 1 증가시키고 다시 반복문 수행
4. 최종 cnt 출력
'''

_pattern = ["c","=","d","-","z","l","j","n","s"]
pattern = ["c=","c-","dz=","d-","lj","nj","s=","z="]
s = input()

idx = 0
cnt = 0

while(idx < len(s)):
    temp = s[idx]
    if temp in _pattern and idx + 1 < len(s):
        temp += s[idx + 1]
        if temp == "dz" and idx + 2 < len(s):
            temp += s[idx + 2]
            if temp == "dz=":
                cnt += 1
                idx += 3
                continue
        else:
            if temp in pattern:
                cnt += 1
                idx += 2
                continue
    
    cnt += 1
    idx += 1


print(cnt)

---

풀이 후기

더 효율적이고 창의적으로 풀어보고 싶었는데 솔직히 귀찮았다. 히히