Computer/알고리즘

[JS] 백준 5430: AC

치즈랑 2026. 4. 6. 16:10

https://www.acmicpc.net/problem/5430

// 5430 AC

// 문자열, 파싱
/* 설계

1. T 입력 받음
1.1 T=0인 경우 return (엣지 케이스)

2. T만큼 값을 출력하는 함수 실행
2.1 start 인덱스, 전체 원소 개수, 그리고 방향 flag 초기화

3. 값을 출력하는 함수
3.1 입력받은 함수, n, 그리고 배열을 저장
배열의 경우 JSON.parse(입력문자열)
3.2 엣지 케이스. n이 0인 경우, 함수 p에 'D'가 있다면 return "error", 아니면 return []

4. 입력받은 함수 p만큼 순회
4.1 문자열이 R인 경우 방향 flag 전환
4.2 문자열이 D인 경우 정방향이면 start+1 count-1, 역방향이면 count-1
4.3 count <0 이라면 return "error"

4.4 순회가 끝난다면
result = 배열.slice(start, start+count)
역방향인 경우 result.reverse()
return JSON.stringify(result)
*/

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .replaceAll("\r", "") // just in case
  .trim()
  .split("\n");

function testCase(p, n, arr) {
  let start = 0;
  let count = n;
  let isReversed = false;

  for (const v of p) {
    if (v === "R") {
      isReversed = !isReversed;
      continue;
    }

    // R이 아니라면 항상 D이므로
    if (!isReversed) {
      start++;
      count--;
    } else {
      count--;
    }

    if (count < 0) {
      return "error";
    }
  }

  const result = arr.slice(start, start + count);

  if (isReversed) result.reverse();

  return JSON.stringify(result);
}

/**
 * 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램
 * @param {string[]} input
 * @returns {string} 최종 결과
 */
function solution(input) {
  const T = Number(input[0]);

  if (T === 0) return;

  const results = [];

  for (let i = 0; i < T; i++) {
    const line = i * 3 + 1;

    const p = input[line];
    const n = Number(input[line + 1]);
    const arr = JSON.parse(input[line + 2]);

    results.push(testCase(p, n, arr));
  }

  return results.join("\n");
}

const result = solution(input);
console.log(result);

 

 

설계하면서 고민한 것들

1. V8 엔진과 운영체제로 보는 배열 연산 (pop vs shift/unshift) - 처음에 투포인터를 선택하면서 생긴 궁금증

투포인터를 선택하신 것은 V8 엔진의 메모리 처리 방식을 고려했을 때 최상의 선택입니다. 왜 배열의 앞부분을 조작하는 unshift나 shift가 뒷부분을 조작하는 pop이나 push보다 압도적으로 비싼지, 로우레벨 단에서 설명해 드리겠습니다.

메모리 할당 (OS와 Heap)

자바스크립트에서 배열을 생성하면, 운영체제는 V8 엔진의 힙(Heap) 메모리 영역에 연속된 메모리 블록을 할당하려고 시도합니다(물론 JS 배열은 객체라서 희소 배열인 경우 해시맵처럼 동작하기도 하지만, 일반적으로 요소가 꽉 찬 배열은 C++의 배열처럼 연속된 메모리를 가집니다 - V8에서는 이를 PACKED_ELEMENTS라고 부릅니다).

콜 스택(Call Stack)의 역할

콜 스택은 실제 배열 데이터를 들고 있지 않습니다. 콜 스택에는 힙 메모리에 생성된 해당 배열의 시작 메모리 주소(참조값) 만이 저장됩니다. 우리가 arr[2]에 접근하려고 하면, 콜 스택에서 힙 메모리 주소를 꺼낸 뒤, '시작 주소 + (인덱스 * 데이터 크기)'라는 단순한 포인터 덧셈 연산을 통해 $O(1)$의 속도로 해당 메모리 공간에 직접 접근합니다.

pop 연산이 $O(1)$인 이유

pop은 배열의 맨 끝 원소를 제거하는 연산입니다. 연속된 메모리 공간에서 맨 마지막 데이터만 지우고 (또는 접근 불가능하게 논리적으로 삭제 처리하고), 배열의 내장 프로퍼티인 length를 1 감소시키면 끝납니다. 메모리 내의 다른 원소들은 자신의 자리를 전혀 옮길 필요가 없기 때문에 CPU 입장에서는 아주 가벼운 연산입니다.

unshift / shift 연산이 $O(N)$인 이유

