프로그래머스 | 문자열의 최대 거리 찾기

📌 문제

랜덤한 문자열의 조합 s 안에서, 반복 없이 가장 긴 알파벳 길이를 구하는 함수를 만드세요. s는 길이가 1 이상 1,000 이하인 문자열입니다.

✨ 해결 방법

1. 이전 문제와 같이 공간이 26개 있는 새로운 배열을 만듭니다. 해당 배열은 각 알파벳의 마지막 위치를 저장합니다.

2. 각 인덱스를 알파벳 숙자에 매칭시키기 위해 아스키 코드를 사용합니다. (.charCodeAt(index))

3. 시작 인덱스, 마지막 인덱스와 최대 길이 등을 선언한 후 문자가 중복일 경우와 아닐 경우로 나눠 코드를 작성합니다.

💻 solution 1

function solution(s) {
    let start = 0; //시작 인덱스
    let end = 0; //마지막 인덱스
    let answer = 0; //결과값 (가장 긴 연속된 알파벳의 길이)
    let indexOfAlphabets = new Array(26).fill(-1); // 각 알파벳의 마지막 인덱스를 저장하는 배열

      while (end < s.length) { // 전체 길이를 순회
        const char = s[end]; //현재 위치의 문자
        
        // 현재 문자의 인덱스가 이전에 나온 중복 문자의 인덱스보다 클 경우 -> 현재 문자열에 중복 문자가 없을 경우
        if (indexOfAlphabets[char.charCodeAt() - 'a'.charCodeAt()] < start) {
            // 현재 문자의 인덱스를 저장하고, 현재까지의 길이를 계산하여 결과값 갱신
            indexOfAlphabets[char.charCodeAt() - 'a'.charCodeAt()] = end;
            answer = Math.max(answer, end - start + 1);
            end++;
        } else {
            // 중복이 발생한 경우 시작 인덱스를 중복된 문자보다 하나 뒤의 위치로 조정
            start = indexOfAlphabets[char.charCodeAt() - 'a'.charCodeAt()] + 1;
        }
    }

    return answer;
}

문자열 abcdcba로 예시를 들어서 설명하겠습니다.

1. 초기 상태

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 0, end: 0
indexOfAlphabets: [-1, -1, -1, -1, -1]
answer: 0

2. 첫 번째 'a'
   현재 문자 'a'의 인덱스는 0이고, indexOfAlphabets[0]은 -1입니다. 따라서 중복이 아니므로 end를 1 증가시켜 부분 문자열을 확장합니다.

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 0, end: 1
indexOfAlphabets: [0, -1, -1, -1, -1]
answer: 1

3. 두 번째 'b'
   현재 문자 'b'의 인덱스는 1이고, indexOfAlphabets[1]은 -1입니다. 따라서 중복이 아니므로 end를 1 증가시켜 부분 문자열을 확장합니다.

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 0, end: 2
indexOfAlphabets: [0, 1, -1, -1, -1]
answer: 2

4. 세 번째 'c'
   현재 문자 'c'의 인덱스는 2이고, indexOfAlphabets[2]은 -1입니다. 따라서 중복이 아니므로 end를 1 증가시켜 부분 문자열을 확장합니다.

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 0, end: 3
indexOfAlphabets: [0, 1, 2, -1, -1]
answer: 3

5. 네 번째 'd'
   현재 문자 'd'의 인덱스는 3이고, indexOfAlphabets[3]은 -1입니다. 따라서 중복이 아니므로 end를 1 증가시켜 부분 문자열을 확장합니다.

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 0, end: 4
indexOfAlphabets: [0, 1, 2, 3, -1]
answer: 4

6. 다섯 번째 'c'
   현재 문자 'c'의 인덱스는 4이고, indexOfAlphabets[2]는 2입니다. 따라서 중복이므로 start를 2 + 1로 이동시켜 중복 부분을 제외하고 다시 탐색합니다.

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 3, end: 4
indexOfAlphabets: [0, 1, 2, 4, -1]
answer: 4

7. 여섯 번째 'b'
   현재 문자 'b'의 인덱스는 5이고, indexOfAlphabets[1]은 1입니다. 따라서 중복이 아니므로 end를 1 증가시켜 부분 문자열을 확장합니다.

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 3, end: 5
indexOfAlphabets: [0, 5, 2, 4, -1]
answer: 4

