[PCCE 모의고사] 10번 문제풀이

https://school.programmers.co.kr/learn/courses/19275/lessons/240615

프로그래머스

 

 

변수 snippet에 쓰여있는 문자열 쌍을 참고하여, 주어지는 문자열 message를 변경하는 코드를 완성해야 하는 문제이다.

 

요구사항

snippet = [["IMO", "In my opinion"]]
message = "IMO, IMO"

 

예를 들어 snippet 과 message 가 위와 같다면, "IMO"는 "In my opinion"으로 치환하여 "IMO, In my opinion"를 결과로 반환해야 한다.

 

치환할 단어는 공백을 기준으로 구분하므로, 위의 message 에서 "IMO,"는 "In my opinion"으로 치환할 수 없다.

 

 

알고리즘

 

1) 치환 대상 정리

dct = dict()  # dictionary

for i in snippet:
    k = i[0]  # key 값
    v = i[1]  # value 값
    dct[k] = v  # 키: 값 쌍으로 dictionary에 저장

 

snippet에 들어있는 각 원소는 [치환_전_단어, 치환_후_단어] 의 구조를 가지고 있다.

 

치환_전_단어를 key, 치환_후_단어를 value로 갖는 dictionary를 생성하면 대치되는 단어쌍에 손쉽게 접근할 수 있다.

 

 

2) message 속 단어 구분

msg = message.split()  # list 형식, 공백 기준 구분

 

message 에서 단어들은 공백으로 구분한다.

 

split()을 이용하면 message 속 단어들을 공백 기준으로 구분하여 list에 저장할 수 있다.

 

 

3) 치환

for i in range(len(msg)):
    word = msg[i]  # i번째 단어
    if word in dct.keys():  # i번째 단어가 치환 대상인 경우
        msg[i] = dct[word]  # 해당 단어를 dct[word]로 치환

 

msg에 저장된 단어들 중, 치환 대상인 단어들을 찾아서 바꿔주면 된다.

 

임의의 단어가 치환 대상이라면, 그 단어는 dictionary의 key 값 중 하나이다.

 

 

즉, 지금 보고 있는 단어 msg[i]가 치환 대상이라면, 이 단어는 dct의 key 값 중 하나에 해당된다.

 

반대로 치환 대상이 아니라면, dct의 key 값에 없을 것이다.

 

 

msg 속 임의의 단어가 치환 대상에 해당되는 경우에만 그 단어를 치환하고, 그 외의 경우는 무시한다.

 

 

 

4) 마무리

ans = ' '.join(i for i in msg)
return ans

 

 

단어들을 치환한 상태인 msg의 자료형을 list에서 string으로 변환해야 한다.

 

' '.join을 사용하면 list에 들어있는 단어들을 공백으로 구분하면서 1개의 string으로 합칠 수 있다.

 

이 문제에서는 반환형을 string으로 요구했기에, 자료형을 string으로 변환한 다음 반환해야 한다.

 

 

 

문제 코드

def solution(snippet, message):
    # 1) 치환 대상 정리
    dct = dict()
    for i in snippet:
        k = i[0]
        v = i[1]
        dct[k] = v
        
    # 2)message 속 단어 구분
    msg = message.split()
    
    # 3) 치환
    for i in range(len(msg)):
        word = msg[i]
        if word in dct.keys():
            msg[i] = dct[word]
    
    # 4) 마무리
    ans = ' '.join(i for i in msg)
    return ans

 

 

 

위의 코드들을 다 합치면, 문제를 풀 수 있다.

 

 

시간복잡도

사용한 풀이의 시간복잡도는 O(n) 이다.

 

for문에서 snippet 과 message의 길이에 선형적으로 비례하여, 처리시간이 증가할 수 있다. 

 

하지만 dict.keys()의 시간복잡도는 Python3 기준으로 O(1)이다.

 

O(n * 1) = O(n)

 

이를 기반으로 시간복잡도를 계산하면, O(n)이 그 결과로 나온다.