배열의 맨 앞, 즉 인덱스 0번 자리에 데이터를 넣거나 빼는 연산입니다. 연속된 메모리 공간으로 할당되어 있기 때문에, 맨 앞의 원소가 빠지거나 새로운 원소가 들어오면 그 뒤에 있는 모든 원소들의 인덱스가 바뀌어야 합니다.

  1. V8 엔진은 메모리의 인덱스 접근성($O(1)$)을 유지하기 위해, 0번 인덱스에 공간을 만들기(또는 채우기) 시작합니다.
  2. 이를 위해 인덱스 1번부터 끝까지의 모든 메모리 블록에 있는 데이터를 하나씩 옆으로 복사해서 옮기는(Memory Copy/Move) 작업을 수행합니다.
  3. 원소가 10만 개라면, 운영체제와 CPU는 10만 번의 메모리 이동 작업을 수행해야 합니다.

결과적으로 데이터가 커질수록 shift/unshift는 치명적인 성능 저하를 가져옵니다. 투포인터를 사용하여 $O(N^2)$의 메모리 이동 비용을 포인터 변수 2개만 조작하는 $O(N)$으로 바꾼 본인의 설계 로직에 확신을 가지셔도 좋습니다.

 

2. JSON.parse(string)의 동작 원리

자바스크립트 엔진(V8 기준) 내부에서 JSON.parse는 단순히 문자열을 쪼개는 수준이 아니라, 컴파일러의 구문 분석(Parsing) 과정을 축소시킨 형태로 동작합니다.

  1. 어휘 분석 (Lexical Analysis): 문자열을 한 글자씩 스캔하며 의미 있는 단위(Token)로 쪼갭니다. 예를 들어 [는 배열의 시작, 123은 숫자, ,는 구분자, ]는 배열의 끝으로 인식합니다.
  2. 구문 분석 (Syntactic Analysis): 쪼개진 토큰들이 올바른 JSON 문법을 따르는지 확인하며 트리 구조(AST와 유사한 형태)를 형성합니다.
  3. 객체 생성 (Object Allocation): * V8 엔진은 분석된 구조를 바탕으로 실제 힙(Heap) 메모리에 자바스크립트 객체나 배열을 할당합니다.
    • 이번 문제처럼 숫자로 이루어진 배열 [1,2,3]을 파싱할 때, V8은 이를 힙 내부에 FixedArray라는 연속된 메모리 구조로 생성하여 매우 빠르게 접근할 수 있도록 최적화합니다.
    • split과 map(Number)를 조합하는 것보다 JSON.parse가 훨씬 빠른 이유는, C++ 레벨에서 최적화된 상태로 한 번의 스캔(Single Pass)만으로 파싱과 타입 변환을 동시에 끝내기 때문입니다.

 

2. JSON.stringify(object)의 동작 원리

이 과정은 반대로 메모리에 있는 객체 구조를 문자열로 직렬화(Serialization)하는 과정입니다.

  1. 재귀적 탐색 (Recursive Traversal): 배열이나 객체의 첫 번째 요소부터 마지막 요소까지 순차적으로 방문합니다.
  2. 직렬화 (Serialization): 각 요소의 자바스크립트 타입을 확인하고, 그에 맞는 문자열 형태로 변환합니다.
    • 숫자 타입 1은 문자 '1'로, 배열은 [와 ] 문자를 붙이는 식입니다.
  3. 문자열 빌더 (String Builder): * 자바스크립트에서 문자열은 **불변(Immutable)**입니다. 따라서 += 연산자로 문자열을 계속 더하면 매번 새로운 메모리 할당이 일어나 매우 느려집니다.
    • V8 엔진 내부의 JSON.stringify는 C++ 레벨에서 효율적인 버퍼(Buffer) 혹은 스트링 빌더를 사용하여 최종 문자열을 한 번에 조립한 뒤, 마지막에 자바스크립트 문자열 객체로 만들어 반환합니다. 이 덕분에 대규모 배열도 아주 빠르게 문자열로 바꿀 수 있습니다.

 

3. V8 엔진 레벨: for...of의 작동 원리와 이터러블

for...of는 마법이 아닙니다. 자바스크립트 엔진은 이 구문을 만나면 내부적으로 **이터러블 프로토콜(Iterable Protocol)**을 따르는 코드로 변환하여 실행합니다.

