1098: 첫 유일 문자 찾기

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

---

1. 문제

• 소문자로만 구성된 주어진 문자열에서 한번만 등장하는 첫 문자를 찾아 그것의 위치를 출력하시오.
  예) "koreatech"이면 0. 설명: 한 번만 등장하는 문자들은 k, o, r, a, t, c, h이며 가장 먼저 등장한 문자는 k이므로 색인값 0이 출력되어야 함.
  예) "lovelove"이면 -1. 설명: 한 번만 등장하는 문자가 없음 

 

---

2. 문제의 조건

• 1 <= T <= 1,000
• 소문자로 구성된 문자열

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 테스트케이스가 1000개 이므로 O(N^2.66)시간 이내의 해결하면 된다고 생각하였습니다.

 

• 아이디어
  
  순서가 있는 dict와 list(or tuple)를 이용하여 풀 수 있다고 생각하였습니다.
  차례대로  dict[s] = [cnt, idx] 형식으로 하여 문제를 충분히 풀 수 있습니다.
  
  즉, O(N^2)의 시간 이내에 해결할 수 있습니다.

 

---

4. 풀이 방법

• str의 0번째부터 끝까지 탐색한다.
• 만약 str[i]번째가 dict() 안에 없을 경우, dict자료형으로 idx와 함께 추가해준다.
• 만약 이미 존재한다면 dict()의 0번째인 cnt를 하나 증가시켜줍니다.
• 만약 탐색이 끝나고, data가 0 (입력값이 없는 경우)라면 -1을 출력해줍니다.
• 또한, data를 전체적으로 탐색하면서 dict의 0번째(cnt)가 1인경우 출력해줍니다. 하지만 1인 경우가 없을 경우 -1을 출력합니다.
  
  ※ Python 3.7 부터 dict은 넣는 순서대로 들어갑니다.

 

---

5. 소스코드

• cjw-git.tistory.com/55

 

---

 

cjw.git@gmail.com

 

www.flowdas.com/2018/01/23/dict-is-ordered.html