1097: 실습시험 연습문제: 가장 긴 접두부분문자열 찾기

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

---

1. 문제

• 문자열 배열이 주어졌을 때, 각 문자열에 공통적으로 들어가 있는 가장 긴 접두사를 찾으시오.
  예) "abddd", "abcd". "abz"이면 "ab"가 답입니다.

 

---

2. 문제의 조건

• 1 <= T <= 1,000

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한이 1초에 케이스 1000개가 주어졌습니다. O(N^2.66) 이내에 풀면 된다고 생각하였습니다.

 

• 아이디어
  
  O(N^2)으로 넉넉히 주어져있으므로, 완전탐색을 이용하면 풀 수 있다고 생각했습니다.

 

---

4. 풀이 방법

• 맨 처음 문자열 idx 0부터 나머지 모든 idx 0번을 비교하고 전부다 같을 경우 변수에다 idx 0번의 str를 담아줍니다.
• 만약, 다를 경우 2중 for을 var(변수)를 이용하여 벗어나고 token을 출력해주면됩니다.
• ex 2 abcdd abcd abc
  
  다음의 예시경우 abcdd의 a를 기준으로
  1. "abcd"의 0번째인 a, "abc"의 0번째인 a를 비교하고
  2. "abcd"의 1번째인 b, "abc"의 1번째인 b를 비교하고
  3. "abcd"의 2번째인 c, "abc"의 2번째인 c를 비교하는데
  
  "abcd"의 4번째인 d는 "abc"는 4번째가 없어서 IndexOutOfRange Error가 발생할 수 있습니다. 그러므로 예외처리를 해주셔야합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/53

 

---

 

cjw.git@gmail.com