어떤 객체가 '이터러블'하다는 것은 객체 내부에 [Symbol.iterator]()라는 메서드가 구현되어 있다는 뜻입니다. 배열과 문자열 모두 V8 엔진 내부 C++ 코드를 보면 이 메서드가 기본적으로 내장되어 있습니다.

엔진은 for (const v of p)를 다음과 같은 논리적 흐름으로 번역합니다.

// 1. 순회를 관리할 이터레이터 객체를 생성 (내부에 index 상태를 가짐)
const iterator = p[Symbol.iterator](); 

// 2. 루프 시작
let result = iterator.next();
while (!result.done) {
    const v = result.value;
    
    // ... 사용자가 작성한 루프 내부 로직 실행 ...
    
    // 3. 다음 원소 요청
    result = iterator.next();
}

4. 운영체제 레벨: 배열과 문자열이 모두 가능한 이유

그렇다면 왜 배열과 문자열 모두 이 프로토콜을 사용할 수 있을까요? 메모리에 저장되는 물리적 형태가 근본적으로 비슷하기 때문입니다.

  • 문자열(String): V8 엔진에서 문자열(예: SeqOneByteString)은 힙 메모리에 연속된 바이트 블록으로 저장됩니다. A, B, C가 메모리에 나란히 붙어있습니다.
  • 배열(Array): (요소가 꽉 찬 일반적인 배열의 경우) V8 엔진의 FixedArray 구조체 역시 힙 메모리에 요소들의 참조값을 연속된 메모리 블록으로 할당합니다.

운영체제 입장에서는 둘 다 그저 '연속된 메모리 공간에 할당된 데이터 덩어리'일 뿐입니다.

이터레이터가 메모리를 탐색하는 과정

  1. p[Symbol.iterator]()를 호출하면, 힙 메모리를 가리키는 시작 주소와 현재 위치를 기억하는 **내부 커서(Index)**를 가진 이터레이터 객체가 생성됩니다.
  2. next() 메서드가 호출될 때마다, 엔진은 커서의 인덱스를 1씩 증가시킵니다.
  3. CPU 레지스터를 이용해 시작 주소 + (커서 * 데이터 크기) 메모리 번지에 접근하여 문자 1개 혹은 배열 원소 1개를 $O(1)$의 속도로 가져옵니다.
  4. 더 이상 읽을 데이터가 메모리 블록 끝을 넘어가면 done: true를 반환하여 루프를 종료합니다.

 

5. [Symbol.iterator]를 가지면 무조건 연속된 메모리인가?

결론부터 말씀드리면 아닙니다. [Symbol.iterator]는 데이터가 메모리에 어떻게 생겼는지(물리적 구조)를 의미하는 것이 아니라, **"이 데이터 덩어리들을 하나씩 차례대로 꺼내줄게"라는 약속(인터페이스, Protocol)**입니다.

  • 연속된 메모리인 경우 (배열, 문자열): 앞서 설명한 것처럼 인덱스를 1씩 더해가며 메모리를 쓱쓱 훑기만 하면 되므로 이터레이터를 구현하기 가장 쉽습니다.
  • 연속되지 않은 메모리인 경우 (Map, Set, Linked List 등): 데이터가 힙 메모리 이곳저곳에 흩어져 포인터로 연결되어 있어도 상관없습니다. 이터레이터 내부의 next() 함수가 '다음 메모리 주소를 찾아가는 로직'만 제대로 구현하고 있다면 완벽하게 for...of를 사용할 수 있습니다.
  • 아예 메모리에 없는 경우 (Generator): 심지어 메모리에 배열을 아예 만들어두지 않고, next()가 호출될 때마다 CPU가 즉석에서 다음 숫자를 계산해서 뱉어내는 '무한 피보나치 수열' 같은 것도 이터러블이 될 수 있습니다.

결론: [Symbol.iterator]는 "내가 다음 데이터를 가져오는 방법을 알고 있다"는 자격증일 뿐, 메모리의 연속성 여부를 보장하지 않습니다.

 

6. 객체(Object)의 메모리 구조는 연속적일까?

자바스크립트의 일반 객체({})는 배열처럼 단순하게 쫙 나열된 연속 메모리 블록이 아닙니다. V8 엔진은 성능 최적화를 위해 객체를 매우 복잡하고 동적인 구조로 관리합니다.

