문제
1부터 N까지 순서대로 이어 쓴 문자열에서, N이 처음 등장하는 위치(1-indexed)를 구하라.
입력
자연수 N이 주어진다 (1 이상 10,000 이하).
출력
N이 처음 등장하는 위치를 출력한다.
예제
| 입력 | 출력 |
|---|---|
12 | 14 |
풀이
1부터 N까지 이어 쓴 문자열을 만들고, N 문자열의 위치를 검색한다.
- 1부터 N까지의 수를 문자열로 이어 붙인다
find()메서드로 N의 문자열 표현이 처음 등장하는 인덱스를 찾는다- 0-indexed를 1-indexed로 변환하여 출력한다
핵심 아이디어: N이 최대 10,000이므로 이어 쓴 문자열의 최대 길이는 약 40,000자로, 직접 생성하여 검색해도 충분하다.
코드
sn = input()
n = int(sn)
snum = "".join(map(str, range(1, n + 1)))
pos = snum.find(sn) + 1
print(pos)복잡도
- 시간: O(N * log N) — 문자열 생성 및 검색
- 공간: O(N * log N) — 이어 쓴 문자열 저장