[JavaScript][백준] 객체는 틀리고, Set은 맞는 이유 (백준 25192번 node.js 풀이 75% 반례)

 요약 

JavaScript 객체에는 기본적으로 ‘constructor’, ‘toString’ 등 특정한 key에 해당하는 값이 존재한다.
따라서 객체를 사용해서 문제를 푼 경우, 문자열 ‘constructor’, ‘toString’ 등이 포함된 히든 케이스를 만나면 틀린 답을 출력할 수 있다.

 

const obj = {};

console.log(obj['constructor']);
console.log(obj['toString']);

 

 

출력 결과

[Function: Object]
[Function: toString]
// 선언만 하고 아직 아무 값도 넣지 않았는데, 이미 뭔가 들어있는 이유가 뭘까요?

 

 

---

 상세 

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

 

node.js로 백준 25192번 문제 ‘인사성 밝은 곰곰이’를 풀고 있었습니다.

이번 문제를 풀기 위해선 “새로운 값이면 갯수를 세고, 이미 저장된 값이면 지나가는” 로직이 필요합니다.

key-value 형태의 자료구조(Map, Set)를 사용하는 문제입니다.

 

그런데 이번에는 JavaScript의 객체를 활용해서 풀어보기로 했습니다.

객체도 key-value 형태고, 선언도 키 값 접근도 간단한 코드로 가능하고, 무엇보다 Set과는 다르게 ES6부터 존재해 왔기 때문에 근본도 넘칩니다.

 

/* 순수 객체를 사용한 key-value 접근. */
const obj = {};

obj['myKey'] = 'myValue';
console.log(obj['myKey']); // 출력 결과 : myValue;

 

 

 

JavaScript에서는 특정 값이  null 이나  undefined 와 같은 값(흔히 말하는 ‘falsy’한 값)은 조건문이나 논리 연산자를 만나면  false 로 형변환이 됩니다.

이번 문제에서도 이러한 성질을 이용해 아래와 같은 로직을 작성했습니다.

/* 오답 코드 */
const fs = require("fs");
const input = fs.readFileSync(0, 'utf-8').trim().split('\n');

let obj = null;
let count = 0;

for(line of input.slice(1)){
    const key = line.trim();
    if(key === 'ENTER')
        obj = {}; 
        // 'ENTER'가 입력될 때마다 새로운 객체로 초기화한다.
    else if(!obj[key]){
		    // 입력받은 문자열이 객체에 key로 저장되어 있는지 확인한다.
		    // 존재하지 않을 경우에만 count를 1 증가시키고, 객체에 문자열을 key로 저장한다.
        obj[key] = true;
        count++;
    }    
}

console.log(count);

 

 

 

그런데 틀렸네요.

채점할 때마다 쭉 정답이 나오다가 75%에서 “틀렸습니다”로 끝납니다.

그렇다면 로직 자체가 틀리지는 않았고, 반례가 있는 것 같습니다.

 

 

📍 왜 틀렸을까?

input에 해당하는 문자열 중에 특정한 문자열이 포함되어 있다면 오답이 발생합니다.
‘constructor’가 포함된 테스트 케이스를 작성해 보겠습니다.

5
ENTER
constructor
abc
def
ghi

 

출력 결과

3

문제가 의도한 대로라면 constructor, abc, def, ghi가 입력될 때마다 정답이 1씩 증가해야 합니다.
따라서 정답은 4여야 합니다.

 

그런데 막상 코드를 실행하면, 출력 결과는 엉뚱하게 3이 나오죠.

이렇게 되는 이유는 JavaScript 객체에 기본적으로 ‘constructor’라는 key에 해당하는 값이 존재하기 때문입니다.

 

 

아래와 같이 새 객체 obj를 생성하고, constructor라는 key에 대응하는 값이 있는지 콘솔로 출력해 보겠습니다.

const obj = {};

console.log(obj['constructor']);

 

출력 결과

[Function: Object]

 

 

