가장 짧은 문자거리 JavaScript 풀이: 양방향 탐색

읽기 전에 알아두면 좋아요

아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.

양방향 스캔: 왼쪽·오른쪽 상태로 가장 가까운 문자 찾기왼쪽과 오른쪽에서 각각 확인한 결과를 합쳐 가까운 위치를 찾습니다. 왼쪽과 오른쪽에서 구한 최소거리 후보를 같은 위치에서 결합합니다.
문자열 알고리즘 기초: 순회·문자 판별·대소문자 변환·숫자 추출문자열의 각 문자를 순서대로 읽고 위치를 확인하는 방법을 복습합니다. 문자와 위치를 나누어 읽고 입력의 순서를 보존하는 방법입니다.

개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.

과정 위치와 선택 복습 안내

과정 위치: 문자열 응용 · 문제

과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.

JavaScript로 문법·실행 복습하기 (선택)

개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.

가장 짧은 문자거리 문제에서는 문자열의 각 위치에 대해 어떤 거리를 구하나요?

문자열의 각 위치에서 지정한 문자까지의 가장 짧은 거리를 구하는 문제입니다. 문자열·인덱스·거리의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.

적용 조건·범위: 자료에는 최소 길이와 t가 s에 없는 경우의 출력 규칙이 따로 적혀 있지 않습니다. 이 글의 유한한 거리 풀이·정답 비교는 t가 적어도 한 번 있는 입력을 대상으로 합니다. t가 없는 입력에 임의의 정답을 부여하지 않습니다.

본문 근거: MDN Math.min 문서 · Node.js fs.readFileSync 문서

문제·입출력·제약

문자열 s와 문자 t가 주어집니다. s의 각 위치에서 t가 있는 위치까지 떨어진 거리 중 가장 작은 값을, 원래 문자 순서대로 출력합니다. 거리는 두 인덱스의 차이이며, 현재 문자가 t이면 거리는 0입니다.

입력: 첫 줄에 문자열 s와 문자 t가 공백으로 구분되어 주어집니다.
s와 t는 소문자로 주어지며, s의 길이는 100을 넘지 않습니다.
출력: 각 위치의 최소거리를 순서대로 한 줄에 공백으로 구분해 출력합니다.
자료에는 최소 길이와 t가 s에 없는 경우의 출력 규칙이 따로 적혀 있지 않습니다. 이 글의 유한한 거리 풀이·정답 비교는 t가 적어도 한 번 있는 입력을 대상으로 합니다. t가 없는 입력에 임의의 정답을 부여하지 않습니다.

사용자 제공 자료의 「섹션 3. 문자열 탐색.pdf」 4쪽과 「4. 가장 짧은 문자거리.txt」를 2026년 10월 14일 직접 읽었습니다. TXT는 HTML 안에서 함수를 호출하는 풀이 예제이며 별도의 온라인 채점 플랫폼 주소는 없습니다. 아래 코드는 PDF의 한 줄 입력 형식에 맞춘 Node.js 실행 파일입니다.

원본 예제 입력

teachermode e

원본 예제 출력

1 0 1 2 1 0 1 2 2 1 0

직접 풀어보기

먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.

내 풀이 JavaScript0 / 6,000바이트

function solve(input) {
    // 입력 문자열을 읽고 문제의 출력 문자열을 반환하세요.
    return '';
}

소문자 s와 문자 t를 읽고 각 위치에서 가장 가까운 t까지의 거리를 공백으로 연결한 문자열로 반환합니다. t가 s에 적어도 한 번 있는 입력이 대상입니다. 입력 예시 전체를 문자열 input으로 전달하고 출력 문자열을 반환합니다. solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. LF·CRLF·끝 줄바꿈 없음에 같은 결과를 반환합니다. Tab은 다음 항목으로 이동합니다. 입력 영역 오른쪽 아래를 끌어 높이를 조절할 수 있습니다.

비밀키·개인정보는 입력하지 마세요. 코드는 이 페이지에만 유지됩니다.

해답·해설 보기

function solve(input) {
    const [text, target] = input.trim().split(/\s+/);
    const distances = [];
    let distance = text.length;
    for (const character of text) {
        distance = character === target ? 0 : distance + 1;
        distances.push(distance);
    }
    distance = text.length;
    for (let i = text.length - 1; i >= 0; i--) {
        distance = text[i] === target ? 0 : distance + 1;
        distances[i] = Math.min(distances[i], distance);
    }
    return distances.join(' ');
}

