๐ ์ฝ๋ฉํ ์คํธ ๋๋น : PS
[ํ๋ก๊ทธ๋๋จธ์ค] ์ต๊ณ ์ ์งํฉ (level3, python)
๋ฌธ์ ์ค๋ช ์์ฐ์ n ๊ฐ๋ก ์ด๋ฃจ์ด์ง ์ค๋ณต ์งํฉ(multi set, ํธ์์ ์ดํ์๋ "์งํฉ"์ผ๋ก ํต์นญ) ์ค์ ๋ค์ ๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์งํฉ์ ์ต๊ณ ์ ์งํฉ์ด๋ผ๊ณ ํฉ๋๋ค. ๊ฐ ์์์ ํฉ์ด S๊ฐ ๋๋ ์์ ์งํฉ ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ฉด์ ๊ฐ ์์์ ๊ณฑ ์ด ์ต๋๊ฐ ๋๋ ์งํฉ ์๋ฅผ ๋ค์ด์ ์์ฐ์ 2๊ฐ๋ก ์ด๋ฃจ์ด์ง ์งํฉ ์ค ํฉ์ด 9๊ฐ ๋๋ ์งํฉ์ ๋ค์๊ณผ ๊ฐ์ด 4๊ฐ๊ฐ ์์ต๋๋ค. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } ๊ทธ์ค ๊ฐ ์์์ ๊ณฑ์ด ์ต๋์ธ { 4, 5 }๊ฐ ์ต๊ณ ์ ์งํฉ์ ๋๋ค. ์งํฉ์ ์์์ ๊ฐ์ n๊ณผ ๋ชจ๋ ์์๋ค์ ํฉ s๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ต๊ณ ์ ์งํฉ์ return ํ๋ solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ ์ต๊ณ ์ ์งํฉ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ 1์ฐจ์ ๋ฐฐ์ด(list, vecto..
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ ๋์งํ (level2, python)
๋ฌธ์ ์ค๋ช โณโณ ๊ฒ์๋ํ๊ฐ ๊ฐ์ต๋์์ต๋๋ค. ์ด ๋ํ๋ N๋ช ์ด ์ฐธ๊ฐํ๊ณ , ํ ๋๋จผํธ ํ์์ผ๋ก ์งํ๋ฉ๋๋ค. N๋ช ์ ์ฐธ๊ฐ์๋ ๊ฐ๊ฐ 1๋ถํฐ N๋ฒ์ ์ฐจ๋ก๋๋ก ๋ฐฐ์ ๋ฐ์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ , 1๋ฒ↔2๋ฒ, 3๋ฒ↔4๋ฒ, ... , N-1๋ฒ↔N๋ฒ์ ์ฐธ๊ฐ์๋ผ๋ฆฌ ๊ฒ์์ ์งํํฉ๋๋ค. ๊ฐ ๊ฒ์์์ ์ด๊ธด ์ฌ๋์ ๋ค์ ๋ผ์ด๋์ ์ง์ถํ ์ ์์ต๋๋ค. ์ด๋, ๋ค์ ๋ผ์ด๋์ ์ง์ถํ ์ฐธ๊ฐ์์ ๋ฒํธ๋ ๋ค์ 1๋ฒ๋ถํฐ N/2๋ฒ์ ์ฐจ๋ก๋๋ก ๋ฐฐ์ ๋ฐ์ต๋๋ค. ๋ง์ฝ 1๋ฒ↔2๋ฒ ๋ผ๋ฆฌ ๊ฒจ๋ฃจ๋ ๊ฒ์์์ 2๋ฒ์ด ์น๋ฆฌํ๋ค๋ฉด ๋ค์ ๋ผ์ด๋์์ 1๋ฒ์ ๋ถ์ฌ๋ฐ๊ณ , 3๋ฒ↔4๋ฒ์์ ๊ฒจ๋ฃจ๋ ๊ฒ์์์ 3๋ฒ์ด ์น๋ฆฌํ๋ค๋ฉด ๋ค์ ๋ผ์ด๋์์ 2๋ฒ์ ๋ถ์ฌ๋ฐ๊ฒ ๋ฉ๋๋ค. ๊ฒ์์ ์ต์ข ํ ๋ช ์ด ๋จ์ ๋๊น์ง ์งํ๋ฉ๋๋ค. ์ด๋, ์ฒ์ ๋ผ์ด๋์์ A๋ฒ์ ๊ฐ์ง ์ฐธ๊ฐ์๋ ๊ฒฝ์์๋ก ์๊ฐํ๋ B๋ฒ ์ฐธ๊ฐ์์ ๋ช ..
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ฉ๋ฆฌ ๋ฐ๊ธฐ (level2, python)
๋ฌธ์ ์ค๋ช ํจ์ง์ด๋ ๋ฉ๋ฆฌ ๋ฐ๊ธฐ๋ฅผ ์ฐ์ตํ๊ณ ์์ต๋๋ค. ํจ์ง์ด๋ ํ๋ฒ์ 1์นธ, ๋๋ 2์นธ์ ๋ธ ์ ์์ต๋๋ค. ์นธ์ด ์ด 4๊ฐ ์์ ๋, ํจ์ง์ด๋ (1์นธ, 1์นธ, 1์นธ, 1์นธ) (1์นธ, 2์นธ, 1์นธ) (1์นธ, 1์นธ, 2์นธ) (2์นธ, 1์นธ, 1์นธ) (2์นธ, 2์นธ) ์ 5๊ฐ์ง ๋ฐฉ๋ฒ์ผ๋ก ๋งจ ๋ ์นธ์ ๋๋ฌํ ์ ์์ต๋๋ค. ๋ฉ๋ฆฌ๋ฐ๊ธฐ์ ์ฌ์ฉ๋ ์นธ์ ์ n์ด ์ฃผ์ด์ง ๋, ํจ์ง์ด๊ฐ ๋์ ๋๋ฌํ๋ ๋ฐฉ๋ฒ์ด ๋ช ๊ฐ์ง์ธ์ง ์์๋ด, ์ฌ๊ธฐ์ 1234567๋ฅผ ๋๋ ๋๋จธ์ง๋ฅผ ๋ฆฌํดํ๋ ํจ์, solution์ ์์ฑํ์ธ์. ์๋ฅผ ๋ค์ด 4๊ฐ ์ ๋ ฅ๋๋ค๋ฉด, 5๋ฅผ returnํ๋ฉด ๋ฉ๋๋ค. ์ ํ ์ฌํญ n์ 1 ์ด์, 2000 ์ดํ์ธ ์ ์์ ๋๋ค. ์ ์ถ๋ ฅ ์ n result 4 5 3 3 ์ ์ถ๋ ฅ ์ ์ค๋ช ์ ์ถ๋ ฅ ์ #1 ์์์ ์ค๋ช ํ ๋ด์ฉ๊ณผ ๊ฐ์ต๋๋ค. ์ ..
[ํ๋ก๊ทธ๋๋จธ์ค] N๊ฐ์ ์ต์๊ณต๋ฐฐ์ (level2, python)
๋ฌธ์ ์ค๋ช ๋ ์์ ์ต์๊ณต๋ฐฐ์(Least Common Multiple)๋ ์ ๋ ฅ๋ ๋ ์์ ๋ฐฐ์ ์ค ๊ณตํต์ด ๋๋ ๊ฐ์ฅ ์์ ์ซ์๋ฅผ ์๋ฏธํฉ๋๋ค. ์๋ฅผ ๋ค์ด 2์ 7์ ์ต์๊ณต๋ฐฐ์๋ 14๊ฐ ๋ฉ๋๋ค. ์ ์๋ฅผ ํ์ฅํด์, n๊ฐ์ ์์ ์ต์๊ณต๋ฐฐ์๋ n ๊ฐ์ ์๋ค์ ๋ฐฐ์ ์ค ๊ณตํต์ด ๋๋ ๊ฐ์ฅ ์์ ์ซ์๊ฐ ๋ฉ๋๋ค. n๊ฐ์ ์ซ์๋ฅผ ๋ด์ ๋ฐฐ์ด arr์ด ์ ๋ ฅ๋์์ ๋ ์ด ์๋ค์ ์ต์๊ณต๋ฐฐ์๋ฅผ ๋ฐํํ๋ ํจ์, solution์ ์์ฑํด ์ฃผ์ธ์. ์ ํ ์ฌํญ arr์ ๊ธธ์ด 1์ด์, 15์ดํ์ธ ๋ฐฐ์ด์ ๋๋ค. arr์ ์์๋ 100 ์ดํ์ธ ์์ฐ์์ ๋๋ค. ์ ์ถ๋ ฅ ์ arr result [2,6,8,14] 168 [1,2,3] 6 ํ์ด ์ฝ๋ def GCD(a, b): while b: a, b = b, a%b return a def LCM(a, ..
[ํ๋ก๊ทธ๋๋จธ์ค] ๊ตฌ๋ช ๋ณดํธ (level2, python)
๋ฌธ์ ์ค๋ช ๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋๋ค์ ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ ์์์ ํ ๋ฒ์ ์ต๋ 2๋ช ์ฉ ๋ฐ์ ํ ์ ์๊ณ , ๋ฌด๊ฒ ์ ํ๋ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๊ฐ [70kg, 50kg, 80kg, 50kg]์ด๊ณ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ด 100kg์ด๋ผ๋ฉด 2๋ฒ์งธ ์ฌ๋๊ณผ 4๋ฒ์งธ ์ฌ๋์ ๊ฐ์ด ํ ์ ์์ง๋ง 1๋ฒ์งธ ์ฌ๋๊ณผ 3๋ฒ์งธ ์ฌ๋์ ๋ฌด๊ฒ์ ํฉ์ 150kg์ด๋ฏ๋ก ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ ์ด๊ณผํ์ฌ ๊ฐ์ด ํ ์ ์์ต๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ต๋ํ ์ ๊ฒ ์ฌ์ฉํ์ฌ ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๋ฅผ ๋ด์ ๋ฐฐ์ด people๊ณผ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ limit๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๊ธฐ ์ํด ํ์ํ ๊ตฌ๋ช ๋ณดํธ ๊ฐ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์..
[ํ๋ก๊ทธ๋๋จธ์ค] ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ (level2, python)
๋ฌธ์ ์ค๋ช ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๋, ์ํ๋ฒณ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ง ๋ฌธ์์ด์ ๊ฐ์ง๊ณ ์์ํฉ๋๋ค. ๋จผ์ ๋ฌธ์์ด์์ ๊ฐ์ ์ํ๋ฒณ์ด 2๊ฐ ๋ถ์ด ์๋ ์ง์ ์ฐพ์ต๋๋ค. ๊ทธ๋ค์, ๊ทธ ๋์ ์ ๊ฑฐํ ๋ค, ์๋ค๋ก ๋ฌธ์์ด์ ์ด์ด ๋ถ์ ๋๋ค. ์ด ๊ณผ์ ์ ๋ฐ๋ณตํด์ ๋ฌธ์์ด์ ๋ชจ๋ ์ ๊ฑฐํ๋ค๋ฉด ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๊ฐ ์ข ๋ฃ๋ฉ๋๋ค. ๋ฌธ์์ด S๊ฐ ์ฃผ์ด์ก์ ๋, ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๋ฅผ ์ฑ๊ณต์ ์ผ๋ก ์ํํ ์ ์๋์ง ๋ฐํํ๋ ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์. ์ฑ๊ณต์ ์ผ๋ก ์ํํ ์ ์์ผ๋ฉด 1์, ์๋ ๊ฒฝ์ฐ 0์ ๋ฆฌํดํด์ฃผ๋ฉด ๋ฉ๋๋ค. ์๋ฅผ ๋ค์ด, ๋ฌธ์์ด S = baabaa ๋ผ๋ฉด b aa baa → bb aa → aa → ์ ์์๋ก ๋ฌธ์์ด์ ๋ชจ๋ ์ ๊ฑฐํ ์ ์์ผ๋ฏ๋ก 1์ ๋ฐํํฉ๋๋ค. ์ ํ์ฌํญ ๋ฌธ์์ด์ ๊ธธ์ด : 1,000,000์ดํ์ ์์ฐ์ ๋ฌธ์์ด์ ๋ชจ๋ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ..
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ด ๋๋ง์๊ธฐ (level2, python)
๋ฌธ์ ์ค๋ช 1๋ถํฐ n๊น์ง ๋ฒํธ๊ฐ ๋ถ์ด์๋ n๋ช ์ ์ฌ๋์ด ์์ด ๋๋ง์๊ธฐ๋ฅผ ํ๊ณ ์์ต๋๋ค. ์์ด ๋๋ง์๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ผ๋ก ์งํ๋ฉ๋๋ค. 1๋ฒ๋ถํฐ ๋ฒํธ ์์๋๋ก ํ ์ฌ๋์ฉ ์ฐจ๋ก๋๋ก ๋จ์ด๋ฅผ ๋งํฉ๋๋ค. ๋ง์ง๋ง ์ฌ๋์ด ๋จ์ด๋ฅผ ๋งํ ๋ค์์๋ ๋ค์ 1๋ฒ๋ถํฐ ์์ํฉ๋๋ค. ์์ฌ๋์ด ๋งํ ๋จ์ด์ ๋ง์ง๋ง ๋ฌธ์๋ก ์์ํ๋ ๋จ์ด๋ฅผ ๋งํด์ผ ํฉ๋๋ค. ์ด์ ์ ๋ฑ์ฅํ๋ ๋จ์ด๋ ์ฌ์ฉํ ์ ์์ต๋๋ค. ํ ๊ธ์์ธ ๋จ์ด๋ ์ธ์ ๋์ง ์์ต๋๋ค. ๋ค์์ 3๋ช ์ด ๋๋ง์๊ธฐ๋ฅผ ํ๋ ์ํฉ์ ๋ํ๋ ๋๋ค. tank → kick → know → wheel → land → dream → mother → robot → tank ์ ๋๋ง์๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ์งํ๋ฉ๋๋ค. 1๋ฒ ์ฌ๋์ด ์์ ์ ์ฒซ ๋ฒ์งธ ์ฐจ๋ก์ tank๋ฅผ ๋งํฉ๋๋ค. 2๋ฒ ์ฌ๋์ด ์์ ์ ์ฒซ ๋ฒ์งธ ์ฐจ๋ก์ ..
[ํ๋ก๊ทธ๋๋จธ์ค] ์นดํซ (level2, python)
๋ฌธ์ ์ค๋ช Leo๋ ์นดํซ์ ์ฌ๋ฌ ๊ฐ๋ค๊ฐ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ค์์๋ ๋ ธ๋์์ผ๋ก ์น ํด์ ธ ์๊ณ ํ ๋๋ฆฌ 1์ค์ ๊ฐ์์ผ๋ก ์น ํด์ ธ ์๋ ๊ฒฉ์ ๋ชจ์ ์นดํซ์ ๋ดค์ต๋๋ค. Leo๋ ์ง์ผ๋ก ๋์์์ ์๊น ๋ณธ ์นดํซ์ ๋ ธ๋์๊ณผ ๊ฐ์์ผ๋ก ์์น ๋ ๊ฒฉ์์ ๊ฐ์๋ ๊ธฐ์ตํ์ง๋ง, ์ ์ฒด ์นดํซ์ ํฌ๊ธฐ๋ ๊ธฐ์ตํ์ง ๋ชปํ์ต๋๋ค. Leo๊ฐ ๋ณธ ์นดํซ์์ ๊ฐ์ ๊ฒฉ์์ ์ brown, ๋ ธ๋์ ๊ฒฉ์์ ์ yellow๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋ ์นดํซ์ ๊ฐ๋ก, ์ธ๋ก ํฌ๊ธฐ๋ฅผ ์์๋๋ก ๋ฐฐ์ด์ ๋ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ ๊ฐ์ ๊ฒฉ์์ ์ brown์ 8 ์ด์ 5,000 ์ดํ์ธ ์์ฐ์์ ๋๋ค. ๋ ธ๋์ ๊ฒฉ์์ ์ yellow๋ 1 ์ด์ 2,000,000 ์ดํ์ธ ์์ฐ์์ ๋๋ค. ์นดํซ์ ๊ฐ๋ก ๊ธธ์ด๋ ์ธ๋ก ๊ธธ์ด์ ๊ฐ๊ฑฐ๋, ์ธ๋ก ๊ธธ์ด๋ณด๋ค ..