프로그래머스 – 가장 가까운 같은 글자 문제 Python

by
Programmers
Meet the best programming lessons in videos and practices. Programmers provide programing lessons, algorithm problems, programming competitions, and blockchain materials.

프로그래머스 문제풀이

문제

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

문제설명

문자열 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은 영어 소문자로만 이루어져 있습니다.

입출력 예

sresult
“banana”[-1, -1, -1, 2, 2, 2]
“foobar”[-1, -1, 1, -1, -1, -1]

입출력 예 설명

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

입출력 예 #2
설명 생략

문제해석과정

  1. 문자열 s의 각 위치 문자를 분석하려 한다.
  2. 각 글자들을 왼쪽부터 오른쪽으로 읽어나간다.
  3. 해당 문자가 처음 나왔다면 -1 을 출력한다.
  4. 해당 문자가 이전에 나왔다면 몇 칸 전에 나왔는지 확인하여 출력한다.
  5. 해당 문자가 이전에 여러번 나왔다면 가장 가까운 위치를 출력한다.

위 같은 문제 및 제한사항을 해석하고 문제풀이를 시작하면 됩니다.

나의 풀이

def solution(s):
    answer = []
    for i in range(len(s)):                #해당 문자열 길이만 큼 반복
        if s[i] in s[:i]:                  #해당 문자가 현재 인덱스까지의 문자열에 존재한다면
            while s[:i].count(s[i])>1:     #현재 인덱스까지의 문자열내에 여러개 존재한다면 1개가 남을때까지 반복
                s = s.replace(s[i],'0',1)  #해당 문자 replace
            answer.append(i-s.index(s[i])) #가까운 해당 문자의 길이 출력
        else:                              #해당 문자가 현재 인덱스까지의 문자열에 존재하지 않는다면
            answer.append(-1)              #-1 출력
    return answer

다른 사람의 풀이

이번 문제는 뭔가 어거지로 정답을 맞추긴했지만 다른 사람들 풀이를 보고 하나 또 배워가는 문제였던 것 같네요.

다른분들은 dict()를 이용해서 해당문자를 키로 주고 해당문자가 새로 확인될때마다 값을 변경해주도록 멋지게 풀었네요.

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

관련 링크

문제해결과정에서 기초가 부족하다고 느껴지시면 아래 정리 글을 참고해주세요.

Python 문법 총 정리1 – Zzrany Blog
여기는 Python을 공부하며 학습한 내용을 정리하는 블로그입니다. 해당 포스팅에서는 개발시 참고하실 수 있도록 Python 문법들을 한눈에 보이도록 필요한 내용만 간략하게 정리해보았습니다.
Python 문법 총 정리2 – Zzrany Blog
여기는 Python을 공부하며 학습한 내용을 정리하는 블로그입니다. 해당 포스팅에서는 개발시 참고하실 수 있도록 Python 문법들을 한눈에 보이도록 필요한 내용만 간략하게 정리해보았습니다.