[프로그래머스][11번째로 푼 문제] 142086. 가장 가까운 같은 글자 (241028)

구분

코딩테스트 연습 > 연습문제

채점결과

• 정확성: 100.0
• 합계: 100.0 / 100.0

제출 일자

2024년 10월 28일 12:47:08

문제 설명

문자열 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을 완성해주세요.

제한사항

• 1 ≤ s의 길이 ≤ 10,000
• s은 영어 소문자로만 이루어져 있습니다.

입출력 예

s	result
"banana"	[-1, -1, -1, 2, 2, 2]
"foobar"	[-1, -1, 1, -1, -1, -1]

입출력 예 설명

입출력 예 #1
지문과 같습니다.

입출력 예 #2
설명 생략

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

 

 

def solution(s):
    temp = {}
    
    for i in range(len(s)):
        if s[i] in temp:
            temp[s[i]][i] = 1
        else:
            temp[s[i]] = [0] * len(s)
            temp[s[i]][i] = 1

    result = [-1] # 처음 숫자는 무조건 -1일 수 밖에 없음
    
    for i in range(1, len(s)):
        _ = -1
        for j in range(i-1, -1, -1):
            if temp[s[i]][j] == 1:
                _ = i - j
                break
        result += [_]
        
    return result

 

 

알겠습니다. 느낀점 변환에서는 앞으로 출처를 포함하지 않겠습니다. 수정된 내용을 다시 작성해 드릴게요.

느낀 점

사실 풀면서도 반복문을 너무 많이 쓴다고 생각하긴 했는데 어떻게 줄여야 할지 감이 안왔다.

아이디어는 반복문으로 돌면서 해당 글자가 있는 위치를 1, 아닌 곳은 0으로 배열을 채우기였다.

예) banana의 경우:

[
    "b" => [1, 0, 0, 0, 0, 0],
    "a" => [0, 1, 0, 1, 0, 1],
    "n" => [0, 0, 1, 0, 1, 0]
]

이런 식으로 기록한 후 다시 글자 인덱스 별로 순회를 돌되 (현재 인덱스) -1부터 0까지 역순으로 순회를 돌면서 배열에 1로 기록된 가장 가까운 인덱스를 찾아서 (현재 인덱스) - (찾은 인덱스)로 하여 result 배열을 만들어서 반환하였다.

차선욱 , 박호윤 , 탈퇴한 사용자 , kimcharzz 외 370 명님의 풀이

def solution(s):
    answer = []
    dic = dict()
    for i in range(len(s)):
        if s[i] not in dic:
            answer.append(-1)
        else:
            answer.append(i - dic[s[i]])
        dic[s[i]] = i

    return answer

네. 간단합니다. 좋아요. 난 왜 이걸 생각 못했지?

dn09yooon@gmail.com님의 풀이

def solution(s):
    return [s[i::-1].find(s[i], 1) for i in range(len(s))]

파이써닉.와우.감탄.네...