[BOJ:2941] 크로아티아알파벳

Link : https://www.acmicpc.net/problem/2941

Note

오늘 프로그래머스 인턴 코딩테스트에서 나의 기본적인 구현실력이 부족함을 느껴서 구현문제를 풀어보기 위해 풀어본 문제.

역시나 구현의 약점이 들어났다. 처음부터 틀렸다. 최초 코드는 아래와 같은데 반례가 존재한다. 리스트에 넣어준 특수한 크로아디아 문자마다 입력으로 주어진 문자에서 개수를 세어주고 공백값으로 바꾸어 주었다. 그리고 마지막에 남은 문자에 대해서 길이를 구해서 전체 문자들의 개수를 구하려고 했다. 그런데 원래 nc=j 문자의 경우 c= 문자를 제거해주면 nj로 마뀌고 이경우 n과 j는 개별 문자로 임에도 nj 특수 문자로 개산이 되는 오류가 발생한다. 이 경우 개선하려면 특수 문자가 나오는 경우 *같은 문제에 주어지지 않은 길이 1자리 문자로 대체한 다음 마지막에 문자의 길이를 계산해주면 해결된다.

반례 존재 틀린코드

import sys

input = sys.stdin.readline

st = input()
cnt = 0
check = ["c=","c-","dz=","d-","lj","nj","s=","z="]

for ch in check:
    cnt += st.count(ch)
    st = st.replace(ch,"")

cnt += len(st)

print(cnt)

위에 풀이가 틀린 풀이임을 알고 문자열 인덱싱 접근법으로 해결했다. 크로아티아에 특수알파벳은 모두 c,d,l,n,s,z로 시작하는데 해당 알파벳일 경우 조건을 확인했는데, c일경우 =,- d일 경우 -,z 여기서 z일 경우(dz)에는 다시 다음 인덱스에서 =이 나오는지 확인해 주었다. 마찬 가지고 l,n,s,z의 경우에도 다음 문자가 크로아티아에 특수 알파벳의 경우와 일치하는지 확인해주었다.

나랑 전혀 다른 방식으로 풀이한 사람도 있었다.
각각의 특수문자의 수를 세어준다음 전체 길이에서 빼주었다. 빼주었다는 의미는 길이를 줄여주었다는 의미로 이해하면 된다. 예를 들면 "abcz=c="에서 'z=':1, 'c=':1로 총 2개가 발견되었고, 전체 길이 5에서 2를 빼주면 3이 나온다. 이렇게 일반화할 수 있는 이유는 'dz='의 경우 3글자짜리를 하나로 취급해야 하는 문자지만 'z='과 중복되기 때문에 'z='에서 중복으로 개수가 계산된다. 구체적으로 살펴보면 'dz=bz='이라는 문자가 주어졌을 때 'z=':2 'dz=':1로 계산되고, 전체 문자열의 길이 6에서 3을 빼주면 실제 사용된 크로아티아 문자의 개수 3이 나온다.
'abc=' -> 'ab*' 로 바꿀때 c=이라는 문자열 길이 2인 글자를 문자열길이 1로 줄이기 때문에 길이를 빼준다고 생각하면된다. 그리고 만약 문자열 길이3인 'dz='을 '*'로 바꿀때는 사실 문자열 길이를 -2를 해준 셈이다. 그런데 특이하게도 'dz='는 'z='라는 문자를 체크할때 중복으로 계산된다. 그래서 각 크로아티아 특수문자별 개수를 계산하여 최초의 문자 길이에서 빼주면된다.

주어진 문자열=> 'nljjz=dz='

각 특수 문자별 개수=> 'lj':1 'z=':2 'dz=':1

여기서 'dz='문자는 길이가 3에서 1로 줄어들기 때문에 전체 문자의 길이에서 뺄 때 2를 빼주어야 맞지만 위에서 설명한대로 'z='가 중복체크 되므로 다른문자들과 동일하게 1을 빼주어도 된다.

9 -1 -2 -1 = 9 - (1+2+1) = 5

크로아티아문자는 우리가 보는 문자의 길이와 실제 길이가 다르다. 표면적 길이에서 실제 길이로 줄여주어야한다. 표면적으로 계산된 문자열의 길이가 2인 문자를 하나의 문자로 계산할 때는 1을 빼주면 되고, 표면적으로 계산된 문자열의 길이가 3인 문자를 하나의 문자로 계산할 때는 2를 빼주면된다. 단, 여기서 특수하게 3개짜리 문자를 가지는 'dz='의 경우 'z='에서 중복 계산 되기 때문에 'z='이 등장하는 개수가 하나 많다. 그러므로 전체 길이에서 각 특수 문자의 개수의 합만큼 빼주면 크로아티아문자 사용 개수가 구해진다.

Code

내풀이

import sys

input = sys.stdin.readline

st = input().rstrip()
cnt = 0

i = 0
while i < len(st):
    if i < len(st) - 1:
        if st[i] == 'c':
            if st[i+1] == "=" or st[i+1] == "-":
                i += 1
        elif st[i] == 'd':
            if st[i+1] == "z":
                if i < len(st) - 2:
                    if st[i+2] == "=":
                        i += 2
            elif st[i+1] == "-":
                i += 1
        elif st[i] == "l" or st[i] == "n":
            if st[i+1] == "j":
                i += 1
        elif st[i] == "s":
            if st[i+1] == "=":
                i += 1
        elif st[i] == "z":
            if st[i+1] == "=":
                i += 1

    cnt += 1
    i += 1
print(cnt)

w=input();
len_w = len(w)
total = [w.count(a) for a in ['=','-','lj','nj','dz=']]
cnt = sum(total)
print(len_w - b)

#st = ['-', '=', 'nj', 'lj', 'dz=']
#fun=input().count
#print( fun('')+~sum(map(fun,st)) )

w=input();
len_w = len(w)
total = [w.count(a) for a in ['=','-','lj','nj','dz=']]
cnt = sum(total)
print(len_w - b)



def croatia(l, word):            
    result = [word.count(i) for i in l if i in word]

    return len(word) - sum(result) 

if __name__ == "__main__":
    croatia_alpabet = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z=']

    word = input()

    print(croatia(croatia_alpabet, word))