def solve(input):
    text, target = input.split()
    distances = []
    distance = len(text)
    for character in text:
        distance = 0 if character == target else distance + 1
        distances.append(distance)
    distance = len(text)
    for i in range(len(text) - 1, -1, -1):
        distance = 0 if text[i] == target else distance + 1
        distances[i] = min(distances[i], distance)
    return ' '.join(map(str, distances))

import java.util.Scanner;
import java.util.StringJoiner;

class Solution {
    public String solve(String input) {
        Scanner scanner = new Scanner(input);
        String text = scanner.next();
        char target = scanner.next().charAt(0);
        int[] distances = new int[text.length()];
        int distance = text.length();
        for (int i = 0; i < text.length(); i++) {
            distance = text.charAt(i) == target ? 0 : distance + 1;
            distances[i] = distance;
        }
        distance = text.length();
        for (int i = text.length() - 1; i >= 0; i--) {
            distance = text.charAt(i) == target ? 0 : distance + 1;
            distances[i] = Math.min(distances[i], distance);
        }
        StringJoiner result = new StringJoiner(" ");
        for (int value : distances) result.add(String.valueOf(value));
        return result.toString();
    }
}

소문자 s와 문자 t를 읽고 각 위치에서 가장 가까운 t까지의 거리를 공백으로 연결한 문자열로 반환합니다. t가 s에 적어도 한 번 있는 입력이 대상입니다. 입력 예시 전체를 문자열 input으로 전달하고 출력 문자열을 반환합니다. new Solution().solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. LF·CRLF·끝 줄바꿈 없음에 같은 결과를 반환합니다.

#include <algorithm>
#include <sstream>
#include <string>
#include <vector>

std::string solve(const std::string& input) {
    std::istringstream in(input);
    std::string text;
    char target;
    in >> text >> target;
    int n = static_cast<int>(text.size());
    std::vector<int> distances(n);
    int distance = n;
    for (int i = 0; i < n; i++) {
        distance = text[i] == target ? 0 : distance + 1;
        distances[i] = distance;
    }
    distance = n;
    for (int i = n - 1; i >= 0; i--) {
        distance = text[i] == target ? 0 : distance + 1;
        distances[i] = std::min(distances[i], distance);
    }
    std::ostringstream result;
    for (int i = 0; i < n; i++) {
        if (i > 0) result << ' ';
        result << distances[i];
    }
    return result.str();
}

using System;

public class Solution {
    public string Solve(string input) {
        string[] tokens = input.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
        string text = tokens[0];
        char target = tokens[1][0];
        int[] distances = new int[text.Length];
        int distance = text.Length;
        for (int i = 0; i < text.Length; i++) {
            distance = text[i] == target ? 0 : distance + 1;
            distances[i] = distance;
        }
        distance = text.Length;
        for (int i = text.Length - 1; i >= 0; i--) {
            distance = text[i] == target ? 0 : distance + 1;
            distances[i] = Math.Min(distances[i], distance);
        }
        return string.Join(" ", distances);
    }
}

소문자 s와 문자 t를 읽고 각 위치에서 가장 가까운 t까지의 거리를 공백으로 연결한 문자열로 반환합니다. t가 s에 적어도 한 번 있는 입력이 대상입니다. 입력 예시 전체를 문자열 input으로 전달하고 출력 문자열을 반환합니다. new Solution().Solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. LF·CRLF·끝 줄바꿈 없음에 같은 결과를 반환합니다.

접근 과정

왼쪽에서 가장 가까운 t까지의 거리를 저장합니다

왼쪽부터 읽으며 t를 만나면 거리 변수 distance를 0으로 바꿉니다. 다른 문자를 만나면 1을 더합니다. 매번 이 값을 배열 answer 뒤에 넣으면 현재 위치의 왼쪽에서 가장 가까운 t까지의 거리가 쌓입니다.

아직 t를 만나지 않았을 때는 Infinity를 사용합니다. 실제 거리를 찾았다는 뜻이 아니라, 이 방향에 후보가 없다는 표시입니다. 첫 t를 만나면 0으로 바뀌므로 이후의 거리는 정상적으로 1씩 증가합니다.

