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

📝24.01.31

🔗 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/142086?language=csharp

문제 설명

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

[C#] 내가 작성한 풀이

보자마자 Dictionary를 활용하는 문제라는 생각이 들었다. string s의 각 char를 키 값으로, 가장 최근의 char의 위치를 value 값으로 저장하고 있으면 검색하기도 용이하고 수정하기도 쉽기 때문에 아래의 방식으로 풀이했다.

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string s) {
        int[] answer = new int[s.Length];
        
        Dictionary<char, int> dic = new Dictionary<char, int>();
        
        for(int i = 0; i < s.Length; i++) {
        	//dic에 s[i]라는 key값이 있다면
            if(dic.ContainsKey(s[i])) {
                int temp = i - dic[s[i]];
                answer[i] = temp;
                dic[s[i]] = i;
            } else { //없다면 s[i]라는 key값과 i라는 value 값 추가
                answer[i] = -1;
                dic.Add(s[i], i);
            }
        }
        return answer;
    }
}

[C#] 남이 작성한 풀이

이중 for문을 돌리는 방법도 있었다. 매번 자기 자신과 같은 가장 가까운 뒤의 글자를 찾는 것인데, 주어진 string s의 길이가 길지 않아서 가능한 것 같다.

제한 사항 : 1 ≤ s의 길이 ≤ 10,000

using System;

public class Solution {
    public int[] solution(string s) {
        int[] answer = new int[s.Length];

        for(int i = 0; i < s.Length; ++i)
        {
            int shortestPosition = -1;

            for(int j = i - 1; j >= 0; --j)
            {
                if(s[j] == s[i])
                {
                    shortestPosition = i - j;
                    break;
                }
            }
            answer[i] = shortestPosition;
        }

        return answer;
    }
}

[C++] 내가 작성한 풀이

위의 Dictionary풀이를 C++에선 map으로 적용할 수 있다.

map의 경우에는 키 값을 가지고 있는지 여부를 iterator 로 판별할 수 있다. 만약 m.find() == m.end()가 true라면 (해당 find를 위해 map의 마지막까지 iterator가 이동했다면) 그동안 찾던 key 값이 없었단 뜻이므로 map에 해당 값이 없던 것이다.

이 방법으로 위의 ContainsKey() 기능을 구현했고 거의 유사한 알고리즘으로 풀이하였다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    map<char, int> m;
    
    for(int i = 0; i < s.length(); i++) {
        if(m.find(s[i]) == m.end()) {
            answer.push_back(-1);
            m.insert({s[i], i});
        } else {
            answer.push_back(i - m[s[i]]);
            m[s[i]] = i;
        }
    }
    return answer;
}

[C++] 남이 작성한 풀이

더 나은 풀이는 없었고, unordered_map을 사용한 경우도 있었다. string s에 어떤 순서에 동일한 문자가 나왔었을지 알 수가 없기 때문에 이 문제에는 unordered_map을 사용하는 것이 성능적 향상을 이끌지는 못할 것 같다.