Object라는 이름을 가진 함수가 존재한다는 출력 결과가 나옵니다.

이 값은  null 이나  undefined , 0과 같이 boolean으로 변환 시  false 가 되는(falsy한) 값이 아닙니다.

따라서  !  연산자를 만나면 의도하지 않은 결과를 얻게 됩니다.

 

const obj = {};
console.log(!obj['abc']); // 임의의 문자열을 키로 사용
console.log(!obj['constructor']); // 'constructor'를 키로 사용

 

출력 결과

true
// !obj['constructor'] => !undefined => !false => true가 됩니다. 
false
// !obj['constructor'] => !(function Object(){...}) => !true => false가 됩니다. 

 

따라서 우리가 사용했던 것처럼  !obj['...'] 를 사용해 분기처리를 하는 조건문은, 이렇게 특정 문자열이 포함된 반례를 만나서 오답을 출력했던 것입니다.

 

 

📍 올바른 풀이

1. JavaScript의 Set을 사용하기

정석대로 JavaScript의 Set을 사용하는 풀이방법입니다.

/* 정답 코드 */
const fs = require("fs");
const input = fs.readFileSync(0, 'utf-8').trim().split('\\n');

let set = new Set();
let count = 0;

for(line of input.slice(1)){
    
    const key = line.trim();
    if(key === 'ENTER')
        set = new Set();
    else if(!set.has(key)){
        set.add(key);
        count++;
    }
}

console.log(count);

 

 

하지만 아래와 같은 방법들을 사용하면, 그대로 객체를 사용하면서 문제를 푸는 것도 가능합니다.

 

 

2. 객체의 key마다 임의의 값을 넣고, 일치여부에 따라 참거짓 판별하기

obj에 key에 해당하는 값이 들어있는지 여부가 아니라, 들어있는 값이 지정한 값과 정확히 일치하는지를 확인하여 보다 정확하게 조건을 판단할 수 있습니다.

const fs = require("fs");
const input = fs.readFileSync(0, 'utf-8').trim().split('\\n');

let obj = null;
let count = 0;

for (line of input.slice(1)) {
    const key = line.trim();
    if (key === 'ENTER')
        obj = {};
    else if (obj[key] !== true) {
		    // 자동 형변환이 일어나지 않도록 !=가 아니라 !==를 사용해야 합니다.
        obj[key] = true;
        count++;
    }
}

console.log(count);

 

 

 

3.  {} 대신  Object.create(null)로 객체 생성하기  

 Object.create(null) 을 사용하면 constructor가 존재하지 않는, 진정한 의미로 비어 있는 객체를 생성할 수 있습니다. 따라서 처음에 의도했던 대로 코드가 동작하는 것을 확인할 수 있습니다.

const fs = require("fs");
const input = fs.readFileSync(0, 'utf-8').trim().split('\\n');

let obj = null;
let count = 0;

for (line of input.slice(1)) {
    const key = line.trim();
    if (key === 'ENTER')
        obj = Object.create(null);
    else if (!obj[key]) {
        obj[key] = true;
        count++;
    }
}

console.log(count);

 

 

📍 왜 저런 key와 value가 들어있나요?

JavaScript는 프로토타입(Prototype) 기반의 객체지향 언어입니다.

프로토타입이란 새로운 객체를 생성할 때 원본 역할을 하는, JavaScript 언어에서 이미 만들어 놓은 객체입니다.

일반적으로 JavaScript의 객체는  Object 라는 이름을 가진 프로토타입을 원본으로 만들어지고,  Object 라는 프로토타입이 가진 속성(프로퍼티)들을 물려받게 됩니다. (좀 더 구체적으로 말하자면 원본 프로토타입이 가진 속성들을 참조할 수 있게 됩니다.)

다음과 같이 코드를 쳐 보면 어떤 속성들을 물려받게 되는지 확인할 수 있습니다.

