π λ¬Έμ
νλ‘κ·Έλλ¨Έμ€ 2022 KAKAO TECH INTERNSHIP λ ν ν© κ°κ² λ§λ€κΈ°
ꡬνν΄μΌ νλ κ²μ
μ£Όμ΄μ§ λ κ°μ λ°°μ΄μ μλ μμλ€μ ν©μ΄ κ°μμΌ νλ€. κ° λ°°μ΄ μμμ μ΄ν©μ΄ κ°μ§ μμΌλ©΄, λ°°μ΄ κ° μμλ€μ μ΄λνμ¬ ν©μ μΌμΉμν¨λ€.
μ΄ λ, μ΄λ κ·μΉμ λ€μκ³Ό κ°λ€.
- λ³ΈμΈ λ°°μ΄μ μ΄ν©μ΄ ν¬λ€κ³ νλ¨λμ΄ μμλ₯Ό μ κ±°νκ³ μΆμ λλ λ³ΈμΈ λ°°μ΄μ 첫 λ²μ§Έ μμλΆν° μ κ±°ν΄μΌ νλ€.
- λ³ΈμΈ λ°°μ΄μ μ΄ν©μ΄ μλ€κ³ νλ¨λμ΄ μλ λ°°μ΄μ μμλ₯Ό μΆκ°νκ³ μΆμ λλ μλ λ°°μ΄μ 첫 λ²μ§Έ μμλ₯Ό μ κ±°νκ³ κ·Έ κ°μ λ³ΈμΈ λ°°μ΄μ λ§μ§λ§ μμλ‘ μ½μ νλ€.
λ¨, μ΄λ€ λ°©λ²μΌλ‘λ κ° λ°°μ΄μ μμ ν©μ κ°κ² λ§λ€ μ μλ κ²½μ°λ μ‘΄μ¬νλ€.
κ°λ¨νκ² μκ°νλ©΄ νλμ λ°°μ΄μ κΈ°μ€μΌλ‘ μλ λ°°μ΄μ shift
(λ°°μ΄μ 첫 λ²μ§Έ μμλ₯Ό μ κ±°νλ€.) μμλ₯Ό push
(λ°°μ΄μ λ§μ§λ§ μμλ‘ μ½μ
νλ€.)νκ³ μλ‘μ΄ ν©μ ꡬνκΈ° μν΄ reduce
(λ°°μ΄μ λ°λ³΅νλ©° μ¬μ©μ μ μ ν¨μμ λ°λΌ κ°μ λμ νλ€.)λ‘ ν©μ ꡬνλ©΄ λλ€. νμ§λ§ shift
μ reduce
λ μκ° λ³΅μ‘λκ° ν° ν¨μλ€μ΄λ€. λ°λΌμ μ΄ λ¬Έμ μμ μ¬μ©νλ©΄ μκ°μ΄κ³Όκ° λ°μνλ€.
νλμ λ°°μ΄λ‘ λ§λ ν, (μΈλ±μ€ λ³μλ‘ μμμ κ³Ό λμ μ μμ νλ©° ν΄λΉ μμμ ν¬ν¨λ μμλ€μ ν©)κ³Ό (κ·Έ μΈ μμλ€μ ν©)μ λΉκ΅νλ©΄ λλ€. κ° μμμ μ΄ν©μ΄ κ°μμ§κ±°λ λ°°μ΄μ λκΉμ§ λ°λ³΅ν λκΉμ§ μμμ λλ λμ μ μμ νλ©° μμλ³ ν©μ λΉκ΅νλ©° μ΅μ’ κ²°κ³Όκ°μΈ μμ νμλ₯Ό λμ νλ€.
1οΈβ£ νλΌλ―Έν°λ‘ μ λ¬λ λ λ°°μ΄μ νλλ‘ ν©μΉλ€.
ꡬ쑰 λΆν΄ ν λΉ κ΅¬λ¬Έμ μ¬μ©ν΄μ λ λ°°μ΄μ ν©μ³ μλ‘μ΄ λ°°μ΄ totalQueue
λ₯Ό μ μΈνλ€.
κ·Έλ¦¬κ³ totalQueue
μμλ€μ ν©μ μ λ° κ°μ ꡬν΄μΌνλ€. λ κ°μ λ°°μ΄ κ°μμ μ΄ν©μ΄ κ°μμΌ νλ―λ‘ μμμ κ³Ό λμ μ μ΄μ©νμ¬ μ§μ ν μμ λ΄ μμλ€μ ν©μ΄ μ΄ν© / 2
μ΄ λλ μμμ μ°Ύμ κ²μ΄κΈ° λλ¬Έμ΄λ€.
λ κ°μ λ°°μ΄ ν©μ κ°μ κ°μ κ°μ ΈμΌνκΈ° λλ¬Έμ μ΄ν© / 2
μ κ°μ΄ νμλΌλ©΄ μ΄λ€ λ°©λ²μΌλ‘λ κ°μμ ν©μ κ°κ² λ§λ€ μ μμΌλ―λ‘ μ’
λ£νλ€.
1
2
3
4
5
6
const solution = (queue1, queue2) => {
const totalQueue = [...queue1, ...queue2];
const halfOfSum = totalQueue.reduce((acc, cur) => acc + cur, 0) / 2;
if (halfOfSum % 1 !== 0) return -1;
};
2οΈβ£ μμμ κ³Ό λμ μ μ΄κΈ°ννκ³ λ°°μ΄μ μννλ©° μμλ€μ ν©μ΄ βμ΄ν© / 2βμ κ°μΈ μμμ μ°Ύλλ€.
μμμ start
λ λ°°μ΄μ μμ μΈλ±μ€μΈ 0μΌλ‘ μ΄κΈ°ννλ€. λμ end
λ νλΌλ―Έν°λ‘ μ λ¬λ°μλ νλ€μ κΈΈμ΄λ‘ μ΄κΈ°ννλ€. μ λ¬λ°μ λΉμμ 2κ°μ νλ κΈΈμ΄κ° κ°κΈ° λλ¬Έμ μ΄λ ν μͺ½μ κ°μ ν λΉν΄λ λμΌνλ€.
κ·Έλ¬λ©΄ μ²μ ν©μ ꡬν μμμ ν©μ ꡬνκ³ μ΄ κ°μ λ°λΌ μμμ κΈ°μ€μ λ€μ μμ ν΄μΌ νλ€.
start
~end
μμμ ν©μ΄μ΄ν© / 2
κ° κ°λ€λ©΄ νμͺ½ μμμ ν©μ΄ κ°μμ§κΈ° μν 쑰건μ λ§μ‘±μν€λ―λ‘start
~end
μμ μ΄ μΈμ λλ¨Έμ§ μμλ€μ ν©μ ꡬν΄μΌ νλ€.- λλ¨Έμ§ μμλ€μ ν©μ΄
start
~end
μμμ ν©κ³Ό κ°λ€λ©΄ μμ νμλ₯Ό 리ν΄νλ€. - λλ¨Έμ§ μμλ€μ ν©μ΄
start
~end
μμμ ν©κ³Ό κ°μ§ μλ€λ©΄ κ° λ°°μ΄μ ν©μ κ°κ² λ§λ€ μ μμμ μλ―Ένλ€. κ·Έλ¬λ―λ‘ -1μ 리ν΄νλ€.
- λλ¨Έμ§ μμλ€μ ν©μ΄
start
~end
μμμ ν©μ΄μ΄ν© / 2
λ³΄λ€ ν¬λ©΄ κ°μ μ€μ¬μΌ νλ€. κ·Έλ¬λ―λ‘start
λ₯Ό 1λ§νΌ μ¦κ°μν¨λ€. μ΄λ μ΄λ κ·μΉ μ€ μμλ₯Ό κΊΌλΌ λμλ λ³ΈμΈ λ°°μ΄μ 첫 λ²μ§Έ μμλ₯Ό μ νν΄μΌ νλ€λ κ²μ λ§μ‘±νλ€.start
~end
μμμ ν©μ΄μ΄ν© / 2
λ³΄λ€ μμΌλ©΄ κ°μ μΆκ°ν΄μΌ νλ€. κ·Έλ¬λ―λ‘end
λ₯Ό 1λ§νΌ μ¦κ°μν¨λ€. μ΄λ μ΄λ κ·μΉ μ€ μμλ₯Ό μΆκ°ν λμλ μλ λ°°μ΄μ 첫 λ²μ§Έ μμλ₯Ό μ νν΄μΌ λ³ΈμΈ λ°°μ΄μ λ§μ§λ§ μμλ‘ μ½μ νλ€λ κ²μ λ§μ‘±νλ€.
λ¬Έμ μ€λͺ μμ μ£Όμ΄μ§ μμλ‘ λ€μ μ 리ν΄λ³΄μ.
queue1
= [3,2,7,2], queue2
= [4,6,5,1]λ‘ κΈΈμ΄κ° 4μΈ λ κ°μ νκ° μ£Όμ΄μ§λ€. λ°λΌμ start
λ 0μΌλ‘, end
λ 4λ‘ μ΄κΈ°ννλ€.
κ·Έλ¦¬κ³ λ κ°μ νλ₯Ό ν©νμ¬ [3,2,7,2,4,6,5,1]λΌλ μλ‘μ΄ λ°°μ΄μ μμ±νλ€. λ°°μ΄μ μ΄ν©μ 30μ΄λ©° κ·Έμ μ λ° κ°μ 15μ΄λ€. μ¦, μμμ ν©μ΄ 15κ° λλ ꡬκ°μ μ°ΎμμΌ νλ€.
start
μ end
μ λ°λΌ μ²μ ν©μ ꡬν μμμ [3,2,7,2]λ€. ν©μ 14λ‘ μ λ° κ°λ³΄λ€ μλ€. κ·Έλ¬λ―λ‘ μμμ λνμΌ νλ€. κ·μΉμ λ°λΌ λμ μμ μ€λ₯Έμͺ½μΌλ‘ 1λ§νΌ μ΄λνλ€.
μ΄μ start
λ 0, end
λ 5μ΄λ€.
end
κ° 4μμλtotalQueue[3]
κΉμ§λ§ μμμ μ§μ νλ μ΄μλ°°μ΄μ μΌλΆλΆλ§ κ°μ Έμ€κΈ° μν΄
slice
ν¨μλ₯Ό μ¬μ©νλ€.slice
λ μμ μΈλ±μ€λΆν° μ’ λ£ μΈλ±μ€ μ κΉμ§λ§ λ°ννκΈ° λλ¬Έμ΄λ€. (substring
κ³Ό λμΌνλ€κ³ μκ°νμ.)μ¦, λ°°μ΄μ
slice
ν¨μμ μμμ κ³Ό λμ μ κΈ°μ€μΌλ‘start
μend
λ₯Ό μ€μ νμλ€λ κ²μ λͺ μ¬νμ.
ν©μ ꡬν μμμ ν μΉΈ λμ΄μ [3,2,7,2,4]λ€. ν©μ 18λ‘ μ λ° κ°λ³΄λ€ ν¬λ€. κ·Έλ¬λ―λ‘ μμμ μ€μ¬μΌ νλ€. κ·μΉμ λ°λΌ μμμ μμ μΌμͺ½μΌλ‘ 1λ§νΌ μ΄λνλ€.
μ΄μ start
λ 1, end
λ 5μ΄λ€.
ν©μ ꡬν μμμ ν μΉΈ μ€μ΄λ€μ΄ [2,7,2,4]λ€. ν©μ 15λ‘ μ λ° κ°λ³΄λ€ μ νν μΌμΉνλ€! μ΄μ ν΄λΉ μμμ΄ μλ λλ¨Έμ§ μμλ€μ ν©μ νμΈν΄μΌ νλ€.
κ° νμ ν©μ΄ κ°μμ§λ ꡬκ°μ [2,7,2,4], [3,6,5,1]μ΄λ€.
λ λ²μ§Έ μμ λ queue1
= [1,2,1,2], queue2
= [1,10,1,2]λ‘ μ£Όμ΄μ§λ€. μμ κ³Όμ μ κ±°μΉλ©° μ΅μ’
μ μΌλ‘ μλμ κ°μ΄ μμμ΄ λΆλ¦¬λλ€.
πΉ μ½λ
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
32
const solution = (queue1, queue2) => {
const totalQueue = [...queue1, ...queue2];
const halfOfSum = totalQueue.reduce((acc, cur) => acc + cur, 0) / 2;
if (halfOfSum % 1 !== 0) return -1;
let start = 0,
end = queue1.length;
let result = 0;
let sum = totalQueue.slice(start, end).reduce((acc, cur) => acc + cur, 0);
while (end <= totalQueue.length) {
if (sum < halfOfSum) {
sum += totalQueue[end++];
result++;
} else if (sum > halfOfSum) {
sum -= totalQueue[start++];
result++;
} else {
const a = totalQueue
.splice(start, end - start)
.reduce((acc, cur) => acc + cur, 0);
const b = totalQueue.reduce((acc, cur) => acc + cur, 0);
if (a === b) return result;
else return -1;
break;
}
}
return -1;
};