[#20436] ZOAC3

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

20436번: ZOAC 3

 

쉬워서, 구현보다는 효율을 신경썼어야 했다.
그래서 pythonic한 것에 대해 배울 수 있었던 기회

 

 

 

문제를 처음보고

# 각 글자의 위치를 검색할 수 있는 data
# 각 글자가 자음인지 / 모음인지를 판단할 수 있는 data


for char in word :

    # 모음 / 자음 판단

    # if 모음 : 모음 예전거리 ~ 모음 현재거리 계산
    	# cnt += NN
    # else : 자음 예전거리 ~ 자음 현재거리 계산
    	# cnt += NN
    
    # cnt += 1 # 누르는 시간

 

이렇게 틀을 잡았다. 

 

구현은 쉬울 것 같아서 어떻게 가장 빠른 자료구조를 쓸 수 있을지 생각했다. 

 

처음엔 딕셔너리가 리스트보다 검색이 빠르니까, {'a' : (1,2) ,,,} 처럼 알파벳에 따른 위치를 기록해둘까 했다. 

근데 어차피 알파벳이 ascii코드로 쭈루룩 있으니까 잘 활용해서 그냥 바로 인덱스로 접근하도록 하는게 낫겠다. 싶었다.

 

파이썬으로 ascii 코드를 확인하는건 ord()함수 를 사용하면 된다고한다!

+) 한번 정해진 좌표는 바뀔일 없으니까, 안전하게 set으로 선언하자

 

그럼 렛츠기릿해보자고

 

 

 

코드

# arr = [a(1,0), b(2, 4), c(2, 2), d(1, 2), e(0, 2), f(1, 3), g(1, 4), h(1, 5), i(0, 7), j(1, 6), k(1, 7), l(1, 8), m(2, 6), n(2, 5), o(0, 8) ,p(0, 9), q(0, 0), r(0, 3), s(1,1) ,t(0, 4), u(0, 6), v(2, 3),w(0, 1), x(2, 1), y(0, 5), z(3, 0)]
position_list = [(1,0), (2, 4), (2, 2), (1, 2), (0, 2), (1, 3), (1, 4), (1, 5), (0, 7), (1, 6), (1, 7), (1, 8), (2, 6),(2, 5), (0, 8) ,(0, 9), (0, 0),(0, 3), (1,1) ,(0, 4), (0, 6), (2, 3),(0, 1), (2, 1), (0, 5), (2, 0)]

jaeum_dict = {'q', 'w', 'e', 'r', 't', 'a', 's', 'd', 'f', 'g', 'z', 'x', 'c', 'v'}
moeum_dict = {'y', 'u', 'i', 'o', 'p', 'h', 'j', 'k', 'l', 'b', 'n', 'm'}

prior_left_pos, prior_right_pos = map(str, input().split())
word = input()

prior_left_pos, prior_right_pos = position_list[ord(prior_left_pos)-97],  position_list[ord(prior_right_pos)-97]
cnt = 0
for char in word :
    # 모음 / 자음 판단
    if char in jaeum_dict : # 자음인경우
        cur_pos = position_list[ord(char)-97]
        cnt += abs(prior_left_pos[0] - cur_pos[0]) + abs(prior_left_pos[1] - cur_pos[1])
        prior_left_pos = cur_pos
    else : # 모음인경우
        cur_pos = position_list[ord(char)-97]
        cnt += abs(prior_right_pos[0] - cur_pos[0]) + abs(prior_right_pos[1] - cur_pos[1])
        prior_right_pos = cur_pos
    cnt += 1

print(cnt)

 

 

와 실버라서 그런지 1트 통과!!

 

 

시간복잡도 확인

쉬운 문제니까 '돌아가는게 중요' 하기 보다 '얼마나 효율적인가' 가 관건인 문제 같다. 

 

나는 키보드에서의 위치를 하나하나 리스트로 하드코딩해서 만드는게 귀찮았지만,, 귀찮은만큼 속도가 괜찮았으면 하는 바램이다!!

 

그럼 남들의 속도를 보러 가볼까?

 

 

.........................................................................

거의 남들에 비해 두배 더 많은 시간이 걸렸다

메모리도 배로 썼다 ㄱ-

 

 

하하 쓰발 누가 pythonic하게 야무지게 짰을꼬.... 

한수 배우러 간다

 

 

 

한수배워요 

keyboard = ["qwertyuiop", "asdfghjkl", "zxcvbnm"]

# dictionary 형태로 key 위치 기록
key = dict()
for r in range(len(keyboard)): 
    for c in range(len(keyboard[r])): 
        key[keyboard[r][c]] = (r, c) 

prior_left, prior_right = input().split()
word = input().rstrip()

prior_left = key[prior_left]
prior_right = key[prior_right]
end_l = [5,5,4] # 자음 / 모음 판단할 기준 # 첫째줄 모음이 시작하는 column index / 두번째줄 ... / 세번째줄...


time = 0
for ch in word:
    r, c = key[ch] # dictionary에서 key 위치 검색
    if c < end_l[r]: # 자음인경우
        time += abs(prior_left[0] - r) + abs(prior_left[1] - c)
        prior_left = (r, c)
    else: # 모음인경우
        time += abs(prior_right[0] - r) + abs(prior_right[1] - c)
        prior_right = (r, c)

print(time + len(word))

 

 

와! 천재다!

 

1) dictionary에 일일이 위치를 하드코딩 하지 않았다. 

나는 위치를 코드로 자동화해서 알아내는 과정도 시간복잡도가 아까웠는데, 

어차피 이정도 문제면 30분안에 풀어내야하니까 그냥 26번 반복문 돌리는게 더 나았다. 

 

2) list를 indexing으로 접근하는 것보다 dictionary를 searching으로 접근하는게 더 빠르구나

와 첨알았다. 막연히 '아무리 dictionary라고 해도 searching이니까, list indexing이 더 빠르겠지' 라고 생각했었다.

아니구만 ㅈㅅㅎㄴㄷ!

나중에 time log 찍어서 한번 확인하거나 관련된 글을 찾아서 포스팅 함 해야겠다.

 

 3) 자음 모음 판단하는게 깔끔하다!

이건 그냥 발상이 천재세요

당신의 아이디어를 back get some me down