알림 문구 템플릿 전개

문제

알림 발송 시스템은 문구 템플릿과 치환 값 목록을 받아 최종 문구를 만듭니다.

solution(template, entries) 를 구현해 전개된 문구를 문자열로 반환하세요.

• template — 치환 자리(placeholder)가 섞인 문구
• entries — "키=값" 형태의 문자열 배열

치환 값 해석 규칙

1. 각 항목은 가장 앞의 = 하나 를 기준으로 키와 값으로 나뉩니다. 즉 "expr=x=y+1" 의 키는 expr, 값은 x=y+1 입니다.
2. 값은 빈 문자열일 수 있습니다 ("x=" → 키 x, 값 "").
3. 같은 키가 여러 번 등장하면 뒤에 나온 항목이 앞의 것을 덮어씁니다.

템플릿 전개 규칙

템플릿을 왼쪽부터 한 번 훑으면서 다음을 적용합니다.

1. {{ 는 여는 중괄호 한 개 { 로, }} 는 닫는 중괄호 한 개 } 로 출력합니다.
2. {키} 는 해당 키의 값으로 바꿉니다. 키가 entries 에 없으면 <none> 을 출력합니다.
3. 그 밖의 문자는 그대로 출력합니다.
4. 치환으로 삽입된 값은 다시 해석하지 않습니다. 값 안에 {, }, {다른키} 가 들어 있어도 글자 그대로 결과에 남습니다.

예시

template = "안녕하세요 {name}님, 주문 {order}건이 준비되었습니다."
entries  = ["name=김철수", "order=3"]
→ "안녕하세요 김철수님, 주문 3건이 준비되었습니다."
 
template = "{{a}} = {a}"
entries  = ["a=1"]
→ "{a} = 1"
   ({{ → "{", a, }} → "}" 이므로 앞부분은 치환되지 않는다)
 
template = "{{{name}}}"
entries  = ["name=Bob"]
→ "{Bob}"
   ({{ → "{", {name} → "Bob", }} → "}")
 
template = "{a}"
entries  = ["a={b}", "b=STOP"]
→ "{b}"
   (삽입된 값 "{b}" 는 재해석하지 않으므로 STOP 이 되지 않는다)
 
template = "{a}-{b}"
entries  = ["a=1"]
→ "1-<none>"

제약 조건

• 1 ≤ template.length ≤ 10,000
• 0 ≤ entries.length ≤ 200, 각 항목 길이 ≤ 200
• entries 의 각 항목에는 = 가 최소 한 개 있고, 키는 길이 1~20 의 영문 소문자·숫자·_ 이다
• template 의 치환 자리 키도 영문 소문자·숫자·_ 로만 이루어진다
• template 은 항상 올바른 형태다. 즉 모든 { 는 {{ 의 일부이거나 올바른 {키} 의 시작이고, 모든 } 는 }} 의 일부이거나 {키} 의 끝이다
• 값과 템플릿의 일반 문자에는 공백·한글 등 임의의 문자가 올 수 있다

시간 복잡도 목표: O(N + M) (N = 템플릿 길이, M = entries 전체 길이)