์ฐจ๋ ๋ด์ญ์ด ๋ด๊ธด ๋ฐฐ์ด(records) ์ํํ๋ฉด์ treeMap์ ๊ฐ ์ฐจ๋๋ฒํธ์ ๋์ ์๊ฐ ๋ด๊ธฐ=> ์๊ฐ์ ๋ถ๋จ์๋ก ๊ณ์ฐ ํ, IN์ผ ๊ฒฝ์ฐ๋ ๋ํ๊ธฐ, OUT์ผ ๊ฒฝ์ฐ๋ ๋นผ๊ธฐtreeMap์ ์ ์ฅ๋ ๋์ ์๊ฐ์ ๋ฐ๋ผ ์๊ธ ๊ณ์ฐํ๊ธฐ=> ๋์ ์๊ฐ์ด ์์์ด๋ฉด OUT์ด ์๋ ์ฐจ๋
k์ง์๋ก ๋ณํํ ๋ ๋๋ ๋๋จธ์ง๋ฅผ StringBuilder์ ์ ์ฅํ๊ณ ๋ง์ง๋ง์ ๋ฌธ์์ด์ ๋ค์ง์ด์ ์ง์๋ก ๋ณํ์ง์๋ก ๋ฐ๊พผ ์ซ์๋ฅผ 0์ ๊ธฐ์ค์ผ๋ก ๋ถ๋ฆฌ๋ถ๋ฆฌํด์ ๊ฐ ์ซ์๊ฐ ์์์ธ์ง ํ๋ณ๐จ ์ฃผ์ -> ์๊ฐ์ด๊ณผ ๋ฐ์long ์๋ฃํ ํ์ -> n์ ์ต๋๊ฐ์ธ 1,000,000์ 2
cntMap : ์ ์ ๋ณ ์ ๊ณ ๋นํ ํ์ ์นด์ดํธidMap : ์ ์ ๋ณ ์ ๊ณ ํ ID ๋ฆฌ์คํธ๋ก ๋ฃ๊ธฐreportSet : report ์ค๋ณต ์ ๊ฑฐcntMap์ value๋ฅผ ํ์ธํ๋ฉด์ k ์ด์ ์ ๊ณ ๋นํ ์ ์ ๋ฅผ ๋ฆฌ์คํธ์ ๋ฃ๊ธฐidMap์ ๋๋ฉด์ ์ ์ ๊ฐ ์ ๊ณ ํ ID ๋ฆฌ์คํธ ์ค์ ์ ์ง๋น
์นดํ ๊ณ ๋ฆฌ๋ก ๊ทธ๋ฃนํ ํ์ MAX ์ง๊ณํจ์๋ก ๋น์ผ ์ํ ๋์ค๊ฒ ํ์๐ซฅ ๋ถ๋ช ํ ๋ง๋๋ฐ.. ์๊พธ ํ๋ ค์ ํค๋งค๋ค๊ฐ \-> group by์ ์๋ ์ปฌ๋ผ์ด๊ณ ์ง๊ณํจ์๋ ์๋ ์ปฌ๋ผ์ select์ ์ฌ์ฉํด์ ์ํ ์ด๋ฆ์ด ์ ํํ ๋งคํ๋์ง ์์ => ์๋ธ์ฟผ๋ฆฌ ํ์์๋ธ์ฟผ๋ฆฌ๋ฅผ ํตํด ๊ทธ๋ฃนํํด
๊ฐ ๋ฐฐ์ด์ ๊ฐ๊ฐ ํ์ ๋ฃ๊ณ , ํฉ๊ณ๋ ๊ตฌํ๊ธฐqueue1์ ํฉ์ด queue2์ ํฉ๋ณด๋ค ๋ ์์ผ๋ฉด queue2์์ ๊บผ๋ด์ queue1์ ๋ฃ๊ธฐ๋ฐ๋๋ก queue2๋ ๋ ์์ผ๋ฉด queue1 ์์ ๋ฃ๊ธฐํ์์ ๋ฃ์๋ ํด๋น ํ์ ์์๊ฐ ํ๋๋ฐ์ ์์ผ๋ฉด ๊ฐ์ ํฉ์ ๋ชป ๋ง๋๋ฏ๋ก -1 ๋ฆฌํด
String ๋ ์ง๋ฅผ ์ผ์๋ก ๋ณ๊ฒฝํด์ฃผ๋ ํจ์ => toDays์ฝ๊ด ์ข ๋ฅ์ ์ ํจ๊ธฐ๊ฐ Map์ ๋ด๊ธฐprivacies ํ๋์ฉ ํ์ธํ๋ฉด์ ๊ฐ์ธ์ ๋ณด ์์ง ์ผ์ + ์ ํจ๊ธฐ๊ฐ ์ผ์ ๊ตฌํ๊ธฐ์ค๋ ๋ ์ง ์ผ์์ ๋น๊ตํด์ ์ค๋ ๋ ์ง๊ฐ ๋ ํฌ๋ฉด ๋ง๋ฃ๊ธฐ๊ฐ์ด ์ง๋ฌ์ผ๋ฏ๋ก ์ ๋ต ๋ฆฌ์คํธ์ ๋ด๊ธฐโญ "20
place ๋ฐฐ์ด ๋๋ฉด์ ์์์(P) ํ์ธ ํ List์ ๋ฃ๊ธฐ, 2์ฐจ์ ๋ฐฐ์ด์ ์์์, ํ ์ด๋ธ, ํํฐ์ ์ ๋ณด ๋ฃ๊ธฐ์์์ ๋ฆฌ์คํธ์ 2์ค for๋ฌธ์ผ๋ก ๋๋ช ์ฉ ํ์ธํ๊ธฐ => isCheck๋ ์์์์ ๋งจํดํผ ๊ฑฐ๋ฆฌ๊ฐ 1์ด๋ฉด ๋ฌด์กฐ๊ฑด false 2์ด๋ฉด ๋ ์์์ ๊ฑฐ๋ฆฌ๊ฐ ์ง์ ์ธ ๊ฒฝ์ฐ
โ๏ธ 2์ค for๋ฌธ๋ณด์ ์ข ๋ฅ ์ ์ธ๊ธฐ ์ํด์ Set์ ๋ฃ๊ณ ํฌ๊ธฐ ๊ตฌํ๊ธฐ๋ณด์ ์ฒซ๋ฒ์งธ ๋ถํฐ 2์ค for๋ฌธ ๋๋ฉด์ ์๋ก์ด set์ ๋ฃ๊ณ ํ์ฌ ํ์ธ ์ค์ธ set ํฌ๊ธฐ๋ ๋ณด์ ์ข ๋ฅ ์ ๊ฐ๊ณ , ๊ตฌ๊ฐ์ด ์งง์ผ๋ฉด answer ๋ฐฐ์ด์ ๋ฃ๊ธฐ๐ ๋ญ์ผ ์ฝ๋ค???? ํ์ง๋ง ํจ์จ์ฑ์์ ์คํจโ๏ธ
a, b ์ ์ ์ ๋ฌด์กฐ๊ฑด ๊ฑฐ์ณ์ผ ํ๋ฏ๋ก 2๊ฐ์ง๋ก ๋๋ ์ ์๊ฐ1) 1 -> a -> b -> n 2) 1 -> b -> a -> n๊ทธ๋ฆฌ๊ณ ๊ฐ๊ฐ ๋ค์ต์คํธ๋ผ ์คํ (1์์ a, a์์ b, b์์ n)์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ Integer.MAX_VALUE๋ก ์ค์ ํ๋ค๊ฐ ์ค๋ฒํ๋ก์ฐ
Dijkstra ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ํน์ ๋ ธ๋์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋ ธ๋๋ก ๊ฐ๋ ๊ฐ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋์๊ณ ๋ฆฌ์ฆ ์๊ฐ๋ณต์ก๋ : O(E logN) (N : ๋ ธ๋ ์, E : ๊ฐ์ ์) ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ์์์ธ ๊ฒฝ์ฐ๋ง ๊ฐ๋ฅ (์์์ธ ๊ฒฝ์ฐ ํ๋ก์ด๋์์ ์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉ) ๊ทธ๋ฆฌ๋ ์
์งํฉ ๋ด๋ถ์ ๊ฐ์ด ์กด์ฌํ๋์ง ์ฌ๋ถIN ์ฟผ๋ฆฌ -> ๋ฉ์ธ ์ฟผ๋ฆฌ์์๋ก ์งํ ์์ STUDENT ํ ์ด๋ธ์กฐ๊ฑด์ด๋ ์๋ธ์ฟผ๋ฆฌ์ ์ผ์นํ์ง ์๋ ๊ฐ์ ๋ฐํโญ ์กฐ๊ฑด์ null์ด ์กด์ฌํ๊ฒ ๋๋ฉด no rows selected๋ก UNKNOWN(=false) ๊ฐ์ด ๋ฐํ๋๋ฏ๋ก ๋ฌด์กฐ๊ฑด null ์ฒ
Group by
ํด๋น ์นธ์ด 0์ด ์๋๋ฉด \-stack์ด ๋น์ด ์์ง ์๊ณ ๋งจ ์์ ์ธํ๊ณผ ๊ฐ์ผ๋ฉด pop ํ +2 \-๋งจ ์์ ์ธํ๊ณผ ๋ค๋ฅด๋ฉด ์ถ๊ฐ add ์ธํ์ ๋ฝ๊ณ 0์ผ๋ก ๋ฆฌ์ ํ ํด๋น ์์น๋ ๋ค ๋ฝ์์ผ๋ฏ๋ก break(๐ ์ฒ์์ break ๊น๋นกํด์ ํค๋งธ์)
์์ด ์๊ณ ๋ฆฌ์ฆ์ผ๋ก id๋ค ์ค ๋ถ๋ id ์๋๋ก ๋ฝ์๋ฝ์ id๋ฅผ ๋ถ๋ id์ ๋งค์นญ์ผ์นํ๋ฉด treeSet์ ๋ด์์ ์ ๋ ฌํ๋ฉด์ set์ผ๋ก ์ ์ฅ๋ฝ์ id๊ฐ ๋ถ๋ id์ ๋ง๋ค๋ฉด treeSet์ ์ฌ์ด์ฆ๊ฐ ๋ถ๋ id ์์ ๊ฐ์์ผํจ๊ฐ์ผ๋ฉด hashSet์ธ answerSet์ treeS
๋ฐ๊นฅ ์ค๊ดํธ ๋๊ฐ ์ ๊ฑฐ ํ "},{" ๊ธฐ์ค์ผ๋ก split\-> substring ์ฌ์ฉ\-> }์ {์ ์ ๊ทํํ์ ์ฌ์ฉ=> ex. {{1,2},{1,2,3}} -> 1,2 / 1,2,3๋ถ๋ฆฌ๋ ํํ ๋ฐฐ์ด์์ ํํ ๊ธธ์ด ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํํ ๋ฐฐ์ด ํ๋์ฉ "," ๊ธฐ์ค์ผ๋ก
parent ํด์๋งต์ ํ๋งค์๊ณผ ์ถ์ฒ์ธ ๋ฃ๊ธฐseller๊ณผ amount ๋ฐฐ์ด ํ๋์ฉ ๊ณ์ฐ ํจ์ ์คํ (calculate)ํด๋น ํ๋งค์์ money ํด์์ ์ด์ต ๊ณ์ฐํด์ ๋ฃ๊ธฐparent ํด์์์ ๊ทธ ํ๋งค์์ ์ถ์ฒ์ธ ์ฐพ์์(containsKey) ์ฌ๊ท๋ก 10% ๊ณ์ฐ ์คํ
๐ซฅ ๋ฌธ์ ๊ฐ ์ด๋ ค์์ ๋ค๋ฅธ ์ฌ๋ ํ์ด ์ฐธ๊ณ ํ๋๋ฐ ์๊ฐ๋ณด๋ค ์ฌ์ ๋ ๋ฌธ์ ์์ฑ๋ ์ ์ ๊ณผ ๊ฐ ๊ทธ๋ํ์ ํน์ง์ ์ฐพ์ผ๋ฉด ๋๋ ๋ฌธ์ ์์ฑ๋ ์ ์ : in์ ๋ฌด์กฐ๊ฑด 0, out์ 2๊ฐ ์ด์๋ง๋ ๋ชจ์ ๊ทธ๋ํ : out์ด 0์ธ ์ ์ ์ด ์์ (๋ง์ง๋ง ์ ์ )8์ ๋ชจ์ ๊ทธ๋ํ : out์ด 2๊ฐ
๋์ ์ ์ ํ๋์ฉ ๊ณ ๋ฅด๊ณ ๊ทธ ์ ์ ์ ์ธํ๊ณ ์ธ์ ๋ฆฌ์คํธ ์์ฑ(createList)์์ฑ ํ ์ธ์ ๋ฆฌ์คํธ์ ์ ์ ์ ๋ณด ๋ฃ๊ธฐ -> bfs ์คํbfs ์คํํด์ ๋ ธ๋ ์ countํ๊ณ ๋ ์ ๋ ฅ๋ง์ ์ก์ ํ ๊ฐ์ ์ฐจ์ด๋ฅผ ๋ฐํ๊ฐ์ฅ ์์ ์ฐจ์ด๊ฐ ์ ๋ต
์กฐํฉ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๋น์นธ ์ค ๋ฒฝ ์ธ์ธ ๊ณณ 3๊ตฐ๋ฐ ๊ตฌํ๊ธฐ๋น์นธ 3๊ณณ์ ๊ณจ๋์ผ๋ฉด bfs ์คํ๋์ค์ arr ์์๋ณต๊ตฌ ์ํค๊ธฐ ์ํด ๋ฐ์ด๋ฌ์ค ๊ฐ์ผ๋ ๊ณณ์ ๋ฐ๋ก ์ขํ ๋ณด๊ด(newVirus)๋น์นธ ์ count๋ฐ์ด๋ฌ์ค ์๋กญ๊ฒ ๊ฐ์ผ๋ ๊ณณ ๋ค์ ๋น์นธ์ผ๋ก ๋ณต๊ตฌ
์๋ฅ ์์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์๋งจ ์์ ์๋ ์ฌ๋์ ๋ฌด์กฐ๊ฑด ์ฑ์ฉ๋๋ฒ์งธ ์ฌ๋๋ถํฐ ๋ฉด์ ์์๊ฐ ์์ฌ๋๋ค๋ณด๋ค ๋์์ง ํ์ธ๋ฉด์ ์์ ํ์ธํ๋ ์ฝ๋์์ ์ด์ค for๋ฌธ์ผ๋ก ์๊ฐ์ด๊ณผ์์ ์ฌ๋๋ค์ ํ๋์ฉ ํ์ธํ๋๊ฒ ์๋๋ผ ์ ์ฌ๋๋ค ์ค ๋์ ์์๋ฅผ ๊ณ์ ๊ฐฑ์ ํ๊ณ ๊ทธ๊ฑธ ๊ธฐ์ค์ผ๋ก ํ์ธ