
https://leetcode.com/problems/two-sum/์ด์ค ๋ฐ๋ณต๋ฌธ์ ํตํด ๋ฐฐ์ด ์์์ ํ๋์ฉ ์ ๊ทผํด์ ํน์ ์์๊ฐ์ ๋ํด๊ฐ๋ฉฐ target์ ๋ํ if๋ฌธ์ ์คํํ๋ค.์๊ฐ๋ณต์ก๋๊ฐ O(n2)์ด ๋์ฌ๊ฒ์ด ๋ปํ์ง๋ง, ๋ค๋ฅธ ๋ฐฉ๋ฒ์ ์๋ชจ๋ฅธ์ง๋ค.. ๊ณต๋ถํด์ผ์ง!

์ซ์๋ก ๋ฐ์ ํ๋ผ๋ฏธํฐ๋ฅผ ๋ฌธ์์ด๋ก ๋ณํํ ํ์, ๋ค์ง์ด์ ๋น๊ตํ๋คreversed()๊ฐ ์๊ทผ ์๊ฐ์ ๋ง์ด ์ก์๋จน๋ ๊ฑด์ง ์๊ฐ์ด ๋ง์ด ๊ฑธ๋ฆผ์ฐพ์๋ณด๋ ๋ฉ์๋ ์์ฒด๋ O(1)์ด๋ผ๋ ๋..Could you solve it without converting the integer to

๋์ ๋๋ฆฌ๋ก ๋ก๋ง ์ซ์์ ํด๋นํ๋ integer๋ฅผ ์ ์ฅํด๋๊ณ , ํด๋น ์์๋ฅผ ๋ง๋ ๋ ๋ํด์ค๋๋ค.์ธ๊ฐ์ง์ ๊ฒฝ์ฐ (I, X, C) ์ด์ ์ ํน์ ๋ฌธ์๊ฐ ์ฌ ๊ฒฝ์ฐ ๊ฐ์ ๋นผ์ ๋ํด์ค์ผ ํ๋ฏ๋ก answer+=-r, ์ผ๋ฐ์ ์ธ ๋ค๋ฅธ ๊ฒฝ์ฐ๋ answer์ ์๋๋ก ํธ๋ ๋ฐฉ๋ฒ์ด ์๋.. ๊ถ๊ธ

๊ฐ์ฅ ๊ธด ๊ณตํต์ prefix๋ฅผ ๊ฐ์ง ์ ์๋ ๊ฒฝ์ฐ๋ ๋ฌธ์์ด ๋ฐฐ์ด ์ค ๊ฐ์ฅ ์งง์ ๋ฌธ์์ด์ผ ๊ฒฝ์ฐ์ด๋ฏ๋ก shortestString์ ๊ธฐ์ค์ผ๋กํ๋ค.๋ฐฐ์ด์ ๋๋ฉด์ prefix๋ฅผ ๋ฐฐ์ด ๋ชจ๋ ๊ฐ์ง๊ณ ์๋ค๋ฉด ๋ค์ longest์ ์ ์ฅํ๊ณ , ๋ค์ ์ธ๋ฑ์ค๋ก ๋์ด๊ฐ๋ค.prefix๋ฅผ ํ๋๋ผ
Submission link : https://leetcode.com/submissions/detail/766534814/์คํ์ ์ฌ์ฉํ์ฌ ํผ๋ค.์ด๋ฆฐ ๊ดํธ์ด๋ฉด ์คํ์ ๋ฃ๊ณ ,๋ซํ ๊ดํธ์ด๋ฉด ์คํ์์ ํ๋๋ฅผ ๋ฝ์ ๋ฏธ๋ฆฌ ์ ์ธํด๋ dict์ ํค๋ก ์ ๊ทผํ์ฌ ์ผ์นํ ๊ฒฝ์ฐ ์ค
Submission link : https://leetcode.com/submissions/detail/767680892/๋งํฌ๋๋ฆฌ์คํธ ๋ฌธ์ , ๋ ธ๋๊ฐ ๊ฐ์ง๊ณ ์๋ next๋ ธ๋์ ๋ฐ๋ณตํด์ ์ ๊ทผํ๋ฉฐ ์ํํ๋ค.head = ์ ๋ต๋ ธ๋/current = ํ์ฌ ํ์์ค์ธ ๋ ธ๋