본문 바로가기
Problem Solving/BOJ

[BOJ][Python]16139번 풀이

by NoiB 2021. 10. 31.
반응형

상당히 오랜만에 돌아온 백준 문제죠. 원래는 단계별 문제풀이를 천천히 올리고 싶었는데 오늘은 괜히 이 문제가 올리고 싶더라고요.

 

문제 링크 : https://www.acmicpc.net/problem/16139

 

16139번: 인간-컴퓨터 상호작용

첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 q가 주어지며, 문제의 수는 1q200,000을 만족한다. 세 번째

www.acmicpc.net

 

해당 문제는 해석을 해야 하는 문자열과 테스트 횟수, 테스트 케이스를 입력으로 주고 테스트 케이스의 조건에 맞는 값을 출력하는 문제입니다. 테스트는 타겟문자와 범위를 제공하고 범위 내에 타겟문자가 몇 번 나오는지를 출력해야 합니다. 여기까지 들으셨다면 아마 눈치 빠른 분들은 아 count(x,_start,_end)를 쓰면 되겠구나 하고 감이 오셨을 겁니다. 그렇다면 한 번 count를 사용해볼까요?

 

import sys

S=input()
q=int(input())

for i in range(q):
    alphabet,l,r=sys.stdin.readline().split()
    print(S.count(alphabet,int(l),int(r)+1))

 

하지만 이렇게 해서 제출을 하게 되면 처음엔 잘 통과하는 듯 싶더니 어느 순간 엄청 느릿느릿하게 통과하다가 시간 초과로 멈추고 50점밖에 못받게 됩니다. 그 이유는 태스크 1은 2000자 이하의 문자열이, 2000번 이하의 테스트를 보는 조건으로 테스트를 진행하는데요. 태스크 2는 문제에서 원래 주어진 조건대로 200000자 이하의 문자열, 200000번 이하의 테스트를 진행하게 되면서 시간초과로 실패하게 되는 겁니다. 문제는 풀었는데 시간이 오래 걸려서 통과하지 못하는 일이 백준에서 문제를 풀다 보면(특히 고난이도로 갈수록) 종종 일어나는데요. 여기에는 '시간 복잡도'라는 개념이 개입을 합니다.

시간 복잡도란?

시간 복잡도는 '문제를 해결함에 있어서 계산과 입력의 함수 사이에서의 관계를 정량화한 것'이라는 설명을 위키백과에서 찾을 수 있습니다. 간단하게 말하자면 문제를 푸는데 시간이 얼마나 걸리느냐를 따지는 거라고 볼 수 있는데요. 시간 복잡도를 표기하는데에 있어서 가장 보편적인 'Big O 표기법'이 있습니다. 이 Big O 표기법은 계수와 낮은 차수의 항을 제외시키고 시간복잡도를 점근적으로 묘사하는 방법입니다. 예를 들어서 어떤 알고리즘의 계산을 식으로 나타냈을 때 2n^2 + 3n 이라는 식이 나온다면 이를 Big O 표기법으로 적으면 O(n^2)이라고 적는 것입니다. 시간 복잡도에 대한 얘기는 이 정도로 하고 다음에 좀 더 자세하게 정리해서 글을 적어보겠습니다.

 

그럼 이제 위의 코드를 좀 따져볼까요?

처음에 문자열을 입력받고, 테스트 횟수를 입력받고, 그 횟수만큼 반복문을 돌리게 되는데요. 반복문 안에서 테스트 케이스를 받고 count를 이용해서 문자열을 탐색하고 범위 내에 갯수를 찾아내게 됩니다. count 함수가 정확하게 어떤 방식으로 문자의 갯수를 찾는지는 모르겠지만 우리는 문자의 갯수를 구하는 알고리즘을 직접 구현하라고 한다면 아마 아래의 코드같은 방법으로 짜는게 가장 쉽게 떠올릴 수 있는 방식이겠죠.

 

s = input()
count = 0
for i in s:
	if i == 'a':
    	count += 1
print(count)

 

위 코드는 s에서 'a'의 갯수를 찾는 코드입니다. 이 코드를 잠시 살펴보면 i를 s의 첫 글자부터 해서 계속 'a'와 같은지를 비교하는데요. 짧은 문장이나 테스트 케이스가 한 번뿐이라면 별로 이런 방법도 문제가 되진 않겠죠. 그런데 문제에서 주어진 것처럼 20만 자의 문자열을 20만 번이나 테스트를 해야 한다면 벌써 400억 번이죠. 이게 만약 n자를 n번 테스트한다고 생각하면 O(n^2)의 시간 복잡도를 갖겠네요. 상당한 양의 연산을 하게됩니다. 정확한 방법은 아니지만 대충 연산 한 번에 1억분의 1초 정도가 걸린다고 생각하라던 친구의 말을 빌리면 400초나 계산을 하고 있는거니까 제한시간인 1초를 상당히 넘기게 되겠죠(물론 실제로 400초까지 걸리진 않습니다). 그렇다면 이 n^2번의 연산을 어떻게든 줄여야 하는게 이번 문제풀이의 핵심이 되겠습니다.

 

import sys

def make_dict(S, al):
    al_dict = {}
    for i in al:
        count = 0
        count_list = []
        for j in S:
            if i == j:
                count += 1
            count_list.append(count)    
        al_dict[i]=count_list
    return al_dict

def count_num_of_alphabet(al_dict, quest_key, quest_left, quest_right):
    low = int(quest_left)
    high = int(quest_right)+1
    answer = al_dict[quest_key][high] - al_dict[quest_key][low]
    return answer

