일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- 웅진씽크빅
- 리액트
- 유데미
- react
- 개발자부트캠프
- javascript
- #프로젝트캠프 #프로젝트캠프후기 #유데미 #스나이퍼팩토리 #웅진씽크빅 #인사이드아웃 #IT개발캠프 #개발자부트캠프 #리액트 #react #부트캠프 #리액트캠프
- 타입스크립트
- 인사이드아웃
- 스나이퍼팩토리
- 해시
- 프로그래머스
- BFS
- 알고리즘
- CS
- 자바스크립트
- 프로젝트캠프
- 네트워크
- typescript
- react-query
- 프로세스
- Algorithm
- App Runner
- ip
- html
- cs #네트워크
- React.js
- 스레드
- 메모리
- IT개발캠프
- Today
- Total
Bin's Blog
[프로그래머스] Level2 - 롤케이크 자르기(Javascript) 본문
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
▶ 문제 요약
1. 철수와 동생은 케이크의 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 나누어진 것으로 판단
2. 철수랑 동생은 동일한 토핑의 개수를 맛봐야 한다.
3. 공평하게 자르는 방법의 수를 찾아라.
▶ 실패 코드
function set(number) {
let set = new Set(number);
return set;
}
function solution(topping) {
let answer = 0;
let left = 0;
let right = topping.length;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
let leftTopping = topping.slice(0, mid), rightTopping = topping.slice(mid, topping.length);
let leftSet = set(leftTopping).size, rightSet = set(rightTopping).size;
if (leftSet == rightSet) {
answer++;
}
if (leftSet < rightSet) {
left++;
} else if (leftSet > rightSet) {
right--;
}
}
console.log(answer)
}
▶ 실패한 이유
- 이 코드가 통과할 줄 알았는데 시간이 엄청 오래 걸린다. 이유 주어진 배열의 길이는 최대 1,000,000이다. 내 코드에서 Set()함수와 슬라이싱 하는 부분은 각각 O(n)의 시간복잡도를 가진다.
- 최선의 경우: O(n) 루프가 한 번만 실행되는 경우
- 최악의 경우: O(n^2) 루프가 n 번 실행되고, 각 루프에서 슬라이싱과 집합 계산이 최악의 시간복잡도를 가지는 경우)
- 입력값의 길이가 최대 1,000,000인 경우, 최악의 시간복잡도는 O(1,000,000 ^ 2)이므로 매우 비효율적인 알고리즘이다.
- 그니까 시간초과가 난다. 문제를 제대로 안 읽나? 반성의 시간이 필요하다...
▶ 정답 코드
function solution(topping) {
let answer = 0;
// Map() 함수 생성
let freq = new Map();
// Set() 함수 생성
let leftFreq = new Set();
// Map에 일단 입력값을 다 넣어준다.
for (const t of topping) {
freq.set(t, (freq.get(t) || 0) + 1);
}
// 기존에 Map()에 담긴 것들은 하나씩 지워주고
// 반면에 Set()에는 하나씩 담겨주면서
// 공평하게 맞춘다.
for (const t of topping) {
freq.set(t, (freq.get(t)-1);
leftFreq.add(t);
// 만약에 원소의 값이 없으면 삭제
if (freq.get(t) === 0) {
freq.delete(t);
}
// 만약에 Map()함수의 사이즈와 Set()함수의 사이즈가 같으면 +1
if (freq.size === leftFreg.size) {
answer += 1;
}
}
return answer;
}
▶ 풀이 과정
1. 이 코드는 Map()함수와 Set()함수를 사용했다. 이유는 밑에서 더 설명하겠다.
2. 일단 입력값을 for of 반복문을 사용해서 Map에 set메서드를 사용해서 넣는다. 그 뒤에 get()메서드를 사용해서 Map()에 들어있는 t가 있는지를 확인하고 혹은 없을 경우 0을 사용한다. 즉 현재 개수를 반환하거나 없는 경우 0을 반환한다. 현재 개수 +1 또는 0 + 1의 값을Map()에 넣어주면 값과 값의 개수가 잘 들어간다.
3. 다시 for of 반복문을 사용하는데 여기서 왜 Map()함수와 Set()함수를 사용한지가 나온다. 이해를 돕기 위해 topping = [1, 2, 1, 3, 1, 4, 1, 2]를 돌려보겠다.
Map(4) { 1 => 3, 2 => 2, 3 => 1, 4 => 1 } Set(1) { 1 }
Map(4) { 1 => 3, 2 => 1, 3 => 1, 4 => 1 } Set(2) { 1, 2 }
Map(4) { 1 => 2, 2 => 1, 3 => 1, 4 => 1 } Set(2) { 1, 2 }
Map(4) { 1 => 2, 2 => 1, 3 => 0, 4 => 1 } Set(3) { 1, 2, 3 }
Map(3) { 1 => 1, 2 => 1, 4 => 1 } Set(3) { 1, 2, 3 }
Map(3) { 1 => 1, 2 => 1, 4 => 0 } Set(3) { 1, 2, 3, 4 }
Map(2) { 1 => 0, 2 => 1 } Set(4) { 1, 2, 3, 4 }
Map(1) { 2 => 0 } Set(4) { 1, 2, 3, 4 }
위의 코드를 보면 Map()함수는 반복문을 돌면서 점차 값의 개수가 사라지는 것을 볼 수 있고 Set()함수는 반대로 계속 넣어주고 있으므로 증가하고 있다. 쉽게 말해 Map()은 전체 배열에서 점차 원소를 지우는 방식, Set()은 중복은 제거하면서 원소를 늘려가는 방식을 사용했다. freq.get(i)-1는 해당 토핑의 개수를 1개 감소시키는 것이다.
4. 이제 get() 메서드를 사용해서 조건문에 만약에 토핑의 개수가 0이라면 delete() 메서드를 사용해서 삭제했다. 이유는 크게 두 가지이다. 첫 번째로는 공간 복잡도를 최적화하기 위해서다. 토핑 개수가 0인데 그걸 삭제 안 하고 냅두면 공간만 차지한다. 그래서 삭제했다.
그리고 조건 검사 간소화하기 위해서다. 개수가 0인 토핑의 항목이 계속 남아 있으면 정확한 비교를 할 수 없다. 그래서 삭제했다. 이 작업을 통해서 코드의 효율성이 상승한다.
5. 이제 마지막으로 Map()과 Set()의 size 메서드를 사용해서 크기가 같은 경우 +1을 해준다. 위의 경우 Map(3) Set(3)인 경우가 2번 존재하므로 2가 된다.
▶ 배운점
1. 항상 문제 제한사항을 잘 보고 문제에 맞는 최적의 자료구조를 활용하자.
2. 기존의 해결방식을 고수하지말고 탈피하자.
'Algorithm' 카테고리의 다른 글
[프로그래머스] Level2 - 124 나라의 숫자(Javascript) (0) | 2023.05.05 |
---|---|
[프로그래머스] Level2 - 삼각 달팽이(Javascript) (0) | 2023.05.04 |
[프로그래머스] Level2 - 다리를 지나는 트럭(Javascript) (0) | 2023.04.29 |
[프로그래머스] Level2 - 가장 큰 수(Javascript) (0) | 2023.04.28 |
[프로그래머스] Level2 - 2개 이하로 다른 비트(Javascript) (0) | 2023.04.27 |