4/25 화 [프로그래머스] 해시(Hash), 완주하지 못한 선수와 Object, Map의 시간복잡도 TIL

[프로그래머스] 해시 > 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

나의 풀이:

// 총 시간 복잡도는: O(M) + 2*O(N) => M = N - 1일 것을 생각하면 대략 3 * O(N), 즉 O(N)이다. 
function solution(participants, completion) {
	// 1. completion 객체 명단을 만든다. => O(M)
	const completed = new Map()
	for (const completer of completion) { // O(M)
		if (completed.has(completer)) { // O(1)
			completed.set(completer, completed.get(completer) + 1); // O(1)
		} else {
			completed.set(completer, 1); // O(1)
		}
	}

	// 2. participants 객체 명단을 만든다. => O(N)
	const participated = new Map()
	for (const participant of participants) { // O(N)
		participated.set(participant, (participated.get(participant) ?? 0) + 1); // O(1) + O(1)
	}
	
	// 3. 둘의 키와 밸류값을 비교한다. => O(N)
	for (const participant of participated.keys()) { // O(N)
		if (!(completed.has(participant))) { // O(1)
			return participant;
		}
		if (participated.get(participant) !== completed.get(participant)) { // O(1) + O(1)
			return participant;
		}
	}

	// 입출력 제한 사항을 벗어난 오류가 있을 경우
	return "미완주자를 찾지 못하였습니다."
}

• 시간 복잡도를 3O(N) → 2O(N)으로 개선한 버전(어차피 O(N)으로 같지만 그래도) :

  // 다른 풀이
  // 1. 완주자 배열 순회 ---> 
  // 2. { 이름: 등장 횟수 } 형태의 객체 만들고, 참가자 배열 순회---> 
  // 3. 이름이 완주 객체에 존재하면 등장횟수 차감, 존재하지 않거나 값이 0이면 리턴
  // => 이렇게 하면 명단을 하나만 만들면 되므로 내가 했던(위의) 방식보다 더 효율적이다. 
  // 시간 복잡도는 O(M) + O(N) = 2*O(N) => O(N)
  function solution2(participant, completion) {
  	const completeObj = {}
  	// 완주자 명단 만들기 
  	completion.forEach(name => { // O(M)
  		// 명단에 없는 이름이면 { 이름: 1 } 
  		if (!completeObj[name]) completeObj[name] = 1 // O(1) + O(1)
  		// 이미 올라간 이름이면 등장횟수++ 
  		else completeObj[name]++ // O(1)
  	})
  	
  	// 참가자와 완주자 명단 비교 
  	return participant.find(name => { // O(N)
  		// 현 참가자가 완주자 명단에 있고, 값이 0이 아니면 값-- 
  		if (completeObj[name]) completeObj[name]-- // O(1) + O(1)
  		// 명단에 없거나 값이 0이면 리턴 
  		else return name
  	})
  }

• 위의 풀이를 Map으로 구현하기:

  // => 굳이 Map으로 할 필요가 없다. '검색'을 하지 않을 땐 Map의 이점이 없다. 
  // 시간 복잡도는 O(M) + O(N) = 2*O(N) => O(N)
  function solution3(participants, completion) {
  	const completionMap = new Map();
  
  	// 1. 완주자 명단 만들기 => O(M)
  	completion.forEach((name) => { // O(M)
  		completionMap.set(name, (completionMap.get(name) ?? 0) + 1); // O(1) + O(1)
  	})
  
  	// 2. 참가자와 완주자 명단 비교 => O(N)
  	return participants.find((name) => { // O(N)
  		// 현 참가자가 완주자 명단에 있고, 값이 0이 아니면 값--
  		if (completionMap.has(name) && completionMap.get(name)) { // O(1) + O(1)
  			completionMap.set(name, completionMap.get(name) - 1); // O(1) + O(1)
  		// 명단에 없거나 값이 0이면 리턴
  		} else {
  			return name;
  		}
  	})
  }

테스트 코드:

const { solution } = require('./103-해시-완주하지 못한 선수');

describe('Unfinished Marathoner', () => {
	[
		{ participants: ['leo'], completion: [], result: 'leo' },
		{ participants: ['ben', 'leo'], completion: ['ben'], result: 'leo' },
		{ participants: ['ben', 'leo', 'hash'], completion: ['ben', 'leo'], result: 'hash' },

		// 동명이인 'leo'가 있고 'leo'가 미완주자인 경우
		{ participants: ['ben', 'leo', 'hash', 'leo'], completion: ['ben', 'leo', 'hash'], result: 'leo' },
		// 동명이인 'leo'가 있고 'leo'가 미완주자가 아닌 경우 
		{ participants: ['ben', 'leo', 'hash', 'leo'], completion: ['ben', 'leo', 'leo'], result: 'hash' },
		
		// 프로그래머스 예시
		{ participants: ["leo", "kiki", "eden"], completion: ["leo", "eden", ], result: "kiki" },
		{ participants: ["marina", "josipa", "nikola", "vinko", "filipa"], completion: ["josipa", "filipa", "marina", "nikola"], result: "vinko" },
		{ participants: ["mislav", "stanko", "mislav", "ana"], completion: ["stanko", "ana", "mislav"], result: "mislav" },
		
		// 전부 동명이인
		{ participants: ['ben', 'ben','ben','ben','ben', 'ben','ben',], completion: ['ben', 'ben','ben','ben','ben','ben',], result: 'ben' },
	]
	.forEach(({ participants, completion, result }) => {
		it(`should return ${result} when given participant and completion lists are ${participants}, ${completion}`, () => {
			expect(solution(participants, completion)).toEqual(result);
		})
	})
})

