๋ฐ์ํ
https://www.acmicpc.net/problem/1966
๋ฌธ์ ํ์ด
//์ค์๋์ ํด๋นํ๋ ๋ฌธ์๋ฅผ ์ง์ฐ๊ธฐ ์ ๊น์ง๋ ๋ฃจํ๋๊ธฐ
์ด๋ถ๋ถ์ ์ฒ์์ importmant++๋ก ๋์์ ๋ ํ
์คํธ์ผ์ด์ค๊ฐ ์ ๋์๋์ด์ ์ ์ถํ๋๋ฐ
๋ฐํ์ ์๋ฌ (ArrayIndexOutOfBounds) ๊ฐ ๋ฐ์ํ๋ค
๋๋ฒ๊ทธํด๋ณด๋ 9๊น์ง์ธ ์ค์๋๊ฐ 10, 11 ๋ก ์ฌ๋ผ๊ฐ๊ณ ์์๋ค
count++๋ก ๊ณ ์น๋ ์ ๋์๊ฐ๋ค!
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.Stack;
public class Main1966 {
/*
3 //ํ
์คํธ์ผ์ด์ค์ ์
1 0 //๋ฌธ์์๊ฐ์, ์ถ๋ ฅ์์๊ฐ ๊ถ๊ธํ ๋ฌธ์๋ ํ์ฌ ํ์ 0๋ฒ์งธ์ ์๋ค (=5๋ฒ๋ฌธ์)
5 //๋ฌธ์์ ์ค์๋
//๊ฒฐ๊ณผ : 5๋ฒ์ด 1๋ฒ์งธ๋ก ์ถ๋ ฅ๋์์ผ๋ 1
4 2 //๋ฌธ์์ ๊ฐ์, ์ถ๋ ฅ์์๊ฐ ๊ถ๊ธํ ๋ฌธ์๋ ํ์ฌ ํ์ 2๋ฒ์งธ์ ์๋ค (=3๋ฒ๋ฌธ์)
1 2 3 4 //๋ฌธ์์ ์ค์๋ (์ต๋๊ฐ 4)
//๋ฌธ์ ์ฌ๋ฐฐ์น : 1, 2, 3, 4 -> //3๋ฒ ํ์ฌ index๋ 2. ์ต๋๊ฐ์ด 3์ด ์๋๋ฏ๋ก index--;
2, 3, 4, 1 -> //3๋ฒ ํ์ฌ index๋ 1. ์ต๋๊ฐ์ด 3์ด ์๋๋ฏ๋ก index--;
3, 4, 1, 2 -> //3๋ฒ ํ์ฌ index๋ 0. index๊ฐ 0์ธ๋ฐ ์ต๋๊ฐ์ด 3์ด ์๋๋ฏ๋ก index = queue.size-1;
4, 1, 2, 3 (4 ์ถ๋ ฅ) -> (์ต๋๊ฐ 3) //3๋ฒ ํ์ฌ index๋ 3. ์ต๋๊ฐ์ด 3์ธ๋ฐ index๊ฐ 0์ด ์๋๋ฉด index--;
1, 2, 3 -> //3๋ฒ ํ์ฌ index๋ 2. ์ต๋๊ฐ์ด 3์ธ๋ฐ index๊ฐ 0์ด ์๋๋ฉด index--;
2, 3, 1 -> //3๋ฒ ํ์ฌ index๋ 1. ์ต๋๊ฐ์ด 3์ธ๋ฐ index๊ฐ 0์ด ์๋๋ฉด index--;
3, 1, 2 (3 ์ถ๋ ฅ)... //3๋ฒ ํ์ฌ index๋ 0. ์ต๋๊ฐ์ด 3์ธ๋ฐ index๊ฐ 0์ด๋ฉด result ์ถ๋ ฅ
//๊ฒฐ๊ณผ : 3๋ฒ์ด 2๋ฒ์งธ๋ก ์ถ๋ ฅ๋์์ผ๋ 2
6 0 //๋ฌธ์์ ๊ฐ์, ์ถ๋ ฅ์์๊ฐ ๊ถ๊ธํ ๋ฌธ์๋ ํ์ฌ ํ์ 0๋ฒ์งธ์ ์๋ค (=1-1๋ฌธ์)
1 1 9 1 1 1 //๋ฌธ์์ ์ค์๋ (์ต๋๊ฐ 9) ๊ตฌ๋ถ์ ์ํด ๋ณ๊ฒฝ : 1-1 1-2 9 1-3 1-4 1-5
//๋ฌธ์ ์ฌ๋ฐฐ์น : 1-1 1-2 9 1-3 1-4 1-5 -> //1-1๋ฒ ํ์ฌ index๋ 0. index๊ฐ 0์ธ๋ฐ ์ต๋๊ฐ์ด 1์ด ์๋๋ฏ๋ก index = queue.size-1;
1-2 9 1-3 1-4 1-5 1-1 -> //1-1๋ฒ ํ์ฌ index๋ 5. ์ต๋๊ฐ์ด 1์ด ์๋๋ฏ๋ก index--;
9 1-3 1-4 1-5 1-1 1-2 (9์ถ๋ ฅ) -> (์ต๋๊ฐ 1) //1-1๋ฒ ํ์ฌ index๋ 4. ์ต๋๊ฐ์ด 1์ธ๋ฐ index๊ฐ 0์ด ์๋๋ฉด index--;
1-3 1-4 1-5 1-1 1-2 (1-3์ถ๋ ฅ) -> //1-1๋ฒ ํ์ฌ index๋ 3. ์ต๋๊ฐ์ด 1์ธ๋ฐ index๊ฐ 0์ด ์๋๋ฉด index--;
1-4 1-5 1-1 1-2 (1-4์ถ๋ ฅ) -> //1-1๋ฒ ํ์ฌ index๋ 2. ์ต๋๊ฐ์ด 1์ธ๋ฐ index๊ฐ 0์ด ์๋๋ฉด index--;
1-5 1-1 1-2 (1-5์ถ๋ ฅ) -> //1-1๋ฒ ํ์ฌ index๋ 1. ์ต๋๊ฐ์ด 1์ธ๋ฐ index๊ฐ 0์ด ์๋๋ฉด index--;
1-1 1-2 (1-1์ถ๋ ฅ)... //1-1๋ฒ ํ์ฌ index๋ 0. ์ต๋๊ฐ์ด 1์ธ๋ฐ index๊ฐ 0์ด๋ฉด result ์ถ๋ ฅ
//๊ฒฐ๊ณผ : 1-1๋ฒ์ด 5๋ฒ์งธ๋ก ์ถ๋ ฅ๋์์ผ๋ 5
* */
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int testcaseCount = scanner.nextInt();
//ํ
์คํธ ์ผ์ด์ค ์๋งํผ ๋ฐ๋ณต
for (int i = 0; i < testcaseCount; i++) {
int documentCount = scanner.nextInt();
int targetDocIndex = scanner.nextInt();
Queue<int[]> queue = new LinkedList<>();
//๋ฌธ์ ์์น, ์ค์๋ ๋ฐฐ์ด์ ์ ์ฅ
int[] importantArr = new int[9];
for (int j = 0; j < documentCount; j++) {
int important = scanner.nextInt();
queue.add(new int[]{ j, important });
//์ค์๋ ํ์ ์
๋ ฅ
importantArr[important-1] = importantArr[important-1] + 1;
}
int process = process(importantArr, queue, targetDocIndex);
System.out.println(process);
}
}
public static int process(int[] importantArr, Queue<int[]> queue, int targetDocIndex){
//๋ช๋ฒ์งธ ์ถ๋ ฅ์ธ์ง
int result = 0;
//System.out.println("์ค์๋ ๋ฑ์ฅํ์ : " + Arrays.toString(importantArr));
//์ค์๋ ๋์ ์์๋๋ก ๋ฐ๋ณต
for (int important=9; important > 0; important--) {
//์ค์๋ ๋ฑ์ฅํ์๋งํผ ๋ฐ๋ณต
for (int count = importantArr[important-1]; count > 0; count--) {
//System.out.println("ํ์ฌ ์ค์๋ : "+important + ", ๋ฑ์ฅํ์ : "+count + ", " + print(queue));
//ํ์ฌ ์ค์๋์ ๋ฌธ์์ ์ค์๋๊ฐ ์ผ์นํ๋ฉด remove
if(important == queue.peek()[1]){
result++;
//์ฐพ๋ ๋ฌธ์์ ๋ฒํธ
if(targetDocIndex == queue.peek()[0]){
//System.out.println("*********** result : " + result);
return result;
}
queue.remove();
}else{ //ํ์ฌ ์ค์๋์ ๋ฌธ์์ ์ค์๋๊ฐ ์ผ์นํ์ง ์๋ค๋ฉด ๋ค๋ก ๋ณด๋ด๊ธฐ
queue.add(queue.poll());
//์ค์๋์ ํด๋นํ๋ ๋ฌธ์๋ฅผ ์ง์ฐ๊ธฐ ์ ๊น์ง๋ ๋ฃจํ๋๊ธฐ
count++;
}
}
}
return 0;
}
public static String print(Queue<int[]> queue){
StringBuilder sb = new StringBuilder();
sb.append("queue : ");
for (int[] o : queue) {
sb.append(Arrays.toString(o)+", ");
}
return sb.toString();
}
}
package util;
import java.io.ByteArrayInputStream;
import java.io.InputStream;
public class TestScanInput {
public static void ScanInput(String inputed){
InputStream in = new ByteArrayInputStream(inputed.getBytes());
System.setIn(in);
}
//์ด๋ ๊ฒ ์ค์ ํด๋๋ฉด ์
๋ ฅ๊ฐ์ ์ ํด๋๊ณ ํ
์คํธ ๋๋ฆด ์ ์๋ค!! ํจ์ฌ ํธ๋ฆฌํจ
}
package baekjoon;
import org.junit.jupiter.api.Test;
import util.TestScanInput;
import java.io.IOException;
class Main1966Test {
@Test
void test1() throws IOException {
TestScanInput.ScanInput("3\n" +
"1 0\n" +
"5\n" +
"4 2\n" +
"1 2 3 4\n" +
"6 0\n" +
"1 1 9 1 1 1");
Main1966.main(new String[0]);
}
@Test
void test2() throws IOException {
TestScanInput.ScanInput("1\n" +
"6 3\n" +
"1 1 9 2 1 2");
Main1966.main(new String[0]);
/*
1-1 1-2 9 2-1 1-3 2-2
1-2 9 2-1 1-3 2-2 1-1
9 2-1 1-3 2-2 1-1 1-2
2-1 1-3 2-2 1-1 1-2
* */
}
@Test
void test3() throws IOException {
TestScanInput.ScanInput("1\n" +
"38 29\n" +
"7 1 8 4 7 1 3 4 6 5 7 8 3 2 8 5 9 4 6 8 2 1 8 7 4 8 5 3 7 6 3 4 6 1 5 2 8 5");
Main1966.main(new String[0]);
//์ ๋ต 15
}
}
๋ฐ์ํ
'๐ฏ Coding Test' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 1012 ์ ๊ธฐ๋๋ฐฐ์ถ ์๋ฐ BFS, DFS (0) | 2022.02.21 |
---|---|
[๋ฐฑ์ค] 1697 ์จ๋ฐ๊ผญ์ง 1์ฐจ์ BFS (0) | 2022.02.12 |
[๋ฐฑ์ค] 9012 ๊ดํธ (0) | 2022.02.11 |
[๋ฐฑ์ค] 10828 ์คํ (๋ฐฐ์ด, LinkedList๋ก ๊ตฌํํด๋ณด๊ธฐ) (0) | 2022.02.10 |
[SWEA] 1206. [S/W ๋ฌธ์ ํด๊ฒฐ ๊ธฐ๋ณธ] 1์ผ์ฐจ - View (0) | 2022.02.10 |