๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

BOJ 17641

[Java] BOJ 1764 ๋“ฃ๋ณด์žก ๋ฌธ์ œ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/1764๊น€์ง„์˜์ด ๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ๊ณผ, ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ์ด ์ฃผ์–ด์งˆ ๋•Œ, ๋“ฃ๋„ ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.์ฒซ์งธ ์ค„์— ๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ˆ˜ N, ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค.์ด์–ด์„œ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ด๋ฆ„๊ณผ, N+2์งธ ์ค„๋ถ€ํ„ฐ ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ์ด๋ฆ„์ด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ด๋ฆ„์€ ๋„์–ด์“ฐ๊ธฐ ์—†์ด ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ง€๋ฉฐ, ๊ทธ ๊ธธ์ด๋Š” 20 ์ดํ•˜์ด๋‹ค. N, M์€ 500,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ์—๋Š” ์ค‘๋ณต๋˜๋Š” ์ด๋ฆ„์ด ์—†์œผ๋ฉฐ, ๋ณด๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์˜ ๋ช…๋‹จ๋„ ๋งˆ์ฐฌ๊ฐ€์ง€์ด๋‹ค.๋“ฃ๋ณด์žก์˜ ์ˆ˜์™€ ๊ทธ ๋ช…๋‹จ์„ ์‚ฌ์ „์ˆœ์œผ๋กœ ์ถœ๋ ฅํ•œ๋‹ค.์•„์ด๋””์–ด๋“ฃ๋„ ๋ชปํ•œ ์‚ฌ๋žŒ์ด๋ฆ„์„ hashmap์— .. 2024. 7. 23.