8. 일곱 번째 'a'
   현재 문자 'a'의 인덱스는 6이고, indexOfAlphabets[0]은 0입니다. 따라서 중복이 아니므로 end를 1 증가시켜 부분 문자열을 확장합니다.

s: a b c d c b a
i: 0 1 2 3 4 5 6
start: 3, end: 6
indexOfAlphabets: [6, 5, 2, 4, -1]
answer: 4

💻 solution 2

function solution(s) {
  // 각 알파벳의 마지막 등장 위치를 저장할 객체
  const indexOfAlphabets = {};
  // 부분 문자열의 시작 위치를 나타내는 변수
  let start = 0;

  // reduce 함수를 사용하여 문자열을 순회하면서 가장 긴 부분 문자열의 길이를 찾음
  return s.split('')
    .reduce((answer, current, index) => {
      // 만약 현재 문자 c가 이전에 등장한 적이 있다면
      if (start <= indexOfAlphabets[current]) {
        // 부분 문자열의 시작 위치를 현재 문자의 다음 위치로 갱신
        start = indexOfAlphabets[current] + 1;
      }

      // 현재 문자의 등장 위치를 저장
      indexOfAlphabets[current] = index;
      
      // 가장 긴 부분 문자열의 길이를 계산하여 반환
      return Math.max(answer, (index - start) + 1);
    }, 0);
}

reduce를 사용하여 조금 더 쉽게 구현할 수 있습니다.
longest 는 누산기, c는 현재 선택한 문자, i는 현재 선택한 요소의 인덱스입니다.

코드에서 start <= indexOfAlphabets[c] 는,
"현재 부분 문자열의 시작 위치 start가 현재 문자 c의 이전 등장 위치와 같거나 작다"를 검사하고 있습니다.
따라서 if 문은 중복이 발생했을 때를 나타냅니다. solution 1과 같이 중복이 발생하면 start를 갱신하여 이전의 중복 다음 문자부터 탐색하도록 합니다.

중복이 아닐 경우, 현재 문자의 등장 위치를 갱신합니다.

또한 예시를 들어서 설명해보겠습니다.

1. 초기 상태

s: a b c c a b
start: 0
indexOfAlphabets: []
answer: 0

2. 첫 번째 'a'
   현재 문자 'a'의 인덱스 0을 indexOfAlphabets에 저장하고, start는 그대로 0입니다.

s: a b c c a b
current: a, index: 0
start: 0
indexOfAlphabets: [0]
answer: 1

3. 두 번째 'b'
   현재 문자 'b'의 인덱스 1을 indexOfAlphabets에 저장하고, start는 그대로 0입니다.

s: a b c c a b
current: b, index: 1
start: 0
indexOfAlphabets: [0, 1]
answer: 2

4. 세 번째 'c'
   현재 문자 'c'의 인덱스 2을 indexOfAlphabets에 저장하고, start는 그대로 0입니다.

s: a b c c a b
current: c, index: 2
start: 0
indexOfAlphabets: [0, 1, 2]
answer: 3

5. 네 번째 'c' : 중복!!
   현재 문자 'c'의 인덱스 3을 indexOfAlphabets에 저장하고, start는 2+1인 3으로 업데이트 됩니다.

s: a b c c a b
current: c, index: 3
start: 3
indexOfAlphabets: [0, 1, 3]
answer: 3 //현재 1

6. 다섯 번째 'a' : 중복!!
   현재 문자 'a'의 인덱스 4을 indexOfAlphabets에 저장하고, start는 그대로 3입니다.

s: a b c c a b
current: a, index: 4
start: 3
indexOfAlphabets: [4, 1, 3]
answer: 3 //현재 2

7. 여섯 번째 'b' : 중복!!
   현재 문자 'b'의 인덱스 5을 indexOfAlphabets에 저장하고, start는 그대로 3입니다.

s: a b c c a b
current: c, index: 5
start: 3
indexOfAlphabets: [4, 5, 3]
answer: 3 //현재 3

따라서, 주어진 문자열 "abccab"에서 반복되지 않는 가장 긴 부분 문자열은 "abc"와 "cab"이며, 길이는 3입니다. 함수는 이 값을 반환합니다.