๋ฐฑ์ค ๋ฒ์ง ์ก๊ฐํ ๋ฒ์ง์ผ๋ก ๋ ์ซ์๊ฐ ์์ ๋ ๋ช ๋ฒ์งธ...? ์ ๋ด๊ฐ ์ฐพ๋ ์ซ์๊ฐ ์์นํ๋์ง ์ฐพ์ผ๋ฉด ๋๋ ๋ฌธ์ !...์ฌ์ค ์กฐ๊ธ ํค๋งธ๋ค ๋ ๋ฒ์ด๋ ํ๋ ธ์ ใ ใ ...์ฝ๋๋ก ์์ฑํด๋ณด๋ ์ด๋ ต์ง ์์๋๋ฐ, ์ฝ๋๋ฅผ ์์ฑํ๊ธฐ๊น์ง ์ด๊ฒ ์ ๊ฒ ํด๋ณด๋ค๊ฐ ์ข ํค๋งธ๋ค ใ ใ ๊ทธ๋๋ ์ฑ๊ณต
QR์ฝ๋ ์์ฑ์ ๊ตฌํํ๊ณ ์๋๋ฐ ์ ํ redirect๊ฐ ๋ ์ผ์ด ์๋ ์ ๊ฐ redirect๊ฐ ๋ผ์ ๋๋ฅผ ๊ดด๋กญํ๋๋ผ...qr.jspqr.js์ ํ redirect ๋ ์ผ์ด ์์ ๊ฑฐ๋ผ๊ณ ์๊ฐํ๋๋ฐ ์๊พธ redirect๊ฐ ๋ผ์ ๋ถ๋ฌ์๋ QR๋ ๋ค์ ์ด๊ธฐํ๊ฐ ๋๋๋ผ ใ ใ ํ์ง๋ง?
๋ฐฑ์ค ์ค์ ์ด๋ ์๊ณ ๋ฆฌ์ฆ ์ข ์ด๋ฅผ n๋ฒ ์ ์์ ๋, ๋ํ๋ผ ์ ์๋ ์ ์ ๊ฒน์น๋ ์ ๋นผ๊ณ ์ถ๋ ฅํด๋ผ!์ด๊ฒ ์ฒ์ ๋ฌธ์ ๋ฅผ ๋ดค์ ๋ ์ ๋ง ๋ฌด์จ ๋ง์ธ์ง ๋ชจ๋ฅด๊ฒ ์ด์์ง์ ๊ทธ๋ ค๋ณด๊ธฐ๋ก ํ๋ค๋ง์ง๋ง์ ๊ทธ๋ฆฌ๊ธฐ ๋นก์ธ์ ๋ชป ๊ทธ๋ฆฐ ๊ฒ ๋ง์ต๋๋ค ์ฌํผ ๊ทธ๋ฆผ์ผ๋ก ์ ๋ฆฌํด๋ณด๋ ์ฌ์ ๋ค ์ข ์ด๋ฅผ ์ ์ผ๋ฉด ํ ๋ณ์
๋ฐฑ์ค ์ธํ์ ์ฌ์ฅ ๋ํ ๊ฑฐ์ค๋ฆ๋์ 0.25, 0.10, 0.05, 0.01 ๋ก ๋๋ ์ ๊ณ์ฐํ๋ฉด ๋๋ ๋ฌธ์ !์ ๋จ์ ๊ณ์ฐ์ ๊ธฐ์ฌ ์ค๋นํ๋ฉด์, ๊ทธ๋ฆฌ๊ณ ๊ต๊ณผ์ ์์ ๋ก ์ฌ์ฌ์ฐฎ๊ฒ ๋ดค๋๋ฐ ๋ฌ๋ฌ๋ ์ฒ์์ด์๋ค.๊ทธ๋๋ ์ด๋ ต์ง ์๊ฒ ํ ์ ์์๋ค์ต์ํ ๊ฑฐ ์ต๊ณ ์์ฆ ํ๋ก๊ทธ๋๋จธ์ค๋ง ์๋ฉ
ํ๋ก๊ทธ๋๋จธ์ค ๋ก๋์ ์ต๊ณ ์์์ ์ต์ ์์๊ฐ์ ์์๋ณผ ์ ์๊ฒ ๋ ๋ก๋ ์ฉ์ง์์ ๋ด๊ฐ ๋น์ฒจ๋ ์ ์๋ ์ต๊ณ ์ ๋ฑ์์ ์ต์ ์ ๋ฑ์๋ฅผ ํ์ธํด๋ผํ๊ต ๋ค๋ ๋ ์ฑํ๊ฒ ๋์๋ ๋์์ด ๋์ํด์ ์์๋ณผ ์ ์๊ฒ ๋... ์ด์ฉ๊ณ ... ๋ฌธ์ ์๋คfor๋ฌธ์ผ๋ก ํธ๋ ๋ฐฉ๋ฒ์ ํด๋ณผ๊น ํ๋๋ฐ ํ
ํ๋ก๊ทธ๋๋จธ์ค ๊ฐ์ ์ซ์๋ ์ซ์ด์ฐ์์ ์ผ๋ก ๋ํ๋๋ ์ซ์๋ ํ๋๋ง ๋จ๊ธฐ๊ณ ๋จ์ ์ซ์๋ ์ถ๋ ฅํ์ง ์์. ๋จ, hashSet์ฒ๋ผ ์ค๋ณต์ด ์์ ์๋ ๊ฒ ์๋๊ณ <์ฐ์์ ์ธ ๊ฐ์ ์> ๊ฐ ์๋ ๊ฒ์์ hashSet์ ๊ตณ์ด ๊ฐ์กฐํ๋๋ฉด!!๋ด๊ฐ์ค์๋ฅผํ๊ธฐ๋๋ฌธ์ด๋ค ํํ...๊ทธ๋ฆฌ๊ณ ํด๋น
ํ๋ก๊ทธ๋๋จธ์ค ์งํ ์ ๊ธฐ์งํ๋ฅผ ์ ์ ํ์๋ฅผ ์ ์ฅํ ์ ์ ๋ณ์ answer๋ฅผ ๋ง๋ค๊ณ 0์ ์ ์ฅํฉ๋๋ค.๋ฐ๋ณต๋ฌธ์ ์ด์ฉํด bill์ ์์ ๊ฐ์ด wallet์ ์์ ๊ฐ ๋ณด๋ค ํฌ๊ฑฐ๋ bill์ ํฐ ๊ฐ์ด wallet์ ํฐ ๊ฐ ๋ณด๋ค ํฐ ๋์ ์๋ ๊ณผ์ ์ ๋ฐ๋ณตํฉ๋๋ค.2-1. bill0์ด
ํ๋ก๊ทธ๋๋จธ์ค ๋น๋ฐ์ง๋ ์ํธํ ๋ ์ ์ ๋ฐฐ์ด์ ์ด์ง์๋ก ๋ฐ๊ฟ์ ๋ง์ ์ ํ๋ ๋ฌธ์ ์ฒ์์๋ ๋จ์ํ 2์ง์๋ก ๋ฐ๊ฟ์ ์๋ฆฟ์ ๋์๊ฐ๋ฉด์ ๋ง์ ๋ง ํด์ฃผ๋ ค๊ณ ํ๋๋ฐ ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋ค ์๋ฅผ ๋ค์ด, arr10 = 9, arr20 = 30 ์ผ ๋, ๊ฐ๊ฐ 2์ง์๋ก ๋ณํํ๋ฉด 1001, 111
ํ๋ก๊ทธ๋๋จธ์ค ์๋ ์ซ์ ๋ํ๊ธฐ 0~9๊น์ง ์ ์ค์ ์ฃผ์ด์ง ๋ฐฐ์ด์ ์๋ ์ซ์๋ค๋ง ๋ํด์ ์ถ๋ ฅํ๊ธฐhashSet์ ์ฌ์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํ์๋ค
๋ฐฑ์ค ์ ์ ๋ ฌํ๊ธฐ์ฒซ ์ค์ ์ ๋ ฅ๋ฐ์ ์ซ์๋งํผ ๋จ์ ์ซ์๋ฅผ ์ ๋ ฅ๋ฐ์์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ฃผ๋ ๋ฌธ์ ์ฑ๊ณต!
ํ๋ก๊ทธ๋๋จธ์ค ๊ฐ์ฅ ํฐ ์ ์ ์๊ฐ ๋ด๊ธด ๋ฐฐ์ด numbers๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์์๋ฅผ ์ฌ๋ฐฐ์นํ์ฌ ๋ง๋ค ์ ์๋ ๊ฐ์ฅ ํฐ ์๋ฅผ ๋ฌธ์์ด๋ก ๋ฐ๊ฟ์ ์ถ๋ ฅํด๋ผ.์ฒ์์๋ ๊ทธ๋ฅ ๋จ์ํ ArrayList๋ก ์ฌ๋ฐฐ์นํด์ ๊ฐ์ฅ ๋ง์ง๋ง ์์๋ถํฐ ์ถ๋ ฅํ๋ ค๊ณ ํ๋ค. ๊ทผ๋ฐ ๋ ์๋ฆฟ์ ์ ์๋ถ
ํ๋ก๊ทธ๋๋จธ์ค K๋ฒ์งธ ์array์ i๋ฒ์งธ ์ซ์๋ถํฐ j๋ฒ์งธ ์ซ์๊น์ง ์๋ฅธ ํ, ๋ฐฐ์ด์ ์ ๋ ฌํด์ k๋ฒ์งธ ์ซ์๋ฅผ ์ถ๋ ฅํด๋ผ์ด๋ฒ์๋ ArrayList๋ฅผ ์ฌ์ฉํด์ ํ์ด๋ดค๋คโ๏ธ์๋ ์ฐ๋ฆฌ๊ฐ ๋ฐฐ์ด์์ ์ฌ์ฉํ๋ index๊ฐ๋ ์ด ์๋ N๋ฒ์งธ~ N ๋ฒ์งธ~ ๋ผ์ index๋ ๋ค ๋ฐ๋ก ๊ณ์ฐํด์คฌ
ํ๋ก๊ทธ๋๋จธ์ค ์์ฃผํ์ง ๋ชปํ ์ ์ ์ ์๋ ๋ ๊ฐ์ ๋ฐฐ์ด์ ๋น๊ตํด์ ์์ฃผํ์ง ๋ชปํ ์ ์์ ์ด๋ฆ์ ์ถ๋ ฅ.๐ ์คํจ ๋ฒ์ ์ด๋ ๊ฒ ์งํ์ ํ๋๋ฐ ์ค๋ต์ด ๋์๋ค. ํ ์คํธ ์ผ์ด์ค๋ฅผ ๋ณด๋, ์ด๋ฆ์ด ๊ฐ์๋ฐ ํ ์ฌ๋์ ์์ฃผํ๊ณ ๋ค๋ฅธ ํ ์ฌ๋์ ์์ฃผํ์ง ์์ ๊ฒ์ ํ์ธํ ์ ์์๋ค.๊ทธ๋์
ํ๋ก๊ทธ๋๋จธ์ค ํฐ์ผ๋ชฌํฐ์ผ๋ชฌ N๋ง๋ฆฌ๊ฐ ์๊ณ , N/2๋ง๋ฆฌ๋ง ๊ณ ๋ฅผ ์ ์๋ค. ์ต๋ํ ๋ง์ ์ข ๋ฅ์ ํฐ์ผ๋ชฌ์ ๊ตฌํ๋ ค๊ณ ํ ๋ ์ต๋๋ก ๋ง์ ์ข ๋ฅ์ ์๋ฅผ ๊ตฌํด๋ผ์ฌ์ค ๋ฌธ์ ์ดํดํ๋๋ฐ ๊ฝค ๊ฑธ๋ ธ๋ค. ์ฒ์์๋ ArrayList๋ก ์ค๋ณต๋ ๊ฑธ ์ผ์ผ์ด ์ง์ฐ๋ ค๋ ๋ฉ์ฒญํ์ง์ ํ๋ค๊ฐ HashSet ์