오른쪽에서 구한 거리와 비교합니다

다시 distance를 Infinity로 초기화하고 맨 뒤에서 앞으로 읽습니다. 같은 규칙으로 오른쪽의 가까운 t까지의 거리를 계산합니다. Math.min(answer[i], distance)로 왼쪽 거리와 오른쪽 거리 중 작은 값을 같은 배열 칸에 저장합니다.

원본 풀이에서 유지한 점과 바꾼 점

TXT의 두 번 순회하는 접근과 배열에 결과를 모으는 방식은 유지했습니다. 원본은 처음 거리를 1000으로 둡니다. 길이 100 이하에서 실제 거리는 최대 99이므로 충분히 큰 값이지만, 이 글에서는 “아직 이 방향에서 찾지 못함”이 드러나도록 Infinity로 표현했습니다. 원본의 짧은 변수 p는 distance로 바꾸고 입력·출력을 추가했습니다.

t가 없는 입력에서는 양쪽 모두 Infinity가 남습니다. 아래 코드가 그 값을 출력하는 것은 구현의 동작일 뿐, 자료가 정의한 정답이나 채점 규칙이 아닙니다.

해설과 정답의 근거

왼쪽 탐색에서는 가장 최근에 만난 t가 현재 위치의 왼쪽 후보 중 가장 가깝습니다. 그보다 앞의 t는 더 멀리 있으므로 다시 비교할 필요가 없습니다. 오른쪽 탐색에서도 같은 이유로 가장 최근에 만난 t가 오른쪽 후보 중 가장 가깝습니다.

현재 위치에서 가장 가까운 t는 왼쪽이나 오른쪽에 있거나, 현재 위치 자체에 있습니다. 양쪽에서 구한 최솟값을 비교하면 세 경우를 모두 포함합니다. t 자신은 두 방향 모두 거리 0이므로 그대로 유지됩니다. 어느 한쪽에만 t가 있으면 유한한 거리와 Infinity 중 유한한 쪽을 선택합니다.

전체 코드를 solution.cjs로 저장하고 예제 입력을 input.txt에 넣은 뒤 node solution.cjs < input.txt로 실행하세요. 외부 패키지는 필요하지 않습니다. 직접 실행할 때는 표준 입력을 읽고, 다른 파일에서 불러올 때는 solution 함수만 사용할 수 있도록 실행 부분을 구분했습니다.

function solution(s, t) {
  const answer = [];
  let distance = Infinity;

  for (const char of s) {
    if (char === t) distance = 0;
    else distance++;
    answer.push(distance);
  }

  distance = Infinity;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === t) distance = 0;
    else distance++;
    answer[i] = Math.min(answer[i], distance);
  }

  return answer;
}

if (require.main === module) {
  const fs = require('node:fs');
  const [s, t] = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
  process.stdout.write(solution(s, t).join(' ') + '\n');
}

module.exports = solution;

입력의 앞뒤 줄바꿈을 제거하고 /\s+/로 두 값을 나눕니다. 이 문제의 소문자 문자열에는 내부 공백이 없으며, LF·CRLF·끝 줄바꿈 없는 입력을 같은 방식으로 읽습니다. 결과 배열은 공백 하나로 연결해 한 줄로 출력합니다.

예제 추적

teachermode를 왼쪽부터 읽으면 첫 e 이전의 t는 아직 왼쪽 후보가 없습니다. 이후 e를 지날 때마다 거리가 0으로 돌아갑니다.

왼쪽 탐색 후: ∞ 0 1 2 3 0 1 2 3 4 0
오른쪽 탐색의 거리: 1 0 3 2 1 0 4 3 2 1 0
각 칸의 작은 값: 1 0 1 2 1 0 1 2 2 1 0

여기서 ∞는 코드의 Infinity를 읽기 쉽게 적은 표시입니다. 인덱스 4의 h는 왼쪽 e까지 3, 오른쪽 e까지 1이므로 1로 바뀝니다. 인덱스 7의 m은 왼쪽까지 2, 오른쪽까지 3이므로 기존 2를 유지합니다.

경계값과 시간·공간 복잡도

다음은 원본 예제와 별도로 만든 확인 입력입니다.

