๐ ๊ธฐ์ง๊ตญ ์ค์น
๐ ๋ฌธ์
N๊ฐ์ ์ํํธ๊ฐ ์ผ๋ ฌ๋ก ์ญ ๋์ด์ ์์ต๋๋ค. ์ด ์ค์์ ์ผ๋ถ ์ํํธ ์ฅ์์๋ 4g ๊ธฐ์ง๊ตญ์ด ์ค์น๋์ด ์์ต๋๋ค. ๊ธฐ์ ์ด ๋ฐ์ ํด 5g ์์๊ฐ ๋์์ ธ 4g ๊ธฐ์ง๊ตญ์ 5g ๊ธฐ์ง๊ตญ์ผ๋ก ๋ฐ๊พธ๋ ค ํฉ๋๋ค. ๊ทธ๋ฐ๋ฐ 5g ๊ธฐ์ง๊ตญ์ 4g ๊ธฐ์ง๊ตญ๋ณด๋ค ์ ๋ฌ ๋ฒ์๊ฐ ์ข์, 4g ๊ธฐ์ง๊ตญ์ 5g ๊ธฐ์ง๊ตญ์ผ๋ก ๋ฐ๊พธ๋ฉด ์ด๋ค ์ํํธ์๋ ์ ํ๊ฐ ๋๋ฌํ์ง ์์ต๋๋ค.
์๋ฅผ ๋ค์ด 11๊ฐ์ ์ํํธ๊ฐ ์ญ ๋์ด์ ์๊ณ , [4, 11] ๋ฒ์งธ ์ํํธ ์ฅ์์๋ 4g ๊ธฐ์ง๊ตญ์ด ์ค์น๋์ด ์์ต๋๋ค. ๋ง์ฝ ์ด 4g ๊ธฐ์ง๊ตญ์ด ์ ํ ๋๋ฌ ๊ฑฐ๋ฆฌ๊ฐ 1์ธ 5g ๊ธฐ์ง๊ตญ์ผ๋ก ๋ฐ๋ ๊ฒฝ์ฐ ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ ์ ์์ต๋๋ค. (์ ํ์ ๋๋ฌ ๊ฑฐ๋ฆฌ๊ฐ W์ผ ๋, ๊ธฐ์ง๊ตญ์ด ์ค์น๋ ์ํํธ๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ํ๋ฅผ ์์ชฝ์ผ๋ก W๋งํผ ์ ๋ฌํ ์ ์์ต๋๋ค.)

์ด๋, ์ฐ๋ฆฌ๋ 5g ๊ธฐ์ง๊ตญ์ ์ต์๋ก ์ค์นํ๋ฉด์ ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ๋ ค๊ณ ํฉ๋๋ค. ์์ ์์์์ ์ต์ 3๊ฐ์ ์ํํธ ์ฅ์์ ๊ธฐ์ง๊ตญ์ ์ค์นํด์ผ ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ ์ ์์ต๋๋ค.
์ํํธ์ ๊ฐ์ N, ํ์ฌ ๊ธฐ์ง๊ตญ์ด ์ค์น๋ ์ํํธ์ ๋ฒํธ๊ฐ ๋ด๊ธด 1์ฐจ์ ๋ฐฐ์ด stations, ์ ํ์ ๋๋ฌ ๊ฑฐ๋ฆฌ W๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ๊ธฐ ์ํด ์ฆ์คํด์ผ ํ ๊ธฐ์ง๊ตญ ๊ฐ์์ ์ต์๊ฐ์ ๋ฆฌํดํ๋ solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์
๐ซ ์ ํ ์ฌํญ
N: 200,000,000 ์ดํ์ ์์ฐ์
stations์ ํฌ๊ธฐ: 10,000 ์ดํ์ ์์ฐ์
stations๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด ์๊ณ , ๋ฐฐ์ด์ ๋ด๊ธด ์๋ N๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ์์ฐ์์ ๋๋ค.
W: 10,000 ์ดํ์ ์์ฐ์
๐ ์ ์ถ๋ ฅ ์

