πHi there!π
cykim43 / algorhythm Goto Github PK
View Code? Open in Web Editor NEWFeel My Rhythmπ΅
Feel My Rhythmπ΅
λͺ ν¨ μ§κ°μ λ§λλ νμ¬μμ μ§κ°μ ν¬κΈ°λ₯Ό μ νλ €κ³ ν©λλ€. λ€μν λͺ¨μκ³Ό ν¬κΈ°μ λͺ ν¨λ€μ λͺ¨λ μλ©ν μ μμΌλ©΄μ, μμμ λ€κ³ λ€λκΈ° νΈν μ§κ°μ λ§λ€μ΄μΌ ν©λλ€. μ΄λ¬ν μ건μ λ§μ‘±νλ μ§κ°μ λ§λ€κΈ° μν΄ λμμΈνμ λͺ¨λ λͺ ν¨μ κ°λ‘ κΈΈμ΄μ μΈλ‘ κΈΈμ΄λ₯Ό μ‘°μ¬νμ΅λλ€.
μλ νλ 4κ°μ§ λͺ ν¨μ κ°λ‘ κΈΈμ΄μ μΈλ‘ κΈΈμ΄λ₯Ό λνλ λλ€.
λͺ ν¨ λ²νΈ | κ°λ‘ κΈΈμ΄ | μΈλ‘ κΈΈμ΄ |
---|---|---|
1 | 60 | 50 |
2 | 30 | 70 |
3 | 60 | 30 |
4 | 80 | 40 |
κ°μ₯ κΈ΄ κ°λ‘ κΈΈμ΄μ μΈλ‘ κΈΈμ΄κ° κ°κ° 80, 70μ΄κΈ° λλ¬Έμ 80(κ°λ‘) x 70(μΈλ‘) ν¬κΈ°μ μ§κ°μ λ§λ€λ©΄ λͺ¨λ λͺ ν¨λ€μ μλ©ν μ μμ΅λλ€. νμ§λ§ 2λ² λͺ ν¨μ κ°λ‘λ‘ λν μλ©νλ€λ©΄ 80(κ°λ‘) x 50(μΈλ‘) ν¬κΈ°μ μ§κ°μΌλ‘ λͺ¨λ λͺ ν¨λ€μ μλ©ν μ μμ΅λλ€. μ΄λμ μ§κ° ν¬κΈ°λ 4000(=80 x 50)μ λλ€.
λͺ¨λ λͺ ν¨μ κ°λ‘ κΈΈμ΄μ μΈλ‘ κΈΈμ΄λ₯Ό λνλ΄λ 2μ°¨μ λ°°μ΄ sizesκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§λλ€. λͺ¨λ λͺ ν¨μ μλ©ν μ μλ κ°μ₯ μμ μ§κ°μ λ§λ€ λ, μ§κ°μ ν¬κΈ°λ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
sizes | result |
---|---|
[[60, 50], [30, 70], [60, 30], [80, 40]] | 4000 |
[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] | 120 |
[[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] | 133 |
μ
μΆλ ₯ μ #1
λ¬Έμ μμμ κ°μ΅λλ€.
μ
μΆλ ₯ μ #2
λͺ
ν¨λ€μ μ μ ν νμ μμΌ κ²Ήμ³€μ λ, 3λ²μ§Έ λͺ
ν¨(κ°λ‘: 8, μΈλ‘: 15)μ΄ λ€λ₯Έ λͺ¨λ λͺ
ν¨λ³΄λ€ ν¬κΈ°κ° ν½λλ€. λ°λΌμ μ§κ°μ ν¬κΈ°λ 3λ²μ§Έ λͺ
ν¨μ ν¬κΈ°μ κ°μΌλ©°, 120(=8 x 15)μ return ν©λλ€.
μ
μΆλ ₯ μ #3
λͺ
ν¨λ€μ μ μ ν νμ μμΌ κ²Ήμ³€μ λ, λͺ¨λ λͺ
ν¨μ ν¬ν¨νλ κ°μ₯ μμ μ§κ°μ ν¬κΈ°λ 133(=19 x 7)μ
λλ€.
μ΄ λ¨μλ‘ κΈ°λ‘λ μ£Όμκ°κ²©μ΄ λ΄κΈ΄ λ°°μ΄ pricesκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, κ°κ²©μ΄ λ¨μ΄μ§μ§ μμ κΈ°κ°μ λͺ μ΄μΈμ§λ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±νμΈμ.
prices | return |
---|---|
[1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
κ΄νΈκ° λ°λ₯΄κ² μ§μ§μ΄μ‘λ€λ κ²μ '(' λ¬Έμλ‘ μ΄λ ΈμΌλ©΄ λ°λμ μ§μ§μ΄μ ')' λ¬Έμλ‘ λ«νμΌ νλ€λ λ»μ λλ€. μλ₯Ό λ€μ΄
'(' λλ ')' λ‘λ§ μ΄λ£¨μ΄μ§ λ¬Έμμ΄ sκ° μ£Όμ΄μ‘μ λ, λ¬Έμμ΄ sκ° μ¬λ°λ₯Έ κ΄νΈμ΄λ©΄ trueλ₯Ό return νκ³ , μ¬λ°λ₯΄μ§ μμ κ΄νΈμ΄λ©΄ falseλ₯Ό return νλ solution ν¨μλ₯Ό μμ±ν΄ μ£ΌμΈμ.
s | answer |
---|---|
"()()" | true |
"(())()" | true |
")()(" | false |
"(()(" | false |
μ
μΆλ ₯ μ #1,2,3,4
λ¬Έμ μ μμμ κ°μ΅λλ€.
H-Indexλ κ³Όνμμ μμ°μ±κ³Ό μν₯λ ₯μ λνλ΄λ μ§νμ λλ€. μ΄λ κ³Όνμμ H-Indexλ₯Ό λνλ΄λ κ°μΈ hλ₯Ό ꡬνλ €κ³ ν©λλ€. μν€λ°±κ³Ό1μ λ°λ₯΄λ©΄, H-Indexλ λ€μκ³Ό κ°μ΄ ꡬν©λλ€.
μ΄λ€ κ³Όνμκ° λ°νν λ Όλ¬Έ nνΈ μ€, hλ² μ΄μ μΈμ©λ λ Όλ¬Έμ΄ hνΈ μ΄μμ΄κ³ λλ¨Έμ§ λ Όλ¬Έμ΄ hλ² μ΄ν μΈμ©λμλ€λ©΄ hμ μ΅λκ°μ΄ μ΄ κ³Όνμμ H-Indexμ λλ€.
μ΄λ€ κ³Όνμκ° λ°νν λ Όλ¬Έμ μΈμ© νμλ₯Ό λ΄μ λ°°μ΄ citationsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ΄ κ³Όνμμ H-Indexλ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
citations | return |
---|---|
[3, 0, 6, 1, 5] | 3 |
μ΄ κ³Όνμκ° λ°νν λ Όλ¬Έμ μλ 5νΈμ΄κ³ , κ·Έμ€ 3νΈμ λ Όλ¬Έμ 3ν μ΄μ μΈμ©λμμ΅λλ€. κ·Έλ¦¬κ³ λλ¨Έμ§ 2νΈμ λ Όλ¬Έμ 3ν μ΄ν μΈμ©λμκΈ° λλ¬Έμ μ΄ κ³Όνμμ H-Indexλ 3μ λλ€.
λ°°μ΄ arrayμ iλ²μ§Έ μ«μλΆν° jλ²μ§Έ μ«μκΉμ§ μλ₯΄κ³ μ λ ¬νμ λ, kλ²μ§Έμ μλ μλ₯Ό ꡬνλ € ν©λλ€.
μλ₯Ό λ€μ΄ arrayκ° [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3μ΄λΌλ©΄
λ°°μ΄ array, [i, j, k]λ₯Ό μμλ‘ κ°μ§ 2μ°¨μ λ°°μ΄ commandsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, commandsμ λͺ¨λ μμμ λν΄ μμ μ€λͺ ν μ°μ°μ μ μ©νμ λ λμ¨ κ²°κ³Όλ₯Ό λ°°μ΄μ λ΄μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
array | commands | return |
---|---|---|
[1, 5, 2, 6, 3, 7, 4] | [[2, 5, 3], [4, 4, 1], [1, 7, 3]] | [5, 6, 3] |
[1, 5, 2, 6, 3, 7, 4]λ₯Ό 2λ²μ§ΈλΆν° 5λ²μ§ΈκΉμ§ μλ₯Έ ν μ λ ¬ν©λλ€. [2, 3, 5, 6]μ μΈ λ²μ§Έ μ«μλ 5μ
λλ€.
[1, 5, 2, 6, 3, 7, 4]λ₯Ό 4λ²μ§ΈλΆν° 4λ²μ§ΈκΉμ§ μλ₯Έ ν μ λ ¬ν©λλ€. [6]μ 첫 λ²μ§Έ μ«μλ 6μ
λλ€.
[1, 5, 2, 6, 3, 7, 4]λ₯Ό 1λ²μ§ΈλΆν° 7λ²μ§ΈκΉμ§ μλ¦
λλ€. [1, 2, 3, 4, 5, 6, 7]μ μΈ λ²μ§Έ μ«μλ 3μ
λλ€.
ROR κ²μμ λ νμΌλ‘ λλμ΄μ μ§ννλ©°, μλ ν μ§μμ λ¨Όμ νκ΄΄νλ©΄ μ΄κΈ°λ κ²μμ λλ€. λ°λΌμ, κ° νμ μλ ν μ§μμ μ΅λν 빨리 λμ°©νλ κ²μ΄ μ 리ν©λλ€.
μ§κΈλΆν° λΉμ μ ν νμ νμμ΄ λμ΄ κ²μμ μ§ννλ €κ³ ν©λλ€. λ€μμ 5 x 5 ν¬κΈ°μ 맡μ, λΉμ μ μΊλ¦ν°κ° (ν: 1, μ΄: 1) μμΉμ μκ³ , μλ ν μ§μμ (ν: 5, μ΄: 5) μμΉμ μλ κ²½μ°μ μμμ λλ€.
μ κ·Έλ¦Όμμ κ²μμ λΆλΆμ λ²½μΌλ‘ λ§νμμ΄ κ° μ μλ κΈΈμ΄λ©°, ν°μ λΆλΆμ κ° μ μλ κΈΈμ
λλ€. μΊλ¦ν°κ° μμ§μΌ λλ λ, μ, λ¨, λΆ λ°©ν₯μΌλ‘ ν μΉΈμ© μ΄λνλ©°, κ²μ 맡μ λ²μ΄λ κΈΈμ κ° μ μμ΅λλ€.
μλ μμλ μΊλ¦ν°κ° μλ ν μ§μμΌλ‘ κ°λ λ κ°μ§ λ°©λ²μ λνλ΄κ³ μμ΅λλ€.
첫 λ²μ§Έ λ°©λ²μ 11κ°μ μΉΈμ μ§λμ μλ ν μ§μμ λμ°©νμ΅λλ€.
λ λ²μ§Έ λ°©λ²μ 15κ°μ μΉΈμ μ§λμ μλν μ§μμ λμ°©νμ΅λλ€.
μ μμμμλ 첫 λ²μ§Έ λ°©λ²λ³΄λ€ λ λΉ λ₯΄κ² μλν μ§μμ λμ°©νλ λ°©λ²μ μμΌλ―λ‘, μ΄ λ°©λ²μ΄ μλ ν μ§μμΌλ‘ κ°λ κ°μ₯ λΉ λ₯Έ λ°©λ²μ λλ€.
λ§μ½, μλ νμ΄ μμ μ ν μ§μ μ£Όμμ λ²½μ μΈμλμλ€λ©΄ μλ ν μ§μμ λμ°©νμ§ λͺ»ν μλ μμ΅λλ€. μλ₯Ό λ€μ΄, λ€μκ³Ό κ°μ κ²½μ°μ λΉμ μ μΊλ¦ν°λ μλ ν μ§μμ λμ°©ν μ μμ΅λλ€.
κ²μ 맡μ μν mapsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μΊλ¦ν°κ° μλ ν μ§μμ λμ°©νκΈ° μν΄μ μ§λκ°μΌ νλ μΉΈμ κ°μμ μ΅μκ°μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ. λ¨, μλ ν μ§μμ λμ°©ν μ μμ λλ -1μ return ν΄μ£ΌμΈμ.
maps | answer |
---|---|
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] | 11 |
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] | -1 |
μμ #1, 2
λ¬Έμ μ μμμ κ°μ΅λλ€.
μν¬μλ μνμ ν¬κΈ°ν μ¬λμ μ€λ§μ λλ€. μν¬μ μΌμΈλ°©μ λͺ¨μκ³ μ¬μ μν λ¬Έμ λ₯Ό μ λΆ μ°μΌλ € ν©λλ€. μν¬μλ 1λ² λ¬Έμ λΆν° λ§μ§λ§ λ¬Έμ κΉμ§ λ€μκ³Ό κ°μ΄ μ°μ΅λλ€.
1λ² μν¬μκ° μ°λ λ°©μ: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2λ² μν¬μκ° μ°λ λ°©μ: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3λ² μν¬μκ° μ°λ λ°©μ: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...
1λ² λ¬Έμ λΆν° λ§μ§λ§ λ¬Έμ κΉμ§μ μ λ΅μ΄ μμλλ‘ λ€μ λ°°μ΄ answersκ° μ£Όμ΄μ‘μ λ, κ°μ₯ λ§μ λ¬Έμ λ₯Ό λ§ν μ¬λμ΄ λꡬμΈμ§ λ°°μ΄μ λ΄μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
answers | return |
---|---|
[1,2,3,4,5] | [1] |
[1,3,2,4,2] | [1,2,3] |
μ μΆλ ₯ μ #1
λ°λΌμ κ°μ₯ λ¬Έμ λ₯Ό λ§μ΄ λ§ν μ¬λμ μν¬μ 1μ λλ€.
μ μΆλ ₯ μ #2
λͺ¨λ μ¬λμ΄ 2λ¬Έμ μ©μ λ§μ·μ΅λλ€.
nκ°μ μμ΄ μλ μ μλ€μ΄ μμ΅λλ€. μ΄ μ μλ€μ μμλ₯Ό λ°κΎΈμ§ μκ³ μ μ ν λνκ±°λ λΉΌμ νκ² λλ²λ₯Ό λ§λ€λ €κ³ ν©λλ€. μλ₯Ό λ€μ΄ [1, 1, 1, 1, 1]λ‘ μ«μ 3μ λ§λ€λ €λ©΄ λ€μ λ€μ― λ°©λ²μ μΈ μ μμ΅λλ€.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
μ¬μ©ν μ μλ μ«μκ° λ΄κΈ΄ λ°°μ΄ numbers, νκ² λλ² targetμ΄ λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ μ«μλ₯Ό μ μ ν λνκ³ λΉΌμ νκ² λλ²λ₯Ό λ§λλ λ°©λ²μ μλ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
numbers | target | return |
---|---|---|
[1, 1, 1, 1, 1] | 3 | 5 |
[4, 1, 2, 1] | 4 | 2 |
μ μΆλ ₯ μ #1
λ¬Έμ μμμ κ°μ΅λλ€.
μ μΆλ ₯ μ #2
+4+1-2+1 = 4
+4-1+2-1 = 4
μ΄ 2κ°μ§ λ°©λ²μ΄ μμΌλ―λ‘, 2λ₯Ό return ν©λλ€.
μΈνμνμλ ATMμ΄ 1λλ°μ μλ€. μ§κΈ μ΄ ATMμμ Nλͺ μ μ¬λλ€μ΄ μ€μ μμλ€. μ¬λμ 1λ²λΆν° Nλ²κΉμ§ λ²νΈκ° λ§€κ²¨μ Έ μμΌλ©°, iλ² μ¬λμ΄ λμ μΈμΆνλλ° κ±Έλ¦¬λ μκ°μ PiλΆμ΄λ€.
μ¬λλ€μ΄ μ€μ μλ μμμ λ°λΌμ, λμ μΈμΆνλλ° νμν μκ°μ ν©μ΄ λ¬λΌμ§κ² λλ€. μλ₯Ό λ€μ΄, μ΄ 5λͺ μ΄ μκ³ , P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 μΈ κ²½μ°λ₯Ό μκ°ν΄λ³΄μ. [1, 2, 3, 4, 5] μμλ‘ μ€μ μ λ€λ©΄, 1λ² μ¬λμ 3λΆλ§μ λμ λ½μ μ μλ€. 2λ² μ¬λμ 1λ² μ¬λμ΄ λμ λ½μ λ κΉμ§ κΈ°λ€λ €μΌ νκΈ° λλ¬Έμ, 3+1 = 4λΆμ΄ κ±Έλ¦¬κ² λλ€. 3λ² μ¬λμ 1λ², 2λ² μ¬λμ΄ λμ λ½μ λκΉμ§ κΈ°λ€λ €μΌ νκΈ° λλ¬Έμ, μ΄ 3+1+4 = 8λΆμ΄ νμνκ² λλ€. 4λ² μ¬λμ 3+1+4+3 = 11λΆ, 5λ² μ¬λμ 3+1+4+3+2 = 13λΆμ΄ κ±Έλ¦¬κ² λλ€. μ΄ κ²½μ°μ κ° μ¬λμ΄ λμ μΈμΆνλλ° νμν μκ°μ ν©μ 3+4+8+11+13 = 39λΆμ΄ λλ€.
μ€μ [2, 5, 1, 4, 3] μμλ‘ μ€μ μλ©΄, 2λ² μ¬λμ 1λΆλ§μ, 5λ² μ¬λμ 1+2 = 3λΆ, 1λ² μ¬λμ 1+2+3 = 6λΆ, 4λ² μ¬λμ 1+2+3+3 = 9λΆ, 3λ² μ¬λμ 1+2+3+3+4 = 13λΆμ΄ κ±Έλ¦¬κ² λλ€. κ° μ¬λμ΄ λμ μΈμΆνλλ° νμν μκ°μ ν©μ 1+3+6+9+13 = 32λΆμ΄λ€. μ΄ λ°©λ²λ³΄λ€ λ νμν μκ°μ ν©μ μ΅μλ‘ λ§λ€ μλ μλ€.
μ€μ μ μλ μ¬λμ μ Nκ³Ό κ° μ¬λμ΄ λμ μΈμΆνλλ° κ±Έλ¦¬λ μκ° Piκ° μ£Όμ΄μ‘μ λ, κ° μ¬λμ΄ λμ μΈμΆνλλ° νμν μκ°μ ν©μ μ΅μκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
첫째 μ€μ μ¬λμ μ N(1 β€ N β€ 1,000)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€μλ κ° μ¬λμ΄ λμ μΈμΆνλλ° κ±Έλ¦¬λ μκ° Piκ° μ£Όμ΄μ§λ€. (1 β€ Pi β€ 1,000)
첫째 μ€μ κ° μ¬λμ΄ λμ μΈμΆνλλ° νμν μκ°μ ν©μ μ΅μκ°μ μΆλ ₯νλ€.
5
3 1 4 3 2
32
XXκ²μμλ νΌλ‘λ μμ€ν (0 μ΄μμ μ μλ‘ ννν©λλ€)μ΄ μμΌλ©°, μΌμ νΌλ‘λλ₯Ό μ¬μ©ν΄μ λμ μ ννν μ μμ΅λλ€. μ΄λ, κ° λμ λ§λ€ ννμ μμνκΈ° μν΄ νμν "μ΅μ νμ νΌλ‘λ"μ λμ ννμ λ§μ³€μ λ μλͺ¨λλ "μλͺ¨ νΌλ‘λ"κ° μμ΅λλ€. "μ΅μ νμ νΌλ‘λ"λ ν΄λΉ λμ μ νννκΈ° μν΄ κ°μ§κ³ μμ΄μΌ νλ μ΅μνμ νΌλ‘λλ₯Ό λνλ΄λ©°, "μλͺ¨ νΌλ‘λ"λ λμ μ ννν ν μλͺ¨λλ νΌλ‘λλ₯Ό λνλ λλ€. μλ₯Ό λ€μ΄ "μ΅μ νμ νΌλ‘λ"κ° 80, "μλͺ¨ νΌλ‘λ"κ° 20μΈ λμ μ νννκΈ° μν΄μλ μ μ μ νμ¬ λ¨μ νΌλ‘λλ 80 μ΄μ μ΄μ΄μΌ νλ©°, λμ μ ννν νμλ νΌλ‘λ 20μ΄ μλͺ¨λ©λλ€.
μ΄ κ²μμλ ν루μ ν λ²μ© ννν μ μλ λμ μ΄ μ¬λ¬κ° μλλ°, ν μ μ κ° μ€λ μ΄ λμ λ€μ μ΅λν λ§μ΄ νννλ € ν©λλ€. μ μ μ νμ¬ νΌλ‘λ kμ κ° λμ λ³ "μ΅μ νμ νΌλ‘λ", "μλͺ¨ νΌλ‘λ"κ° λ΄κΈ΄ 2μ°¨μ λ°°μ΄ dungeons κ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ μ κ° ννν μ μλ μ΅λ λμ μλ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
k | dungeons | result |
---|---|---|
80 | [[80,20],[50,40],[30,10]] | 3 |
νμ¬ νΌλ‘λλ 80μ λλ€.
λ§μ½, 첫 λ²μ§Έ β λ λ²μ§Έ β μΈ λ²μ§Έ λμ μμλ‘ νννλ€λ©΄
λ§μ½, 첫 λ²μ§Έ β μΈ λ²μ§Έ β λ λ²μ§Έ λμ μμλ‘ νννλ€λ©΄
λ°λΌμ μ΄ κ²½μ° μΈ λμ μ λͺ¨λ ννν μ μμΌλ©°, μ μ κ° ννν μ μλ μ΅λ λμ μλ 3μ λλ€.
NΓNκ°μ μκ° NΓN ν¬κΈ°μ νμ μ±μμ Έ μλ€. (x1, y1)λΆν° (x2, y2)κΉμ§ ν©μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. (x, y)λ xν yμ΄μ μλ―Ένλ€.
μλ₯Ό λ€μ΄, N = 4μ΄κ³ , νκ° μλμ κ°μ΄ μ±μμ Έ μλ κ²½μ°λ₯Ό μ΄ν΄λ³΄μ.
1 | 2 | 3 | 4 |
---|---|---|---|
2 | 3 | 4 | 5 |
3 | 4 | 5 | 6 |
4 | 5 | 6 | 7 |
μ¬κΈ°μ (2, 2)λΆν° (3, 4)κΉμ§ ν©μ ꡬνλ©΄ 3+4+5+4+5+6 = 27μ΄κ³ , (4, 4)λΆν° (4, 4)κΉμ§ ν©μ ꡬνλ©΄ 7μ΄λ€.
νμ μ±μμ Έ μλ μμ ν©μ ꡬνλ μ°μ°μ΄ μ£Όμ΄μ‘μ λ, μ΄λ₯Ό μ²λ¦¬νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
첫째 μ€μ νμ ν¬κΈ° Nκ³Ό ν©μ ꡬν΄μΌ νλ νμ Mμ΄ μ£Όμ΄μ§λ€. (1 β€ N β€ 1024, 1 β€ M β€ 100,000) λμ§Έ μ€λΆν° Nκ°μ μ€μλ νμ μ±μμ Έ μλ μκ° 1νλΆν° μ°¨λ‘λλ‘ μ£Όμ΄μ§λ€. λ€μ Mκ°μ μ€μλ λ€ κ°μ μ μ x1, y1, x2, y2 κ° μ£Όμ΄μ§λ©°, (x1, y1)λΆν° (x2, y2)μ ν©μ κ΅¬ν΄ μΆλ ₯ν΄μΌ νλ€. νμ μ±μμ Έ μλ μλ 1,000λ³΄λ€ μκ±°λ κ°μ μμ°μμ΄λ€. (x1 β€ x2, y1 β€ y2)
μ΄ Mμ€μ κ±Έμ³ (x1, y1)λΆν° (x2, y2)κΉμ§ ν©μ κ΅¬ν΄ μΆλ ₯νλ€.
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4
27
6
64
λΉμ μ ν°μΌλͺ¬μ μ‘κΈ° μν μ€λ μ¬ν λμ, ν λ°μ¬λμ μ°κ΅¬μ€μ λμ°©νμ΅λλ€. ν λ°μ¬λμ λΉμ μκ² μμ μ μ°κ΅¬μ€μ μλ μ΄ N λ§λ¦¬μ ν°μΌλͺ¬ μ€μμ N/2λ§λ¦¬λ₯Ό κ°μ Έκ°λ μ’λ€κ³ νμ΅λλ€.
ν λ°μ¬λ μ°κ΅¬μ€μ ν°μΌλͺ¬μ μ’
λ₯μ λ°λΌ λ²νΈλ₯Ό λΆμ¬ ꡬλΆν©λλ€. λ°λΌμ κ°μ μ’
λ₯μ ν°μΌλͺ¬μ κ°μ λ²νΈλ₯Ό κ°μ§κ³ μμ΅λλ€. μλ₯Ό λ€μ΄ μ°κ΅¬μ€μ μ΄ 4λ§λ¦¬μ ν°μΌλͺ¬μ΄ μκ³ , κ° ν°μΌλͺ¬μ μ’
λ₯ λ²νΈκ° [3λ², 1λ², 2λ², 3λ²]μ΄λΌλ©΄ μ΄λ 3λ² ν°μΌλͺ¬ λ λ§λ¦¬, 1λ² ν°μΌλͺ¬ ν λ§λ¦¬, 2λ² ν°μΌλͺ¬ ν λ§λ¦¬κ° μμμ λνλ
λλ€. μ΄λ, 4λ§λ¦¬μ ν°μΌλͺ¬ μ€ 2λ§λ¦¬λ₯Ό κ³ λ₯΄λ λ°©λ²μ λ€μκ³Ό κ°μ΄ 6κ°μ§κ° μμ΅λλ€.
μ΄λ, 첫 λ²μ§Έ(3λ²) ν°μΌλͺ¬κ³Ό λ€ λ²μ§Έ(3λ²) ν°μΌλͺ¬μ μ ννλ λ°©λ²μ ν μ’
λ₯(3λ² ν°μΌλͺ¬ λ λ§λ¦¬)μ ν°μΌλͺ¬λ§ κ°μ§ μ μμ§λ§, λ€λ₯Έ λ°©λ²λ€μ λͺ¨λ λ μ’
λ₯μ ν°μΌλͺ¬μ κ°μ§ μ μμ΅λλ€. λ°λΌμ μ μμμμ κ°μ§ μ μλ ν°μΌλͺ¬ μ’
λ₯ μμ μ΅λκ°μ 2κ° λ©λλ€.
λΉμ μ μ΅λν λ€μν μ’
λ₯μ ν°μΌλͺ¬μ κ°μ§κΈΈ μνκΈ° λλ¬Έμ, μ΅λν λ§μ μ’
λ₯μ ν°μΌλͺ¬μ ν¬ν¨ν΄μ N/2λ§λ¦¬λ₯Ό μ ννλ € ν©λλ€. Nλ§λ¦¬ ν°μΌλͺ¬μ μ’
λ₯ λ²νΈκ° λ΄κΈ΄ λ°°μ΄ numsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, N/2λ§λ¦¬μ ν°μΌλͺ¬μ μ ννλ λ°©λ² μ€, κ°μ₯ λ§μ μ’
λ₯μ ν°μΌλͺ¬μ μ ννλ λ°©λ²μ μ°Ύμ, κ·Έλμ ν°μΌλͺ¬ μ’
λ₯ λ²νΈμ κ°μλ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
nums | result |
---|---|
[3,1,2,3] | 2 |
[3,3,3,2,2,4] | 3 |
[3,3,3,2,2,2] | 2 |
μ
μΆλ ₯ μ #1
λ¬Έμ μ μμμ κ°μ΅λλ€.
μ
μΆλ ₯ μ #2
6λ§λ¦¬μ ν°μΌλͺ¬μ΄ μμΌλ―λ‘, 3λ§λ¦¬μ ν°μΌλͺ¬μ 골λΌμΌ ν©λλ€.
κ°μ₯ λ§μ μ’
λ₯μ ν°μΌλͺ¬μ κ³ λ₯΄κΈ° μν΄μλ 3λ² ν°μΌλͺ¬ ν λ§λ¦¬, 2λ² ν°μΌλͺ¬ ν λ§λ¦¬, 4λ² ν°μΌλͺ¬ ν λ§λ¦¬λ₯Ό κ³ λ₯΄λ©΄ λλ©°, λ°λΌμ 3μ return ν©λλ€.
μ
μΆλ ₯ μ #3
6λ§λ¦¬μ ν°μΌλͺ¬μ΄ μμΌλ―λ‘, 3λ§λ¦¬μ ν°μΌλͺ¬μ 골λΌμΌ ν©λλ€.
κ°μ₯ λ§μ μ’
λ₯μ ν°μΌλͺ¬μ κ³ λ₯΄κΈ° μν΄μλ 3λ² ν°μΌλͺ¬ ν λ§λ¦¬μ 2λ² ν°μΌλͺ¬ λ λ§λ¦¬λ₯Ό κ³ λ₯΄κ±°λ, νΉμ 3λ² ν°μΌλͺ¬ λ λ§λ¦¬μ 2λ² ν°μΌλͺ¬ ν λ§λ¦¬λ₯Ό κ³ λ₯΄λ©΄ λ©λλ€. λ°λΌμ μ΅λ κ³ λ₯Ό μ μλ ν°μΌλͺ¬ μ’
λ₯μ μλ 2μ
λλ€.
μ μ¬μκ°μ λλμ΄ λ€μ΄, μΌλΆ νμμ΄ μ²΄μ‘볡μ λλλΉνμ΅λλ€. λ€νν μ¬λ² 체μ‘λ³΅μ΄ μλ νμμ΄ μ΄λ€μκ² μ²΄μ‘볡μ λΉλ €μ£Όλ € ν©λλ€. νμλ€μ λ²νΈλ 체격 μμΌλ‘ λ§€κ²¨μ Έ μμ΄, λ°λ‘ μλ²νΈμ νμμ΄λ λ°λ‘ λ·λ²νΈμ νμμκ²λ§ 체μ‘볡μ λΉλ €μ€ μ μμ΅λλ€. μλ₯Ό λ€μ΄, 4λ² νμμ 3λ² νμμ΄λ 5λ² νμμκ²λ§ 체μ‘볡μ λΉλ €μ€ μ μμ΅λλ€. 체μ‘λ³΅μ΄ μμΌλ©΄ μμ μ λ€μ μ μκΈ° λλ¬Έμ 체μ‘볡μ μ μ ν λΉλ € μ΅λν λ§μ νμμ΄ μ²΄μ‘μμ μ λ€μ΄μΌ ν©λλ€.
μ 체 νμμ μ n, 체μ‘볡μ λλλΉν νμλ€μ λ²νΈκ° λ΄κΈ΄ λ°°μ΄ lost, μ¬λ²μ 체μ‘볡μ κ°μ Έμ¨ νμλ€μ λ²νΈκ° λ΄κΈ΄ λ°°μ΄ reserveκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, 체μ‘μμ μ λ€μ μ μλ νμμ μ΅λκ°μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
n | lost | reserve | return |
---|---|---|---|
5 | [2, 4] | [1, 3, 5] | 5 |
5 | [2, 4] | [3] | 4 |
3 | [3] | [1] | 2 |
μμ #1
1λ² νμμ΄ 2λ² νμμκ² μ²΄μ‘볡μ λΉλ €μ£Όκ³ , 3λ² νμμ΄λ 5λ² νμμ΄ 4λ² νμμκ² μ²΄μ‘볡μ λΉλ €μ£Όλ©΄ νμ 5λͺ
μ΄ μ²΄μ‘μμ
μ λ€μ μ μμ΅λλ€.
μμ #2
3λ² νμμ΄ 2λ² νμμ΄λ 4λ² νμμκ² μ²΄μ‘볡μ λΉλ €μ£Όλ©΄ νμ 4λͺ
μ΄ μ²΄μ‘μμ
μ λ€μ μ μμ΅λλ€.
μ΄μ체μ μ μν μ€ νλλ μ»΄ν¨ν° μμ€ν μ μμμ ν¨μ¨μ μΌλ‘ κ΄λ¦¬νλ κ²μ λλ€. μ΄ λ¬Έμ μμλ μ΄μ체μ κ° λ€μ κ·μΉμ λ°λΌ νλ‘μΈμ€λ₯Ό κ΄λ¦¬ν κ²½μ° νΉμ νλ‘μΈμ€κ° λͺ λ²μ§Έλ‘ μ€νλλμ§ μμλ΄λ©΄ λ©λλ€.
μλ₯Ό λ€μ΄ νλ‘μΈμ€ 4κ° [A, B, C, D]κ° μμλλ‘ μ€ν λκΈ° νμ λ€μ΄μκ³ , μ°μ μμκ° [2, 1, 3, 2]λΌλ©΄ [C, D, A, B] μμΌλ‘ μ€ννκ² λ©λλ€.
νμ¬ μ€ν λκΈ° ν(Queue)μ μλ νλ‘μΈμ€μ μ€μλκ° μμλλ‘ λ΄κΈ΄ λ°°μ΄ priorities
μ, λͺ λ²μ§Έλ‘ μ€νλλμ§ μκ³ μΆμ νλ‘μΈμ€μ μμΉλ₯Ό μλ €μ£Όλ location
μ΄ λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, ν΄λΉ νλ‘μΈμ€κ° λͺ λ²μ§Έλ‘ μ€νλλμ§ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
priorities | location | return |
---|---|---|
[2, 1, 3, 2] | 2 | 1 |
[1, 1, 9, 1, 1, 1] | 0 | 5 |
μμ #1
λ¬Έμ μ λμ¨ μμ κ°μ΅λλ€.
μμ #2
6κ°μ νλ‘μΈμ€ [A, B, C, D, E, F]κ° λκΈ° νμ μκ³ μ€μλκ° [1, 1, 9, 1, 1, 1] μ΄λ―λ‘ [C, D, E, F, A, B] μμΌλ‘ μ€νλ©λλ€. λ°λΌμ Aλ 5λ²μ§Έλ‘ μ€νλ©λλ€.
Leoλ μΉ΄ν«μ μ¬λ¬ κ°λ€κ° μλ κ·Έλ¦Όκ³Ό κ°μ΄ μ€μμλ λ
ΈλμμΌλ‘ μΉ ν΄μ Έ μκ³ ν
λ리 1μ€μ κ°μμΌλ‘ μΉ ν΄μ Έ μλ 격μ λͺ¨μ μΉ΄ν«μ λ΄€μ΅λλ€.
Leoλ μ§μΌλ‘ λμμμ μκΉ λ³Έ μΉ΄ν«μ λ
Έλμκ³Ό κ°μμΌλ‘ μμΉ λ 격μμ κ°μλ κΈ°μ΅νμ§λ§, μ 체 μΉ΄ν«μ ν¬κΈ°λ κΈ°μ΅νμ§ λͺ»νμ΅λλ€.
Leoκ° λ³Έ μΉ΄ν«μμ κ°μ 격μμ μ brown, λ Έλμ 격μμ μ yellowκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ μΉ΄ν«μ κ°λ‘, μΈλ‘ ν¬κΈ°λ₯Ό μμλλ‘ λ°°μ΄μ λ΄μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
brown | yellow | return |
---|---|---|
10 | 2 | [4, 3] |
8 | 1 | [3, 3] |
24 | 24 | [8, 6] |
λ°°μ΄ arrκ° μ£Όμ΄μ§λλ€. λ°°μ΄ arrμ κ° μμλ μ«μ 0λΆν° 9κΉμ§λ‘ μ΄λ£¨μ΄μ Έ μμ΅λλ€. μ΄λ, λ°°μ΄ arrμμ μ°μμ μΌλ‘ λνλλ μ«μλ νλλ§ λ¨κΈ°κ³ μ λΆ μ κ±°νλ €κ³ ν©λλ€. λ¨, μ κ±°λ ν λ¨μ μλ€μ λ°νν λλ λ°°μ΄ arrμ μμλ€μ μμλ₯Ό μ μ§ν΄μΌ ν©λλ€. μλ₯Ό λ€λ©΄,
arr | answer |
---|---|
[1,1,3,3,0,1,1] | [1,3,0,1] |
[4,4,4,3,3] | [4,3] |
μ
μΆλ ₯ μ #1,2
λ¬Έμ μ μμμ κ°μ΅λλ€.
무μΈλμ κ°ν μ¬λλ€μ ꡬλͺ 보νΈλ₯Ό μ΄μ©νμ¬ κ΅¬μΆνλ €κ³ ν©λλ€. ꡬλͺ 보νΈλ μμμ ν λ²μ μ΅λ 2λͺ μ© λ°μ ν μ μκ³ , λ¬΄κ² μ νλ μμ΅λλ€.
μλ₯Ό λ€μ΄, μ¬λλ€μ λͺΈλ¬΄κ²κ° [70kg, 50kg, 80kg, 50kg]μ΄κ³ ꡬλͺ 보νΈμ λ¬΄κ² μ νμ΄ 100kgμ΄λΌλ©΄ 2λ²μ§Έ μ¬λκ³Ό 4λ²μ§Έ μ¬λμ κ°μ΄ ν μ μμ§λ§ 1λ²μ§Έ μ¬λκ³Ό 3λ²μ§Έ μ¬λμ 무κ²μ ν©μ 150kgμ΄λ―λ‘ κ΅¬λͺ 보νΈμ λ¬΄κ² μ νμ μ΄κ³Όνμ¬ κ°μ΄ ν μ μμ΅λλ€.
ꡬλͺ 보νΈλ₯Ό μ΅λν μ κ² μ¬μ©νμ¬ λͺ¨λ μ¬λμ ꡬμΆνλ €κ³ ν©λλ€.
μ¬λλ€μ λͺΈλ¬΄κ²λ₯Ό λ΄μ λ°°μ΄ peopleκ³Ό ꡬλͺ 보νΈμ λ¬΄κ² μ ν limitκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, λͺ¨λ μ¬λμ ꡬμΆνκΈ° μν΄ νμν ꡬλͺ λ³΄νΈ κ°μμ μ΅μκ°μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
people | limit | return |
---|---|---|
[70, 50, 80, 50] | 100 | 3 |
[70, 80, 50] | 100 | 3 |
λ€νΈμν¬λ μ»΄ν¨ν° μνΈ κ°μ μ 보λ₯Ό κ΅νν μ μλλ‘ μ°κ²°λ ννλ₯Ό μλ―Έν©λλ€. μλ₯Ό λ€μ΄, μ»΄ν¨ν° Aμ μ»΄ν¨ν° Bκ° μ§μ μ μΌλ‘ μ°κ²°λμ΄μκ³ , μ»΄ν¨ν° Bμ μ»΄ν¨ν° Cκ° μ§μ μ μΌλ‘ μ°κ²°λμ΄ μμ λ μ»΄ν¨ν° Aμ μ»΄ν¨ν° Cλ κ°μ μ μΌλ‘ μ°κ²°λμ΄ μ 보λ₯Ό κ΅νν μ μμ΅λλ€. λ°λΌμ μ»΄ν¨ν° A, B, Cλ λͺ¨λ κ°μ λ€νΈμν¬ μμ μλ€κ³ ν μ μμ΅λλ€.
μ»΄ν¨ν°μ κ°μ n, μ°κ²°μ λν μ λ³΄κ° λ΄κΈ΄ 2μ°¨μ λ°°μ΄ computersκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, λ€νΈμν¬μ κ°μλ₯Ό return νλλ‘ solution ν¨μλ₯Ό μμ±νμμ€.
n-1
μΈ μ μλ‘ ννν©λλ€.n | computers | return |
---|---|---|
3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
μμ #1
μλμ κ°μ΄ 2κ°μ λ€νΈμν¬κ° μμ΅λλ€.
μμ #2
μλμ κ°μ΄ 1κ°μ λ€νΈμν¬κ° μμ΅λλ€.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. πππ
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google β€οΈ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.