[프로그래머스] 가장 가까운 글자

[문제]

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

• b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
• a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

[틀린풀이]

def solution(s):
    answer = []
    arr=[]
    result=[]
    a=[]
    for i in s:
        answer.append(i)
    for i,j in enumerate(answer):
        print(i,j)
        if (j not in arr):
            result.append(-1)
            arr.append(j)
        else:
            for k in range(len(arr)):
                if(arr[k]==j):
                    result.append(i-k)
                    arr.append(j)
                           
    #같은 값이 나오는 인덱스를 찾아 뺀 후 append
    return result

 

문제를 읽고 나는 빈 배열을 하나 생성해서 문자열 s에서 하나씩  arr(빈 배열)에 넣은 다음 arr에 있는 문자와 s의 n번째 글자가 같아지면 두 인덱스의 길이 차를 구해서 문제를 풀려고 했다.

 

하지만 이 방법은 같은 글자가 3개 이상일 때 가까운 글자를 찾기에 부적절한 방법이었다.

또한 이 방식대로 해결했다고 하여도 이중 for문이 사용되어 시간복잡도 O(n^2)을 가진다.

 

[맞는 풀이]

def solution(s):
    answer = []
    last = {}  # 각 문자가 마지막으로 나온 위치 저장

    for i, ch in enumerate(s):
        print(i,ch)
        if ch in last:
            answer.append(i - last[ch])
        else:
            answer.append(-1)

        last[ch] = i  # 현재 위치 갱신
    return answer

 

빈 딕셔너리 last를 생성한 후 각 문자가 마지막으로 나온 위치를 저장한다.

enumerate 함수로 문자열 s의 값을 하나씩 키:값 형태로 추출한다.

만약 값이 last에 있는 문자라면 answer에 현재 인덱스(키)와 마지막으로 나온 위치를 뺀 값을 append한다.

그렇지 않을 경우 -1을 append한다.

for문이 돌 때마다 last에 저장되어 있는 문자가 마지막으로 나온 위치를 갱신해주면,

문자열 s가 끝날때까지 조건문에 따라 answer에 맞는 값을 추가한다.

 

[시간복잡도]

O(n) - for문

풀이에서 for문이 한 번 사용되었으므로 시간복잡도는 O(n)이 된다.