a a → 0: 한 문자만 있을 때
aaaa a → 0 0 0 0: 모두 t일 때
abbb a → 0 1 2 3: 맨 앞에만 t가 있을 때
bbba a → 3 2 1 0: 맨 뒤에만 t가 있을 때
abcba a → 0 1 2 1 0: 양끝의 t 사이에서 가까운 쪽이 바뀔 때
길이 100의 문자열에서 t가 한쪽 끝에만 있으면 반대쪽 끝의 거리는 99입니다.

2026년 10월 14일 Node.js v24.19.0에서 원본 예제 1개와 별도 확인 입력 15개를 LF·CRLF·끝 줄바꿈 없음으로 각각 실행해 48회 모두 예상 출력과 일치했습니다. 추가로 a·b·c로 만든 길이 1~8의 모든 문자열 중 대상 문자가 존재하는 27,990개 조합을 전수 비교했습니다. 각 위치에서 모든 대상 위치를 다시 찾는 별도 기준 풀이와 결과가 일치했습니다.

시간 복잡도 O(n): 길이 n의 문자열을 두 번 읽습니다. 입력 분리와 결과 연결도 입력·출력 길이에 비례하며, n≤100 범위에서 처리할 수 있습니다.
공간 복잡도 O(n): n개의 결과 배열과 입력·출력 문자열이 필요합니다. 결과 배열을 제외한 탐색용 변수는 O(1)입니다.

공식 채점 서버에 제출한 결과는 아닙니다. 원본이 정의하지 않은 t 부재와 빈 문자열의 출력 규칙까지 검증했다고 주장하지 않습니다.

자가 확인

오른쪽 탐색을 빼면 bbba a에서 어떤 문제가 생기나요?
두 번째 탐색 전에 distance를 다시 초기화해야 하는 이유를 설명할 수 있나요?
변형 질문: 최소거리 대신 가장 가까운 t의 위치를 반환한다면 무엇을 더 저장해야 할까요? 양쪽 거리가 같은 경우 어느 쪽을 고를지도 먼저 정해 보세요.

확인 기준 보기

한 방향에서 보이지 않는 후보를 반대 방향이 보완한다는 점을 설명하면 됩니다. 위치를 반환하는 변형에서는 최근 t의 인덱스도 필요하고, 같은 거리의 선택 규칙은 원본 거리 문제에는 없던 새 조건입니다.

문자를 순서대로 읽는 연습은 숫자만 추출 풀이에서 복습할 수 있습니다. 원본 자료의 다음 문제는 “문자열 압축”입니다. 아래 자동 학습 이동의 다음 글은 현재 사이트 과정 순서에 따라 표시되며 원본의 다음 문제와 다를 수 있습니다.

기술 동작 참고: MDN Math.min 문서, Node.js fs.readFileSync 문서를 2026년 10월 14일 확인했습니다. 문제 조건과 예제는 위에서 밝힌 제공 TXT·PDF를 기준으로 했습니다.

글 소개·학습 준비·전체 목차

가장 짧은 문자거리는 왼쪽에서 한 번, 오른쪽에서 한 번 읽으며 구한 거리 중 작은 값을 고르면 됩니다. “같은 문자가 여러 곳에 있을 때, 각 위치에서 가장 가까운 문자를 어떻게 찾을까요?”라는 질문을 풀어 봅니다. 문자열 인덱스·배열·반복문·조건문을 알고 있다면, 모든 위치를 다시 탐색하지 않고 최소거리 배열을 만들 수 있습니다.

설명용 문자열 eabce의 양끝 e에서 가운데를 향한 화살표와 오른쪽 아래 갈색 곰: 가장 짧은 문자거리를 양방향으로 찾는 표지

이 글이 도움이 되었나요?

조회 중

이어서 공부하기

체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 전처리할 문자와 비교할 문자를 구분하고 마지막 문자·마지막 묶음을 확인하세요.

같은 주제의 문제에 적용하며 방금 배운 개념을 확인합니다.

권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.

원래 과정 목록 순서 (선택)

읽음 기록

읽음 — / 전체 57개 · 필수 57개

이 글을 쓴 해비

웹사이트를 제작·운영하고, 개인 서비스와 자동화·AI 도구를 만듭니다. 직접 만들며 배운 내용과 문제 해결 과정을 BlogFlow에 기록합니다.

새 글 받아보기

RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.

RSS 피드 구독하기

가장 짧은 문자거리 풀이: 양방향 탐색으로 최소거리 구하기