알게된 것:

• 자바스크립트의 Map과 Object의 시간 복잡도에 대해.

  ⇒ Map과 Object가 다른 점에는 키로 삼을 수 있는 종류가 다르다는 것과 이터러블이고 아니고가 다르다는 점 외에, 시간 복잡도가 다르다는 점도 포함된다. Map과 Object 모두 삽입 삭제에 O(1) 시간복잡도를 가지지만, 특정 키를 갖고 있는지를 찾을 때 차이가 발생한다. Object의 경우 여러 방법으로 특정 키가 있는지 없는지를 찾을 수 있는데 방법에 따라 걸리는 시간이 많이 달라진다. Map의 경우는 has와 keys 등의 메소드가 모두 거의 확실하게 O(1)의 시간복잡도만으로 가능하므로 복잡한 Object에 비해 이점을 가진다고 볼 수 있다. 또한, Map의 경우 keys, values, entries 메소드가 모두 이터레이터를 반환하므로 요소를 일일이 순회하여 배열을 만들어 반환하는 Object의 keys, values, entries에 비해 시간과 공간 복잡도 면에서 장점을 가진다.

  (참고: 자바스크립트에서 Object에 특정 키가 존재하는지 확인하는 가장 효율적인 방법에 관한 토론과 실험들: https://stackoverflow.com/questions/1098040/checking-if-a-key-exists-in-a-javascript-object)

  (참고: Object의 keys, entries의 시간 복잡도를 V8 엔지니어가 답하다 → 기본적으로 O(N), 자료가 수천 개가 넘어가면 O(NlogN)이 된다고 함 - https://stackoverflow.com/questions/64909990/object-entries-time-complexity)(여기도 동시 답변 - https://stackoverflow.com/questions/7716812/object-keys-complexity)

[JavaScript] Map 객체의 시간 복잡도

Q. 자바스크립트 객체 Map의 메소드 set과 has, get은 O(1)인가?

A. 이곳의 답변에 따르면, V8의 Map과 Set은 hash table 기반으로 작성됐기 때문에 get & set & add & has 시간 복잡도를 거의 O(1)이라고 여길 수 있다고 한다.

Big-O of Maps:

• Insertion — O(1)

• Removal — O(1)

• Access — O(1)

• Searching — O(1)

Big-O of Maps methods:

• set, delete, get, has — O(1)

• keys, values, entries — O(1)

  ⇒ 반환되는 것이 이터레이터이므로 O(1)이라고 볼 수 있다.

(추가로 참고하면 좋은: V8이 Map과 Set 등의 자료구조에서 해시 테이블을 구현한 방법 - https://v8.dev/blog/hash-code)

(참고: Map.keys는 O(1)인가? - https://stackoverflow.com/questions/49659209/is-it-constant-time-to-call-map-prototype-keys-in-javascript)

(참고: 해시 테이블의 시간 복잡도 표 - https://www.bigocheatsheet.com/)

[JavaScript] 객체(Object)의 시간 복잡도

Big-O of Objects:

• Insertion — O(1)

• Removal — O(1)

• Access — O(1)

• Searching — O(n)

Big-O of Object methods:

• Object.keys — O(n)

• Object.values — O(n)

• Object.entries — O(n)

• hasOwnProperty — O(1)

⇒ 단순히 삽입하고 삭제하는 거라면 Map이 아닌 그냥 객체도 충분히 빠르다.

[JavaScript] 배열(Array)의 시간 복잡도

Big-O of Arrays:

• Insertion — It depends. Insertion at the end is O(1). But insertion at the beginning is o(n)

• Removal — It depends. Removal at the end is O(1). But in between or at the beginning is o(n)

• Access — O(1)

• Searching — O(n)

Big-O of Array methods:

• push, pop — O(1)

• shift, unshift, concat, slice, splice — O(n)

• forEach/map/filter/reduce/etc. — O(n)

(참고: https://javascript.plainenglish.io/performance-of-arrays-and-objects-in-javascript-through-the-lens-of-big-o-5a7c5891a43f)

---

※ 위 내용은 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※

Uploaded by N2T