๐ 1. ๋ฌธ์ ์ค๋ช
์ถ๋ฐ์ง์ ๋ถํฐ distance๋งํผ ๋จ์ด์ง ๊ณณ์ ๋์ฐฉ์ง์ ์ด ์์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ๊ทธ์ฌ์ด์๋ ๋ฐ์๋ค์ด ๋์ฌ์์ต๋๋ค. ๋ฐ์ ์ค ๋ช ๊ฐ๋ฅผ ์ ๊ฑฐํ๋ ค๊ณ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด, ๋์ฐฉ์ง์ ์ด 25๋งํผ ๋จ์ด์ ธ ์๊ณ , ๋ฐ์๊ฐ [2, 14, 11, 21, 17] ์ง์ ์ ๋์ฌ์์ ๋ ๋ฐ์ 2๊ฐ๋ฅผ ์ ๊ฑฐํ๋ฉด ์ถ๋ฐ์ง์ , ๋์ฐฉ์ง์ , ๋ฐ์ ๊ฐ์ ๊ฑฐ๋ฆฌ๊ฐ ์๋์ ๊ฐ์ต๋๋ค. ์์์ ๊ตฌํ ๊ฑฐ๋ฆฌ์ ์ต์๊ฐ ์ค์ ๊ฐ์ฅ ํฐ ๊ฐ์ 4์
๋๋ค.์ถ๋ฐ์ง์ ๋ถํฐ ๋์ฐฉ์ง์ ๊น์ง์ ๊ฑฐ๋ฆฌ distance, ๋ฐ์๋ค์ด ์๋ ์์น๋ฅผ ๋ด์ ๋ฐฐ์ด rocks, ์ ๊ฑฐํ ๋ฐ์์ ์ n์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ฐ์๋ฅผ n๊ฐ ์ ๊ฑฐํ ๋ค ๊ฐ ์ง์ ์ฌ์ด์ ๊ฑฐ๋ฆฌ์ ์ต์๊ฐ ์ค์ ๊ฐ์ฅ ํฐ ๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ๋์ฐฉ์ง์ ๊น์ง์ ๊ฑฐ๋ฆฌ dista..
My Tech Blog (ํ์ด)
๐ค 1. ๋ฌธ์ ์ค๋ช
๋ฌธ์ ์ค๋ช
n๋ช
์ด ์
๊ตญ์ฌ์ฌ๋ฅผ ์ํด ์ค์ ์์ ๊ธฐ๋ค๋ฆฌ๊ณ ์์ต๋๋ค. ๊ฐ ์
๊ตญ์ฌ์ฌ๋์ ์๋ ์ฌ์ฌ๊ด๋ง๋ค ์ฌ์ฌํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๋ค๋ฆ
๋๋ค. ์ฒ์์ ๋ชจ๋ ์ฌ์ฌ๋๋ ๋น์ด์์ต๋๋ค. ํ ์ฌ์ฌ๋์์๋ ๋์์ ํ ๋ช
๋ง ์ฌ์ฌ๋ฅผ ํ ์ ์์ต๋๋ค. ๊ฐ์ฅ ์์ ์ ์๋ ์ฌ๋์ ๋น์ด ์๋ ์ฌ์ฌ๋๋ก ๊ฐ์ ์ฌ์ฌ๋ฅผ ๋ฐ์ ์ ์์ต๋๋ค. ํ์ง๋ง ๋ ๋นจ๋ฆฌ ๋๋๋ ์ฌ์ฌ๋๊ฐ ์์ผ๋ฉด ๊ธฐ๋ค๋ ธ๋ค๊ฐ ๊ทธ๊ณณ์ผ๋ก ๊ฐ์ ์ฌ์ฌ๋ฅผ ๋ฐ์ ์๋ ์์ต๋๋ค.๋ชจ๋ ์ฌ๋์ด ์ฌ์ฌ๋ฅผ ๋ฐ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ต์๋ก ํ๊ณ ์ถ์ต๋๋ค. ์
๊ตญ์ฌ์ฌ๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ์ฌ๋ ์ n, ๊ฐ ์ฌ์ฌ๊ด์ด ํ ๋ช
์ ์ฌ์ฌํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด ๋ด๊ธด ๋ฐฐ์ด times๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฌ๋์ด ์ฌ์ฌ๋ฅผ ๋ฐ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ..
๐ค 1. ๋ฌธ์ ์ค๋ช
๋ฌธ์ ์ค๋ช
์ด์ค ์ฐ์ ์์ ํ๋ ๋ค์ ์ฐ์ฐ์ ํ ์ ์๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋งํฉ๋๋ค. ์ด์ค ์ฐ์ ์์ ํ๊ฐ ํ ์ฐ์ฐ operations๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฐ์ฐ์ ์ฒ๋ฆฌํ ํ ํ๊ฐ ๋น์ด์์ผ๋ฉด [0,0] ๋น์ด์์ง ์์ผ๋ฉด [์ต๋๊ฐ, ์ต์๊ฐ]์ return ํ๋๋ก solution ํจ์๋ฅผ ๊ตฌํํด์ฃผ์ธ์. ์ ํ์ฌํญoperations๋ ๊ธธ์ด๊ฐ 1 ์ด์ 1,000,000 ์ดํ์ธ ๋ฌธ์์ด ๋ฐฐ์ด์
๋๋ค.operations์ ์์๋ ํ๊ฐ ์ํํ ์ฐ์ฐ์ ๋ํ๋
๋๋ค.์์๋ “๋ช
๋ น์ด ๋ฐ์ดํฐ” ํ์์ผ๋ก ์ฃผ์ด์ง๋๋ค.- ์ต๋๊ฐ/์ต์๊ฐ์ ์ญ์ ํ๋ ์ฐ์ฐ์์ ์ต๋๊ฐ/์ต์๊ฐ์ด ๋ ์ด์์ธ ๊ฒฝ์ฐ, ํ๋๋ง ์ญ์ ํฉ๋๋ค.๋น ํ์ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ผ๋ ์ฐ์ฐ์ด ์ฃผ์ด์ง ๊ฒฝ์ฐ, ํด๋น ์ฐ์ฐ์ ๋ฌด์ํฉ๋๋ค. ์
์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #116๊ณผ -..
๐ 1. ๋ฌธ์ ์ค๋ช
ํ๋๋์คํฌ๋ ํ ๋ฒ์ ํ๋์ ์์
๋ง ์ํํ ์ ์์ต๋๋ค. ๋์คํฌ ์ปจํธ๋กค๋ฌ๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ต๋๋ค. ๊ฐ์ฅ ์ผ๋ฐ์ ์ธ ๋ฐฉ๋ฒ์ ์์ฒญ์ด ๋ค์ด์จ ์์๋๋ก ์ฒ๋ฆฌํ๋ ๊ฒ์
๋๋ค. ์๋ฅผ ๋ค์ด- 0ms ์์ ์ 3ms๊ฐ ์์๋๋ A์์
์์ฒญ - 1ms ์์ ์ 9ms๊ฐ ์์๋๋ B์์
์์ฒญ - 2ms ์์ ์ 6ms๊ฐ ์์๋๋ C์์
์์ฒญ ์ ๊ฐ์ ์์ฒญ์ด ๋ค์ด์์ต๋๋ค. ์ด๋ฅผ ๊ทธ๋ฆผ์ผ๋ก ํํํ๋ฉด ์๋์ ๊ฐ์ต๋๋ค. ํ ๋ฒ์ ํ๋์ ์์ฒญ๋ง์ ์ํํ ์ ์๊ธฐ ๋๋ฌธ์ ๊ฐ๊ฐ์ ์์
์ ์์ฒญ๋ฐ์ ์์๋๋ก ์ฒ๋ฆฌํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์ฒ๋ฆฌ ๋ฉ๋๋ค.- A: 3ms ์์ ์ ์์
์๋ฃ (์์ฒญ์์ ์ข
๋ฃ๊น์ง : 3ms) - B: 1ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 3ms ์์ ์ ์์
์ ์์ํด์ 12ms ์์ ์ ์์
์๋ฃ(์์ฒญ์์ ์ข
๋ฃ๊น์ง ..
๐ 1. ๋ฌธ์ ์ค๋ช
์
์ถ๋ ฅ ์ ์ค๋ช
1. ์ค์ฝ๋น ์ง์๊ฐ 1์ธ ์์๊ณผ 2์ธ ์์์ ์์ผ๋ฉด ์์์ ์ค์ฝ๋น ์ง์๊ฐ ์๋์ ๊ฐ์ด ๋ฉ๋๋ค.์๋ก์ด ์์์ ์ค์ฝ๋น ์ง์ = 1 + (2 * 2) = 5๊ฐ์ง ์์์ ์ค์ฝ๋น ์ง์ = [5, 3, 9, 10, 12] 2. ์ค์ฝ๋น ์ง์๊ฐ 3์ธ ์์๊ณผ 5์ธ ์์์ ์์ผ๋ฉด ์์์ ์ค์ฝ๋น ์ง์๊ฐ ์๋์ ๊ฐ์ด ๋ฉ๋๋ค.์๋ก์ด ์์์ ์ค์ฝ๋น ์ง์ = 3 + (5 * 2) = 13๊ฐ์ง ์์์ ์ค์ฝ๋น ์ง์ = [13, 9, 10, 12] ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๊ฐ 7 ์ด์์ด ๋์๊ณ ์ด๋ ์์ ํ์๋ 2ํ์
๋๋ค.๐ก 2. ์ ๊ทผ๋ฐฉ์ํญ์ ์ ๋ ฌ์ด ๋์ด ์์ด์ ๋ฎ์ ์์๋ถํฐ ๊บผ๋ผ ์ ์๋ ์ฐ์ ์์ ํ ์ฌ์ฉPriority Queue(์ฐ์ ์์ํ)๋ฐฐ์ด์ ์ฐ์ ์์ ํ์ ๋ฃ๋๋คํ ์์์ ๊ฐ์ฅ ๋ฎ์ ์ซ์๊ฐ k..
๐ 1. ๋ฌธ์ ์ค๋ช
๐ก 2. ์ ๊ทผ๋ฐฉ์์ด์คfor๋ฌธํ์ฌ ์ธ๋ฑ์ค์ ์๋ ์์๊ณผ ์ดํ ๋ชจ๋ ๊ฐ์ ๋น๊ตํ๋ฉด์ ํ์ฌ ์์๊ฐ ๋น๊ตํ๊ณ ์๋ ์์๋ณด๋ค ์ปค์ง๋ฉด break;๋ฅผ ๊ฑธ์ด์ค๋ค.๊ทธ ์ ๊น์ง๋ answer[i]++์ ํด ์ค๋ค. ํ์ฌ ์์๊ฐ ๋ ํฌ๋ค๋ ๋ง์ ์ดํ์ ๊ฐ๊ฒฉ์ด ๋จ์ด์ก๋ค๋ ๊ฒ์ ์๋ฏธํ๊ธฐ ๋๋ฌธ์ด๋ค. ํ์ฌ ์์๊ฐ ๋น๊ตํ๋ ๊ฐ๊ณผ ๊ฐ๊ฑฐ๋ ๋ ์ ๋ค๋ฉด ๊ฐ๊ฒฉ์ด ์ ์ง๋๊ฑฐ๋ ์ค๋ฅธ ๊ฒ์ด๋ค.์คํ(Stack)๊ทผ๋ฐ ์ด๊ฒ ์คํ/ํ ๋ฌธ์ ๋ผ๋๋ฐ ์คํ์ผ๋ก๋ ์ด๋ป๊ฒ ํ์ง? ์ค์๊ทธ๋์ ๋ค๋ฅธ ์ฌ๋๋ค์ ์ด๋ป๊ฒ ํธ๋ ์ง ์ข ์ฐพ์ ๋ดค๋ค. ๊ทธ๋ฅ ์ด์คํฌ๋ฌธ์ผ๋ก ํธ๋๊ฒ ๋ ๊ฐ๋จํ ๊ฒ ๊ฐ๋ค. prices์ ์ธ๋ฑ์ค๋ฅผ ์คํ์ ๋ฃ์ด ์ฃผ๋ฉด์ ํ์ฌ ๊ฐ๊ฒฉ๊ณผ ์คํ์ ๊ฐ์ฅ ์ ๊ฐ๊ฒฉ์ ๋น๊ตํด์ค๋ค. ์คํ์ด ๋น์ด์์ง ์๊ณ , ํ์ฌ ๊ฐ๊ฒฉ์ด ์คํ์ ๊ฐ์ฅ ์ ๊ฐ๊ฒฉ๋ณด๋ค ์์ผ๋ฉด ๋ฐ๋ก ๊ฐ๊ฒฉ์ด..
๐ 1. ๋ฌธ์ ์ค๋ช
๐ก 2. ์ ๊ทผ๋ฐฉ์ Queueํธ๋ญ ์ง์
๋ก์ง: ๋ค๋ฆฌ์ ๋งจ ์ ํธ๋ญ์ด ๋๊ฐ๊ณ ์๋ก์ด ํธ๋ญ์ด ๋ค๋ฆฌ์ ์ฌ๋ผ๊ฐ ์ ์๋์ง ํ์ธํ ํ ๋ค๋ฆฌ์ ์ถ๊ฐ์ด๋์๊ฐ: ํธ๋ญ์ด ๋ค๋ฆฌ ์์ ์ค๋ฅด๋ฉด ๋งค 1์ด๋ง๋ค ํ ์นธ์ฉ ์์ผ๋ก ์ด๋ํจ.์กฐ๊ฑด ๊ฒ์ฌ: ๋ค๋ฆฌ๊ฐ ๊ฒฌ๋ ์ ์๋ ๋ฌด๊ฒ๋ฅผ ์ด๊ณผํ์ง ์๋ ๊ฒฝ์ฐ์๋ง ํธ๋ญ์ ์ถ๊ฐํ๋ฉฐ, ๊ทธ๋ ์ง ์์ผ๋ฉด 0์ ์ถ๊ฐํด์ ๋น ๊ณต๊ฐ ๋ง๋ค๊ธฐ bridge_length ์ฌ์ด์ฆ์ Queue ๋ง๋ค๊ณ 0๊ฐ์ผ๋ก ์ด๊ธฐํ(๋ค๋ฆฌ์ ํธ๋ญ ํ๋๋ ์๋ ์ํ)๋ณ์ currentWeight ํ์ฌ ๋ค๋ฆฌ ์์ ์ด ๋ฌด๊ฒ ๋ณ์ time ๊ฒฝ๊ณผ์๊ฐ(๋ฌธ์ ์์ returnํ ๊ฐ)๋ค๋ฆฌ์ ๊ธธ์ด๊ฐ 1์ด๊ฑฐ๋ ํธ๋ญ์ ๊ฐ์๊ฐ 1 ์ผ๋๋ ํด๋น time ๋จผ์ returnํธ๋ญ์ ๊ฐฏ์๋งํผ ์๋์ ๊ณผ์ ์ ๋ฐ๋ณต1. ๋ค๋ฆฌ์ ์๋ถ๋ถ ํธ๋ญ์ ํ์์ ์ ๊ฑฐ2. ..
1. ๋ฌธ์ ์ค๋ช
์์ #1๋ฌธ์ ์ ๋์จ ์์ ๊ฐ์ต๋๋ค. ์์ #26๊ฐ์ ํ๋ก์ธ์ค [A, B, C, D, E, F]๊ฐ ๋๊ธฐ ํ์ ์๊ณ ์ค์๋๊ฐ [1, 1, 9, 1, 1, 1] ์ด๋ฏ๋ก [C, D, E, F, A, B] ์์ผ๋ก ์คํ๋ฉ๋๋ค. ๋ฐ๋ผ์ A๋ 5๋ฒ์งธ๋ก ์คํ๋ฉ๋๋ค.2. ์ ๊ทผ๋ฐฉ์2-1. ๋ฐฐ์ด ์ชผ๊ฐ๊ธฐ (์ถ์ฒํ์ง ์์โ)๋ณด์๋ง์ ์ต๋๊ฐ์ ์ฐพ์์ ์ต๋๊ฐ์ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฐฐ์ด์ ์ชผ๊ฐ์ ๋ค์ ๋ถ์ด๋ฉด ๋ ๊ฑฐ ๊ฐ๋ค๊ณ ์๊ฐํ๋ค. priorities ๋ฐฐ์ด๋ฅผ ์ํํ๋ฉด์ ์ฐ์ ์์ max๊ฐ์ ์ฐพ๊ณ , ๊ทธ ๊ฐ์ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฐฐ์ด์ ๋ ๊ฐ๋ก ์ชผ๊ฐ ๋ค์, ์ ๋ค๋ก ์ด์ด์ ๋ถ์ด๋ ๊ฒ์ด๋ค. ๋๊ฒ ์ฝ๊ฒ ํ ์ค ์์๋๋ฐ ์๊ฐ๋ณด๋ค ์ด๋ ค์ ๊ณ ์์งํ ๊ณ์ ์คํจํ๋ค. ๋ฐฐ์ด ์ชผ๊ฐ๋ ๋ฉ์๋๋ฅผ ๊ตฌ๊ธ์์ ์ฐพ์๊ฐ๋ฉด์ ์ฝ๋๋ฅผ ์ฐ๋๋ฐ ์จ ๋ด๋ ค ๊ฐ์๋ก ..