console.log(Object.getOwnPropertyNames(Object.prototype));
// Object의 프로토타입에 어떤 속성이 들어있는지 확인해 보겠습니다.

 

출력 결과

[
  'constructor',
  '__defineGetter__',
  '__defineSetter__',
  'hasOwnProperty',
  '__lookupGetter__',
  '__lookupSetter__',
  'isPrototypeOf',
  'propertyIsEnumerable',
  'toString',
  'valueOf',
  '__proto__',
  'toLocaleString'
]

 

앞서 예시로 들었던 constructor, toString 등이 포함되어 있는 것을 확인할 수 있습니다.

 

JavaScript에서는 이렇게 물려받은 속성들도  []  연산자로 접근할 수 있습니다. 따라서 새 객체 obj를 생성하고 아무것도 넣지 않았는데도, obj[ ] 안에 위와 같은 값들이 존재하는 것을 확인할 수 있습니다.

const obj = {};

console.log(
    obj['constructor']
);

console.log(
    obj['__proto__']
);

console.log(
    obj['toString']
);

 

출력 결과

[Function: Object]
[Object: null prototype] {}
[Function: toString]

 

25192번 문제에서 주어진 제약사항은 “닉네임은 숫자 또는 영문 대소문자로 구성되어 있다”라는 것입니다. 공교롭게도 constructor, toString과 같은 프로퍼티는 영문 대소문자로만 구성되어 있고 따라서 반례가 될 수 있었던 것입니다.

 

 

📍 Object.create(null)을 사용하면?

3번 풀이에서  Object.create(null) 을 사용해서 반례를 해결했습니다.

 Object.create(null) 을 사용하면, 아무 프로토타입도 상속받지 않은 텅 빈 객체를 만들게 됩니다.
(어려운 말로 프로토타입 체인이 없는 순수한 객체를 생성하게 됩니다.)

 

console.log(Object.getOwnPropertyNames(Object.create(null)));
// Object.create(null)에 어떤 속성이 들어있는지 확인해 보겠습니다.

 

출력 결과

[]
// 아무 속성도 들어있지 않아 텅 빈 배열이 출력됩니다.

 

하지만 공식 문서에 따르면  Object.create(null) 이 코드는 실무에 적합한 코드는 아닙니다.  Object 의 프로토타입을 상속한 게 아니기 때문에, 일반적인 객체가 갖고 있는 기능이 없기 때문입니다. 그래서 오히려 실무에서 오작동할 가능성도 높고, 디버깅도 어렵습니다.

 

"An object with a null prototype can behave in unexpected ways, because it doesn't inherit any object methods from Object.prototype. This is especially true when debugging, since common object-property converting/detecting utility functions may generate errors, or lose information (especially if using silent error-traps that ignore errors)."

— mdn web docs

 

 

예를 들어서  Object.create(null) 로 만든 객체에  toString() 을 사용하면 에러가 발생합니다.

const normalObj = {}; // 일반적인 객체
const nullProtoObj = Object.create(null); // Object.create(null)로 만든 객체

console.log(normalObj); // 출력 결과 : "[object Object]"
console.log(nullProtoObj); // 에러 발생: Cannot convert object to primitive value

 

 

 

 참고자료 

이번 게시글 작성하는 데 가장 큰 도움을 주신 백준 @wizardrabbit님께 감사드립니다.

https://www.acmicpc.net/board/view/156013

 

본문 2번, 3번 풀이는 아래 질의내용을 보고 참고했습니다. (유사한 문제인 백준 1764번 듣보잡 문제에 관한 질의내용입니다.)

https://www.acmicpc.net/board/view/150855

 

Object 및 프로토타입과 관련된 내용은 아래 공식 문서를 참고했습니다.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object#null-prototype_objects

Object - JavaScript | MDN

https://developer.mozilla.org/ko/docs/Learn_web_development/Extensions/Advanced_JavaScript_objects/Object_prototypes

Object prototypes - Web 개발 학습하기 | MDN