๐ค ํ์ด ๋ฐฉ๋ฒ
์์ ์์น๋ถํฐ ๋๊น์ง ์ํํ๋ฉฐ ์ ํ ๋ฒ์๋ฅผ ํ์ธํ๋ค.
1๏ธโฃ ์ ํ ๋ฒ์ ๋ด์ ์๋ ๊ฒฝ์ฐ โก๏ธ ์ ํ ๋ฒ์์ ๋ ๋ค์์ผ๋ก ์ด๋ํ๋ค.
2๏ธโฃ ์ ํ ๋ฒ์ ๋ฐ์ ์๋ ๊ฒฝ์ฐ โก๏ธ ํ์ฌ ์์น๊ฐ ์ ํ ๋ฒ์ ๋์ ์์นํ๋๋ก ๊ธฐ์ง๊ตญ์ ์ธ์ฐ๊ณ ๋ฐ๋ํธ ๋ ๋ค์์ผ๋ก ์ด๋ํ๋ค.
์ด๋ ๊ฒ ํ๋ฉด ํน์ ์์น์ ์์ ๋ ๊ทธ ์ ์์น๋ค์ ๋ชจ๋ ์ ํ ๋ฒ์ ๋ด์ ์๋ ๊ฒ์ ๋ณด์ฅํ ์ ์๋ค. ์ด๋ฐ ์์ผ๋ก ์ผ๋จ ํ์ฌ ์ํฉ์ ์ต์ ์ฑ ์ ์ ํํ๋ ๋ฐฉ์์ Greedy ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ณ ํ๋ค.
๐ป ํ์ด ์ฝ๋
๋ฐฉ๋ฒ โ : Queue ๋ฅผ ์ด์ฉํ ํ์ด
public class ๊ธฐ์ง๊ตญ_์ค์น {
public static void main(String[] args) {
// ์ด๊ธฐ๊ฐ ์ธํ
int N = 11;
int[] stations = {4, 11};
int W = 1;
// ํ์ด ์์
int answer = 0;
Queue<Integer> sq = new LinkedList<>();
for (int s : stations) sq.offer(s); // Queue ์ ๊ฐ ์ถ๊ฐ => [4, 11]
int position = 1;
while (position <= N) {
if (!sq.isEmpty() && position >= sq.peek()-W) {
// ํ์ฌ ์์น๊ฐ ๊ธฐ์ง๊ตญ์ ๋ฒํ ์ ํ ๋ฒ์ ์์ ์๋ ๊ฒฝ์ฐ
position = sq.poll() + W + 1; // poll : ๋งจ ์์ ๊ฐ ๋ฐํ ํ ์ญ์
} else {
answer++; // ํ์ฌ ์์น ๊ธฐ์ค ์ ํ๋ฒ์ ์ต๋ ๊ฑฐ๋ฆฌ์ ๊ธฐ์ง๊ตญ ์ธ์
position += 2*W + 1; // ์ด๋
}
}
}
}
โก๏ธ ๋ ์ค์ผ ์ ์๋ ๋ฐฉ๋ฒ์ด ์๋์ง ์๊ฐํด๋ณด์!
1๏ธโฃ Loop ๋ฅผ ๊ฐ์ํํ๋ค? โก๏ธ ์ด๋ฏธ ๋จ์ผ loop ์ด๊ณ ๊ฑด๋๋ฐ๋ฉด์ ์ด๋์ค์ด๋ฏ๋ก ๋์ด์ ์ค์ผ ์ ์๋ค.
2๏ธโฃ Object type (์ฐธ์กฐ๋ฐฉ์) ์ธ Queue ๋์ primitive type ์ ์ฌ์ฉํ ์ ์์๊น? โก๏ธ ์ฃผ์ด์ง ๋ฐฐ์ด์ index ์ ๊ทผ ๋ฐฉ์์ผ๋ก ์ฌ์ฉํด๋ณด์!
๋ฐฉ๋ฒ โก : Queue ์์ด
public class ๊ธฐ์ง๊ตญ_์ค์น {
public static void main(String[] args) {
// ์ด๊ธฐ๊ฐ ์ธํ
int N = 11;
int[] stations = {4, 11};
int W = 1;
// ํ์ด ์์
int answer = 0;
int si = 0; // station ๋ฐฐ์ด์ index
int position = 1;
while (position <= N) {
if (si < stations.length && position >= stations[si]-W) { // ์ฃผ์ด์ง ๋ฐฐ์ด๊ณผ primitive type ์ธ si ๋ฅผ ์ฌ์ฉ
position = stations[si] + W + 1;
si++;
} else {
answer++;
position += 2*W + 1;
}
}
System.out.println(answer);
}
}
'Algorithm ๐ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| ์ด๋ถ ํ์ ๐ (Binary Search) (0) | 2023.04.17 |
|---|---|
| ๊ทธ๋ํ๐ (Graph) (0) | 2023.03.21 |
| ๋์ ๊ณํ๋ฒ๐๏ธ (Dynamic Programming) (0) | 2023.03.13 |
| ๊น์ด ์ฐ์ ํ์ (DFS) & ๋๋น ์ฐ์ ํ์ (BFS ) (0) | 2023.01.15 |
| [๐จ ์ปค๋ฎค๋ฌ๋/7๊ธฐ/Java] ] ๊ฐ์ฅ ํฐ ์ (Bubble Sort) (0) | 2022.11.02 |