al = 'abcdefghijklmnopqrstuvwxyz'
S=' ' + sys.stdin.readline().rstrip()
q=int(sys.stdin.readline())
al_dict = make_dict(S,al)
#print(al_dict)
for i in range(q):
    quest_key, quest_left, quest_right = sys.stdin.readline().split()
    answer = count_num_of_alphabet(al_dict, quest_key, quest_left, quest_right)
    print(answer)

 

위 코드는 100점을 다 받은 코드인데요. 실질적으로 이 코드는 O(n)의 시간복잡도를 갖게 됩니다. 어떻게 그렇게 되는지 천천히 나눠서 진행해보겠습니다.

 

def make_dict(S, al)

def make_dict(S, al):
    al_dict = {}
    for i in al:
        count = 0
        count_list = []
        for j in S:
            if i == j:
                count += 1
            count_list.append(count)    
        al_dict[i]=count_list
    return al_dict

이 함수는 al_dict라는 dictionary 자료형에 각 알파벳을 key값으로, 제공받은 문자열(S)의 인덱스에 따라 각 key값의 갯수를 리스트 자료형으로 value값으로 받는 함수입니다. 가령 S = 'aaaaa'의 문자열이 입력될 때 이 함수를 선언하면 {'a' : [1, 2, 3, 4, 5], 'b' = [0, 0, 0, 0, 0,] ...} 이렇게 S가 a로만 이루어져 있으니 a는 인덱스에 따라 값이 계속 커지지만 다른 알파벳들은 전부 0이 되는 거죠.

 

def count_num_of_alphabet(al_dict, quest_key, quest_left, quest_right)

def count_num_of_alphabet(al_dict, quest_key, quest_left, quest_right):
    low = int(quest_left)
    high = int(quest_right)+1
    answer = al_dict[quest_key][high] - al_dict[quest_key][low]
    return answer

이 함수는 테스트 문자와 범위가 입력될 때 범위 내에 테스트 문자가 몇 개나 있는지를 확인하는 함수입니다. S = 'aaaaa'이고 만약 'a'가 테스트 문자, 테스트 범위가 '0 0'으로 주어진다면 answer는 1이 되어야겠죠.

 

main

import sys

al = 'abcdefghijklmnopqrstuvwxyz'
S=' ' + sys.stdin.readline().rstrip()
q=int(sys.stdin.readline())
al_dict = make_dict(S,al)
#print(al_dict)
for i in range(q):
    quest_key, quest_left, quest_right = sys.stdin.readline().split()
    answer = count_num_of_alphabet(al_dict, quest_key, quest_left, quest_right)
    print(answer)

이제 메인을 좀 살펴볼까요? 먼저 key값으로 넘길 알파벳을 선언합니다(이 방법 말고 훨씬 스마트한 방법이 많습니다만...). 그러고 S를 입력받는데 앞에 공백 한 칸을 넣어주시고 뒤에 rstrip()으로 공백을 빼주세요. 앞의 공백은 뒤에서 설명하겠지만 뒤의 공백을 빼주는 이유는 sys.stdin.readline()의 경우 맨 뒤에 개행 문자가 붙기 때문에 이렇게 split()을 사용하는 경우가 아니라면 빼주는 것이 바람직합니다. 그리고 테스트 횟수를 입력받고 make_dict(S, al)을 실행해서 모든 알파벳에 대한 S에서의 값으로 이뤄진 dictionary가 하나 만들어집니다(지금 보니 굳이 모든 알파벳에 대해 다 할 필요 없이 S를 구성하는 알파벳으로만 dictionary를 만드는 쪽이 좀 더 경제적이겠네요). 그리고 반복문에서 테스트 문자와 범위를 입력받고 count_num_of_alphabet을 실행하는데 저희가 아까 전에 S의 맨 앞에 공백을 하나 넣었죠? 만약 공백 없이 진행을 하게 되면 S[0]에 테스트 문자가 있는 경우 answer의 값이 무조건 하나 작은 값이 나오게 됩니다. 그 이유는 S = 'abb'(왼쪽 공백 없음) 일 때 al_dict = {'a' : [1, 1, 1], 'b' : [0, 1, 2]}가 되고 테스트 케이스가 'a 0 0'일 경우 al_dict['a'][0] 은 1이기 때문에 answer를 구하는 식에 따라 1 - 1로 0이 되어버리기 때문입니다. 따라서 왼쪽에 공백을 하나 넣어줌으로써 어떤 key값에서도 S[0]이면 무조건 값이 0이 되게 해서 해결을 했습니다.

 

결국 맨 처음에 제시했던 코드와 결정적으로 다른 부분은 처음에 딕셔너리를 만들 때는 모든 알파벳에 대한 경우를 다 따지기 때문에 너무 비효율적인 거 아냐? 싶지만 극한의 개념으로 생각을 해볼 때 n^2이 n 보다 훨씬 빨리 발산하기 때문에 n이 커지면 커질수록 두 번째 코드가 훨씬 효율적이다 라는 사실을 알 수 있습니다.

 

자세하게 설명을 하려다 보니 평소보다 글이 많이 길어졌는데요. 다들 본인만의 방법이 있기 때문에 제 것을 무작정 따라 하기보다는 이 사람은 이렇게 했구나 정도만 생각하시면 될 것 같습니다. 굳이 남의 코드를 답습함으로써 공부를 하려는 의도가 아니라면 다른 사람의 코드를 하나하나 완벽하게 파악하는 건 상당히 귀찮은 작업이 되니까요. 오늘도 긴 글 읽어주셔서 감사합니다.

반응형