V8은 객체를 최대한 정적 타입 언어(C++)의 struct처럼 빠르게 동작하게 만들고 싶어 합니다. 이를 위해 **히든 클래스(Hidden Class, 또는 Shape)**라는 개념을 도입했습니다.

  1. In-object Properties (연속된 편): 객체를 처음 만들고 속성이 몇 개 없을 때는, V8이 객체 자체가 있는 메모리 공간 안에 속성값들을 나란히 저장합니다. 이때 히든 클래스는 "A 속성은 시작 주소에서 +8바이트 위치에 있어"라는 식의 오프셋(Offset) 지도를 만듭니다. 접근 속도가 매우 빠릅니다.
  2. Dictionary Mode (비연속적): 하지만 속성이 너무 많아지거나, 코드가 실행되는 도중에 delete로 속성을 지우고 새로운 속성을 마구 추가하면 히든 클래스의 지도가 망가집니다. V8은 최적화를 포기하고 이 객체를 해시 테이블(Hash Table) 구조인 딕셔너리 모드로 바꿉니다. 이때부터 데이터는 힙 메모리 사방에 흩어져 비연속적으로 저장됩니다.

일반 객체({})는 [Symbol.iterator]를 기본적으로 가지고 있지 않습니다. 객체의 속성들은 배열처럼 '순서'를 보장하도록 설계되지 않았기 때문입니다. (물론 ES6 이후 객체 속성의 생성 순서가 어느 정도 보장되긴 하지만, 근본적으로 객체는 순차 조회를 위한 자료구조가 아닙니다.)

 

7. Object vs Map: 값 저장 방식과 키(Key) 타입의 차이

이 부분이 프론트엔드 최적화와 직결되는 아주 중요한 포인트입니다.

Object의 키가 문자열(또는 Symbol)만 가능한 이유

언어의 태생적인 목적 때문입니다. 자바스크립트의 객체는 본래 obj.name 이나 obj.age처럼 **식별자(Identifier)**를 통해 값을 묶어두는 용도로 만들어졌습니다. 프로그래밍 언어에서 식별자는 기본적으로 텍스트(문자열)로 해석됩니다.

따라서 숫자를 키로 넣더라도 내부적으로는 문자열로 강제 형변환(Coercion)이 일어납니다. obj[1] = "A" 를 수행하면 엔진은 obj["1"] = "A" 로 바꾸어 히든 클래스에 등록합니다. 만약 객체를 키로 넣으려 하면 obj["[object Object]"] 라는 무의미한 문자열 키로 뭉개져 버립니다.

Map의 저장 원리: 해시 테이블과 참조값

ES6에서 도입된 Map은 객체의 이런 한계를 극복하기 위해 진정한 의미의 **자료구조인 해시 맵(Hash Map)**으로 새롭게 설계되었습니다.

Map은 값을 저장할 때 키(Key)가 들어오면 **해시 함수(Hash Function)**를 돌립니다.

  • 원시값(숫자, 문자열 등): 값 자체를 해싱하여 고유한 인덱스(Bucket 주소)를 만듭니다.
  • 객체(Object, Array, Function): 객체가 문자열로 바뀌는 것이 아닙니다. 힙 메모리상에 존재하는 해당 **객체의 물리적인 참조값(메모리 주소 자체)**이나 엔진 내부의 고유 ID를 해시 함수에 집어넣어 해시 코드를 생성합니다.

그렇기 때문에 겉보기에 똑같이 생긴 빈 객체 두 개를 넣어도, 메모리 주소가 다르므로 서로 완벽하게 다른 키로 동작할 수 있는 것입니다.

 
const map = new Map();
const obj1 = {};
const obj2 = {};

map.set(obj1, "첫번째 객체 데이터");
map.set(obj2, "두번째 객체 데이터"); // 덮어쓰이지 않고 따로 저장됨!

게다가 Map은 내부적으로 삽입된 순서를 기억하는 연결 리스트(Linked List) 같은 보조 구조를 함께 관리하기 때문에, 기본적으로 [Symbol.iterator]를 탑재하고 있어 for...of로 넣은 순서대로 순회할 수 있습니다.

728x90

'Computer > 알고리즘' 카테고리의 다른 글

[C++] 프로그래머스 [1차] 프렌즈  (0) 2026.06.13
[JS] 백준 16928: 뱀과 사다리 게임  (0) 2026.04.08
[JS] 프로그래머스 가장 큰 수  (1) 2025.01.27
[JS] 프로그래머스 K번째수  (2) 2025.01.26
[JS] 프로그래머스 주식가격  (1) 2025.01.25

'Computer/알고리즘'의 다른글

  • 현재글[JS] 백준 5430: AC

관련글

티스토리툴바