1071: 암호 해석 - 오고고

Link : judge.koreatech.ac.kr/problem.php?id=1071

---

1. 문제

• 당신은 제 3차 세계대전에서 상대국의 암호를 해석하기 위해 고용된 컴퓨터 과학자입니다.
  상대국의 암호는 당신을 혼란에 빠뜨리기 위해 의미있는 문구 사이에 “ogo”로 시작하며 그 뒤에 “go” 라는 문자열이 0번 이상 반복되는 의미없는 문구들을 담아 놓았습니다. 예를 들어서 “ogo”, “ogogo”, “ogogogo” 는 당신을 혼란에 빠뜨리기 위한 의미없는 문자열이며, “go”, “og”, “ogog”, “ogogog”, “oggo”, 는 당신을 혼란에 빠뜨리기 위한 의미없는 문자열이 아닙니다.
  의미없는 문자열은 항상 가질 수 있는 최대 길이로 간주하여야 합니다. 예를 들어서 “ogogoo”라는 암호가 주어질 때 “ogo”를 의미없는 문자로, “goo”를 의미있는 문자로 취하는 것은 불가능하며 “ogogo” 를 의미없는 문자로 간주하여야 합니다.
  우수한 컴퓨터 과학자인 당신은 주어진 암호문에서 모든 의미없는 문자열을 등장할 때 마다 *** 로 대체하기로 하였습니다. 주어진 암호문에 대하여 당신의 작업물을 출력 해 주세요.

 

---

2. 문제의 조건

• 1 <= n <= 100 (문자열 길이)

 

---

3. 문제 접근

• 시간 복잡도
  
  100개의 데이터이므로 O(N^4.5)이내의 시간에 풀면 된다고 생각하였습니다.

 

• 아이디어
  
  ogo를 찾을 수 없을 때 까지 무한번 반복합니다.
  최대 100개의 길이이므로 ogo 33개 이상 반복하지 않습니다.
  또한, ogo 다음 go는 48번 이상을 반복할 수 없습니다. 최악의 50번 즉 N/2.
  
  즉, 시간복잡도 O(N)에 해결할 수 있습니다.

 

---

4. 풀이 방법

• find으로 ogo의 위치를 찾습니다
  find으로 찾지 못하면 -1을 return 하여 break하면 그것이 정답.
• idx부터 len(str) - 1 까지 반복합니다.
  "gogogo" 일 경우, "go"를 판단하기위해 -1 지점에서 해야한다.
• 만약 str[idx + 3] == 'g' and str[idx + 4] == 'o' 면
  "ogogo"
   01234
  계속있으므로 pos를 2증가시킵니다. 이것을 g o가 안나올 때까지 반복합니다.
• 만약 끝지점에 도달하거나 g o가 안나온다면 idx + pos 지점까지 전부 ***으로 치환합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/51

 

---

 

cjw.git@gmail.com