๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1966
- ์๋ก์ด ํ๋ฆฐํฐ๊ธฐ ๋ด๋ถ ์ํํธ์จ์ด๋ฅผ ๊ฐ๋ฐํ์๋๋ฐ, ์ด ํ๋ฆฐํฐ๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ฐ๋ผ ์ธ์๋ฅผ ํ๊ฒ ๋๋ค.
- ํ์ฌ Queue์ ๊ฐ์ฅ ์์ ์๋ ๋ฌธ์์ ‘์ค์๋’๋ฅผ ํ์ธํ๋ค.
- ๋๋จธ์ง ๋ฌธ์๋ค ์ค ํ์ฌ ๋ฌธ์๋ณด๋ค ์ค์๋๊ฐ ๋์ ๋ฌธ์๊ฐ ํ๋๋ผ๋ ์๋ค๋ฉด, ์ด ๋ฌธ์๋ฅผ ์ธ์ํ์ง ์๊ณ Queue์ ๊ฐ์ฅ ๋ค์ ์ฌ๋ฐฐ์น ํ๋ค. ๊ทธ๋ ์ง ์๋ค๋ฉด ๋ฐ๋ก ์ธ์๋ฅผ ํ๋ค.
- ์๋ฅผ ๋ค์ด Queue์ 4๊ฐ์ ๋ฌธ์(A B C D)๊ฐ ์๊ณ , ์ค์๋๊ฐ 2 1 4 3 ๋ผ๋ฉด C๋ฅผ ์ธ์ํ๊ณ , ๋ค์์ผ๋ก D๋ฅผ ์ธ์ํ๊ณ A, B๋ฅผ ์ธ์ํ๊ฒ ๋๋ค.
- ์ฌ๋ฌ๋ถ์ด ํ ์ผ์, ํ์ฌ Queue์ ์๋ ๋ฌธ์์ ์์ ์ค์๋๊ฐ ์ฃผ์ด์ก์ ๋, ์ด๋ค ํ ๋ฌธ์๊ฐ ๋ช ๋ฒ์งธ๋ก ์ธ์๋๋์ง ์์๋ด๋ ๊ฒ์ด๋ค. ์๋ฅผ ๋ค์ด ์์ ์์์ C๋ฌธ์๋ 1๋ฒ์งธ๋ก, A๋ฌธ์๋ 3๋ฒ์งธ๋ก ์ธ์๋๊ฒ ๋๋ค.
- ์ฒซ ์ค์ ํ ์คํธ์ผ์ด์ค์ ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ์ผ์ด์ค๋ ๋ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
- ํ ์คํธ์ผ์ด์ค์ ์ฒซ ๋ฒ์งธ ์ค์๋ ๋ฌธ์์ ๊ฐ์ N(1 ≤ N ≤ 100)๊ณผ, ๋ช ๋ฒ์งธ๋ก ์ธ์๋์๋์ง ๊ถ๊ธํ ๋ฌธ์๊ฐ ํ์ฌ Queue์์ ๋ช ๋ฒ์งธ์ ๋์ฌ ์๋์ง๋ฅผ ๋ํ๋ด๋ ์ ์ M(0 ≤ M < N)์ด ์ฃผ์ด์ง๋ค.
- ์ด๋ ๋งจ ์ผ์ชฝ์ 0๋ฒ์งธ๋ผ๊ณ ํ์. ๋ ๋ฒ์งธ ์ค์๋ N๊ฐ ๋ฌธ์์ ์ค์๋๊ฐ ์ฐจ๋ก๋๋ก ์ฃผ์ด์ง๋ค. ์ค์๋๋ 1 ์ด์ 9 ์ดํ์ ์ ์์ด๊ณ , ์ค์๋๊ฐ ๊ฐ์ ๋ฌธ์๊ฐ ์ฌ๋ฌ ๊ฐ ์์ ์๋ ์๋ค.
- ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด ๋ฌธ์๊ฐ ๋ช ๋ฒ์งธ๋ก ์ธ์๋๋์ง ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- LinkedList์ ๋ค์ด์ค๋ ์๋ฒ๊ณผ ๋ค์ด์จ ์ฐ์ ์์ ์ซ์๋ฅผ int ๋ฐฐ์ด๋ก ์ ์ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ While๋ฌธ์ ๋๋ฆฌ๋ฉด์ ์ ์ผ ์์ ์๋ ๋ฐฐ์ด์ ๊บผ๋ด์ ํด๋น ๋ฐฐ์ด์ ์ ์ฅ๋ ์ฐ์ ์์๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ์ฒด ๋ฐฐ์ด์์ ๋ ๋์ ์ฐ์ ์์๊ฐ ์๋์ง ์ฐพ๋๋ค.
- ๋ง์ฝ ๋ ๋์ ์ฐ์ ์์๊ฐ ์๋ค๋ฉด ๋งจ ์์ ์๋ ๊ฒ์ ๋นผ๋ด์ ๋ค์ LinkedList์ ๋ฃ๊ณ ํด๋น ์ฐ์ ์์๊ฐ ์๋ ์์ ๋ฐฐ์ด๋ค๋ ๋ชจ๋ ๋นผ์ ๋ค์ ๋ฃ๋๋ค.
- ๊ทธ๋ฆฌ๊ณ ๋ ๋์๊ฒ ์๋์ง๋ฅผ ํ๋ณํ๋ ๋ณ์๋ฅผ true๋ก ๋ฐ๊พธ๊ณ ๋ฐ๋ณต๋ฌธ์ ์ข ๋ฃํ๋ค.
- ๋ง์ฝ ๋ ๋์๊ฒ ์๋ค๋ฉด, ํด๋น ๋งจ ์์ ๋ฐฐ์ด์ ๋นผ๋ด๊ณ ์ถ๋ ฅ ํ์์ 1์ ๋ํด์ค๋ค.
- ๊ทธ๋ฆฌ๊ณ ๋ง์ฝ ๋งจ ์์ ๋ฐฐ์ด ์๋ฒ์ด ์ถ๋ ฅ์์๋ฅผ ์์์ผ๋๋ ๋ฌธ์ ์๋ฒ๊ณผ ๊ฐ๋ค๋ฉด ํด๋น ์ถ๋ ฅ ์์๋ฅผ ์ถ๋ ฅ ํ While๋ฌธ์ ์ข ๋ฃํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฒ์์๋ ์ฝ๋๊ฐ ๋๋ฌด ๋ณต์กํ์๋ค... stack์ hashmap, deque ๋ฑ๋ฑ ์ต๋ํ ๋ฐ๋ณต๋ฌธ์ ๋๋ฆฌ์ง ์๊ณ ์ต๋๊ฐ์ ๋ฐ๋ก๋ฐ๋ก ์ฐพ์์ ์๊ฐ์ด๋ฅผ ์ค์ด๋ ์ฝ๋๋ฅผ ์ง๊ณ ์ถ์ ์๊ฐ์ ์ฝ๋๊ฐ ๋๋ฌ์์ก๋ ๊ฒ ๊ฐ๋ค ใ ใ (์๊ฐ๋ ์ค๋๊ฑธ๋ ธ๋ค....)
- for๋ฌธ์ ๋๋ ค๋ ์๊ฐ์ด ๊ทธ๋ ๊ฒ ์ค๋ ๊ฑธ๋ฆฌ์ง ์์ผ๋ (๋ฌผ๋ก ๊ณผํ๋ฉด ์๋๋ค..!) ๋ฌธ์ ํด๊ฒฐ์ ์ฐ์ ์ผ๋ก ์๊ฐํ๊ณ ์๊ฐ์ด๋ฅผ ์ค์ฌ๋ณด์...!
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ1966 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int test = 0; test < T; test++){
StringTokenizer st = new StringTokenizer(br.readLine());
// ๋ฌธ์์ ๊ฐ์
int N = Integer.parseInt(st.nextToken());
// ๋ช๋ฒ์งธ ๋ฌธ์์ ์ถ๋ ฅ ์์น๋ฅผ ์๊ณ ์ถ์์ง
int M = Integer.parseInt(st.nextToken());
// ๋ช๋ฒ์งธ์ธ์ง, ์ฐ์ ์์๊ฐ ์ผ๋ง์ธ์ง ์ ์ฅํ ๋ฐฐ์ด
LinkedList<int[]> q = new LinkedList<>();
StringTokenizer st2 = new StringTokenizer(br.readLine());
// ์ซ์๋ฅผ ์
๋ ฅ๋ฐ์์ ๋ฐฐ์ด๊ณผ stack์ ๋ฃ์
for(int i = 0; i < N; i++){
int n = Integer.parseInt(st2.nextToken());
// M๋ฒ์งธ ๋ฌธ์์ ์ค์๋๊ฐ ๋ญ์ง ์ ์ฅ
q.add(new int[]{i, n});
}
// ์ถ๋ ฅ์ด ๋ช๋ฒ์งธ์ธ์ง ์ ์ฅํ ๋ณ์
int cnt = 0;
while(true){
// ๋งจ ์์ ์ซ์๊ฐ ์ถ๋ ฅ ์ซ์ ์ถ๋ ฅํ๊ธฐ ์ํด์
int top[] = q.poll();
// ๋ ๋์ ์ฐ์ ์์๊ฐ ์๋์ง ํ๋ณํ ๋ณ์
boolean isHigher = false;
// q์ ํฌ๊ธฐ๋งํผ ๋ฐ๋ณต
for(int i = 0; i < q.size(); i++){
// ๋ง์ฝ ๋งจ ์์ ์๋ ๋ฌธ์์ ์ฐ์ ์์๋ณด๋ค
// ๋ค๋ฅธ ๋ฌธ์์ ์ฐ์ ์์๊ฐ ๋ ๋๋ค๋ฉด
if(q.get(i)[1] > top[1]){
// ๋งจ ์์ ๋นผ๋ธ ๊ฐ์ ๋ค์ ํ์ ๋ฃ์
q.add(top);
// ๋งจ ์์ ์๋ ๊ฒ์ ๋ค์ ํ์ ๋ฃ๊ณ
// i๋ฒ์งธ๊ฐ ๋งจ ์์ ์๋ ๊ฒ๋ณด๋ค ์ฐ์ ์์๊ฐ ๋ ๋์ผ๋ฏ๋ก
// i๋ฒ์งธ๊น์ง ๋ชจ๋ ๊บผ๋ด์ ๋ค์ ๋ค๋ก ๋ฃ์
for(int j = 0; j < i; j++){
q.add(q.poll());
}
// ๋ ๋์ ๊ฒ์ด ์์ผ๋ฏ๋ก true๋ก ๋ณํ ํ, ์ข
๋ฃ
isHigher = true;
break;
}
}
// ๋ง์ฝ ๋ ๋์ ๊ฐ์ด ์๋ค๋ฉด
if(!isHigher){
// ์ถ๋ ฅ + 1
cnt = cnt + 1;
// ๋ง์ฝ ๋งจ์์ ์๋ ๋ฌธ์์ ๋ฒํธ์ ์ถ๋ ฅ์์๋ฅผ ์์์ผํ๋
// ๋ฌธ์์ ๋ฒํธ๊ฐ ๊ฐ๋ค๋ฉด
if(top[0] == M){
// ์ถ๋ ฅ ์์ ์ถ๋ ฅ ํ, ์ข
๋ฃ
sb.append(cnt + "\n");
break;
}
}
}
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 1654 ๋์ ์๋ฅด๊ธฐ (10) | 2024.07.22 |
---|---|
[Java] BOJ 2108 ํต๊ณํ (2) | 2024.07.22 |
[Java] BOJ 1929 ์์ ๊ตฌํ๊ธฐ (0) | 2024.07.21 |
[Java] BOJ 18110 solved.ac (2) | 2024.07.21 |
[Java] BOJ 10845 ํ (4) | 2024.07.20 |