[BaekJoon] 25957번 : 단어 우월 효과 (캠브릿지 대학의 연구결과) (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 단어 우월 효과 입니다.

25957번: 단어 우월 효과 (캠브릿지 대학의 연구결과)

👨🏻‍💻 문제 풀이

1. 입력 받은 N개의 정상적인 단어를 각 단어별 특정한 조건으로 key 를 생성하는 함수 만들기

def matching_key_generator(word):
    key = word
    
    if len(word) > 2:
        key = "-".join([word[0], word[-1], "".join(sorted(word[1:-1]))])
    elif len(word) == 2:
        key = "-".join(list(word))
        
    return key

입력 받은 N개의 단어를 아래의 방법을 활용하여 해당 단어임을 나타내는 unique 한 key 값을 만들었습니다.

구분	내용		예시
단어의 길이가 1인 경우	단어 그 자체를 key 값으로		단어 : i / key : i
단어의 길이가 2인 경우	첫번째 문자와 두번째 문자 사이를 - 로 이어줌		단어 : hi / key h-i
단어의 길이가 2보다 큰 경우	첫번째 문자, 마지막 문자 그리고 가운데 존재하는 단어를 오름차순으로 정렬한 값을 - 로 이어준 값		단어 : somjang key : s-g-ajmno

2. 각 단어별 생성한 key값을 key 로 단어를 value 로 하는 matching dictionary 만드는 함수 만들기

def word_matching_dict(word_list):
    matching_dict = {}
    
    for word in word_list:
        key = matching_key_generator(word=word)
        matching_dict[key] = word
        
    return matching_dict

각 단어마다 1번에서 만든 함수를 활용하여 만든 key 값을 가지고 

그 값을 key 로 단어를 value 로 하는 dictionary 를 만들었습니다.

3. 공백을 기준으로 붙어있는 M개의 순서가 뒤바뀌어 있는 단어를 split 한 뒤 1번과 2번에서 만든 함수를 활용하여 정상적인 단어들로 구성된 문자열을 만드는 함수 만들기

2번에서 만든 함수로 생성한 key - 단어 matching dictionary 를 활용하여

순서가 뒤바뀌어 있는 단어를 정상적인 단어로 바꾸어 주는 작업 진행하였습니다.

def word_superiority_effect(word_list, S):
    answer = []
    
    word_S_list = S.split()
    
    matching_dict = word_matching_dict(
        word_list=word_list
    )
    
    for word_idx, word in enumerate(word_S_list):
        key = matching_key_generator(word=word)
        answer.append(matching_dict[key] if key in matching_dict else word)
            
    return " ".join(answer)

순서가 뒤바뀐 단어를 1번에서 만든 함수를 활용하여 key로 변환

-> 변환한 key 값을 활용하여 그 key 값을 가진 정상적인 단어 가져오기

 

위 방식으로 모든 단어를 치환해주었습니다.

4. 시간초과를 피하기 위한 input -> sys.stdin.readline 작업 (개행문자 주의!)

3번까지 했으면 사실 문제에서 원하는 결과가 나오지만 

문제에 보면 N과 M이 0과 200,000 사이 값이라는 점 때문에 그냥 제출하면 시간초과 가 발생하게 됩니다.

 

위에서 푼 방식으로는 N과 M이 모두 200,000일 때 반복문을 최대 400,000번 까지 돌게됩니다.

여기서 input() 은 200,000번 까지 돌 수 있는데 항상 백준에서 input 이 어느정도 이상 실행되면 시간 초과가 발생하여

input() 을 sys.stdin.readline() 로 바꾸어 풀곤 합니다.

 

이를 바꾸는 것은 딱 두 줄이면 됩니다.

import sys

input = sys.stdin.readline

이렇게 바꾸어주면 input() 이라고 작성했던 부분들이 자동으로 sys.stdin.readline() 처럼 동작하게 됩니다.

 

자! 그런데 이렇게 변환하고 제출하면 이제 에러가 발생하기 시작합니다.

 

이것 때문에 솔직히 삽질을 조금 많이 했습니다. 🥲

 

왜? 코드에서 sys.stdin.readline() 하나만 바꾸었는데 왜?? 왜??? 라고 생각하다가

예전에도 비슷한 문제가 있었던 것 같았고 잘 생각해보니 sys.stdin.readline() 을 사용하면

값 뒤에 개행문자가 생겨서 해당 값을 지워주지 않으면 코드에서 에러가 발생한 것이었습니다.

 

sys.stdin.readline() 에서 생기는 개행문자를 지워주기 위해서

input() 뒤에 rstrip() 을 붙여서 모든 입력 값에서 뒤에 붙는 개행문자를 제거하도록 하였습니다.

 

여기까지 하니 드디어 성공!

 

일단 input 에 대한 output 이 나오는 것 까지는 성공하여 좋았으나

조금 더 효율적인 방법이 있을지는 다른 분들의 코드를 보고 좀 더 고민해보아야할 것 같습니다.

 

읽어주셔서 감사합니다.

---

👨🏻‍💻 코드 ( Solution )

import sys

input = sys.stdin.readline


def matching_key_generator(word):
    key = word
    
    if len(word) > 2:
        key = "-".join([word[0], word[-1], "".join(sorted(word[1:-1]))])
    elif len(word) == 2:
        key = "-".join(list(word))
        
    return key


def word_matching_dict(word_list):
    matching_dict = {}
    
    for word in word_list:
        key = matching_key_generator(word=word)
        matching_dict[key] = word
        
    return matching_dict


def word_superiority_effect(word_list, S):
    answer = []
    
    word_S_list = S.split()
    
    matching_dict = word_matching_dict(
        word_list=word_list
    )
    
    for word_idx, word in enumerate(word_S_list):
        key = matching_key_generator(word=word)
        answer.append(matching_dict[key] if key in matching_dict else word)
            
    return " ".join(answer)
    

if __name__ == "__main__":
    word_list = []
    
    N = int(input().rstrip())
    
    for _ in range(N):
        word_list.append(input().rstrip())
        
    M = int(input().rstrip())
    S = input().rstrip()
    
    print(word_superiority_effect(word_list=word_list, S=S))

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07