[프로그래머스/C++] 가장 가까운 같은 글자 (Lv.1)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/142086?language=cpp

프로그래머스

1. 문제 접근

문자열에서 각 문자를 기준으로

이전에 같은 문자가 등장한 적이 있는지 확인하는 문제이다.

• 처음 등장한 문자라면 -1
• 이전에 등장했다면 현재 위치와 이전 위치의 거리 출력

예를 들어 "banana" 라면:

문자 이전 같은 문자 위치 거리

문자	이전 같은 문자 위치	거리
b	없음	-1
a	없음	-1
n	없음	-1
a	1	2
n	2	2
a	3	2

결과:

[-1,-1,-1,2,2,2]

이 문제는 크게 2가지 방식으로 해결할 수 있다.

1. 이전 문자들을 전부 탐색하는 방식 (이중 반복문)
2. 문자의 마지막 위치를 저장하는 방식 (map 활용) ⇒ 핵심
   
   

2. 풀이 (2개)

• 1번 풀이 - 이중 반복문 탐색
  기본적인 방식이다. 현재 문자 기준으로 앞쪽 문자들을 모두 확인하면서 같은 문자를 찾는다.
  가장 마지막에 발견된 같은 문자와의 거리를 저장하면 된다.
  

  #include <string>
  #include <vector>
  
  using namespace std;
  
  vector<int> solution(string s) {
      vector<int> answer;
  
      for (int i = 0; i < s.size(); i++) {
  
          int distance = -1; 
          // 기본 값 -1로 설정 -> 같은 문자가 없으면 -1로 출력 
          
          // 현재 문자(i) 이전까지 탐색
          for (int j = 0; j < i; j++) {
          
  
              // 같은 문자 발견시 거리 계산 (i-j)
              if (s[i] == s[j]) {
                  distance = i - j;
              }
          }
  
          answer.push_back(distance);
      }
  
      return answer;
  }

  - 이중 반복문으로 문자열의 길이가 길어질수록 비효율적인 코드
  
  
• 2번 풀이 - map 활용
  

  #include <string>
  #include <vector>
  #include <map>
  
  using namespace std;
  
  vector<int> solution(string s)
  {
      map<char, int> mp; 
      vector<int> answer;
  
      for (int i = 0; i < s.size(); ++i)
      {
          if (mp.find(s[i]) != mp.end())
              answer.push_back(i - mp[s[i]]);
          else
              answer.push_back(-1);
  
          mp[s[i]] = i; //(핵심) 현재 문자의 위치 갱신 의미 
      }
  
      return answer;
  }

그림으로 설명

3. 문법 설명

• map
  map은 key-value 형태로 데이터를 저장하는 컨테이너이다.
  

  map<char, int> mp;

  
  

  자료형	역할
  char	key
  int	value

  // 예시
  mp['a'] =3;
  -> key: a, value: 3
  -> 문자 'a'의 위치를 3으로 저장
  

• find()
  

  // 특정 key가 존재하는지 확인한다.
  mp.find(s[i])
  
  // 존재하지 않으면 아래를 반환한다.
  mp.end()
  
  //따라서 2번 풀이가 아래 처럼 if문을 사용한 것
  if(mp.find(s[i]) != mp.end())

4. 최종 요약

이 문제는 "이전에 같은 문자가 어디 있었는가?" 를 찾는 문제이다.

• 1번 풀이 - 이중 반복문 사용, 직관적, 구현 쉬움, 시간복잡도 O(N²)
• 2번 풀이 - map 사용, 이전 위치 저장, 한 번만 순회, 시간복잡도 O(N)

⇒ 2번 풀이가 훨씬 알고리즘 적으로 효율적 구조이다.

순서대로 1번 풀이 -> 2번 풀이 결과