[๋ฌธ์์ด] 10.๊ฐ์ฅ ์งง์ ๋ฌธ์๊ฑฐ๋ฆฌ
์ค๋ช
ํ ๊ฐ์ ๋ฌธ์์ด s์ ๋ฌธ์ t๊ฐ ์ฃผ์ด์ง๋ฉด ๋ฌธ์์ด s์ ๊ฐ ๋ฌธ์๊ฐ ๋ฌธ์ t์ ๋จ์ด์ง ์ต์๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์.
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ๋ฌธ์์ด s์ ๋ฌธ์ t๊ฐ ์ฃผ์ด์ง๋ค. ๋ฌธ์์ด๊ณผ ๋ฌธ์๋ ์๋ฌธ์๋ก๋ง ์ฃผ์ด์ง๋๋ค.
๋ฌธ์์ด์ ๊ธธ์ด๋ 100์ ๋์ง ์๋๋ค.
์ถ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ๊ฐ ๋ฌธ์์ด s์ ๊ฐ ๋ฌธ์๊ฐ ๋ฌธ์ t์ ๋จ์ด์ง ๊ฑฐ๋ฆฌ๋ฅผ ์์๋๋ก ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1
teachermode e
์์ ์ถ๋ ฅ 1
1 0 1 2 1 0 1 2 2 1 0
<<ํ์ด>>
์ฐ์ ๋ด๊ฐ ์ฒ์์ ํ๋ ํ์ด๋ค. ใ ใ ์ด ์ฝ๋๋ฅผ ์์ธํ ๋ณด๋ฉด ๋ชจ์์ด ์์์ ์ ์ ์๋ค.
์ผ๋จ ์ฒซ ๋ฒ์งธ ๋ชจ์์
์ฒซ ์์์ด ์ฐพ๋ ๊ฐ์ด ์๋๋ฐ๋ ๋ถ๊ตฌํ๊ณ ๊ฑฐ๋ฆฌ๊ฐ 1์ด๋ผ๊ณ ๊ณ์ฐํ๋ฉฐ ์์ํ๋ค. ๋ด๊ฐ ๋ง๋ก๋ง ํ๋ฉด ๋ฌด์จ ๋ง์ธ์ง ์ธ์ง ๋ชปํ ๊ฑฐ๋ค. ํด๋ณด๋ฉด ๋ฌด์จ ๋ง์ธ์ง ์ธ์ง ํ๋ค !!
๋ง์ฝ, abbbbbe ์ค ์ฐพ๋ ๋ฌธ์๊ฐ e๋ผ๋ฉด ๊ฐ์ฅ ์ฒซ๋ฒ์งธ ๋ฌธ์ a๋ e์ 1๊ฑฐ๋ฆฌ๋งํผ ์๋ค๊ณ ๋๋ ์ ์ด๋ค.
์ฌ์ค์ ์ฐพ๋ ๋ฌธ์ e๋ผ๋ ๊ฒ์ ๋ง๋๋ ์๊ฐ ๋ถํฐ ์ ํํ๊ฒ ์์น ๊ฑฐ๋ฆฌ๊ฐ ๋๋ค.
๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ๋๋ต ํฌ๊ธฐ๋ฅผ ์ก๋ ๊ฒ์ด ํ์ํ๋ค.
import javax.print.DocFlavor;
import java.util.ArrayList;
import java.util.Scanner;
class Main{
public ArrayList<Integer> solution(String str, char e) {
ArrayList<Integer> list = new ArrayList<>();
int count = 0;
for (char x : str.toCharArray()) {
if (x != e) {
count++;
list.add(count);
} else {
count = 0;
list.add(count);
}
}
count = 0;
for (int i = str.length() - 1; i >= 0; i--) {
if (str.charAt(i) != e) {
count++;
if (list.get(i) > count ) {
list.add(i, count);
System.out.println(list);
}
} else {
count = 0;
}
}
return list;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
String str = in.next();
char e = in.next().charAt(0);
for (int a : T.solution(str, e)) {
System.out.print(a);
}
}
}
===> ํด๊ฒฐ
์ฐ์ p = 1000์ผ๋ก ์ค์ ํด๋๊ณ ์์ํ๋ค. ์ด ๋ฌธ์ ๋ ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ํ ๋ฒ ์ค๋ฅธ์ชฝ์์ ์ผ์ชฝ์ผ๋ก ํ ๋ฒ ์ด ๋๋ฒ์ ๋ฐ๋ณต๋ฌธ์ด ํ์ํ๋ค. ๊ทธ์ค ์์ ๊ฐ์ ๋ฃ์ด์ค์ผ ํ๋ ๋ฌธ์ ์ด๋ค. ๊ทธ๋ ๊ธฐ ๋๋ฌธ์ 1000์ผ๋ก ์ค์ ํด๋๋ฉด ์ค๋ฅ๊ฐ ๋ฐ์ํ์ง ์๋๋ค. ์์ ๊ฐ์ ๋ฃ์ด์ฃผ๋ฉด ๋๋๊น, ๋ฌธ์ ์์๋ ๋ฌธ์์ด์ ๊ธธ์ด๊ฐ 100์ ๋์ง ์๋๋ค๊ณ ํ๋ ๋๋ํ๊ฒ 1000์ผ๋ก ์ก์ ์คฌ๋ค.
์ฌ๊ธฐ์ ์ฌ์ฉํ ์ฃผ๋ class๋ ๋ด์ฅ ํด๋์ค Math์ ๊ทธ ํด๋์ค์ ๋ฉ์๋์ธ min ์ด๋ค.
import java.util.ArrayList;
import java.util.Scanner;
class Main{
public int[] solution(String str, char e) {
int[] answer = new int[str.length()];
int p = 1000;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == e) {
p = 0;
answer[i] = p;
} else {
p++;
answer[i] = p;
}
}
p = 1000;
for (int i = str.length() - 1; i >= 0; i--) {
if (str.charAt(i) == e) p = 0;
else {
p++;
answer[i] = Math.min(answer[i], p);
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
String str = in.next();
char e = in.next().charAt(0);
for (int a : T.solution(str, e)) {
System.out.print(a + " ");
}
}
}
<<์ถ๊ฐ ๊ณต๋ถ>>
๋ด๊ฐ ์ฒ์์ ArrayList๋ฅผ ์ด์ฉํด์ ํด๋น ์ธ๋ฑ์ค์ ์ถ๊ฐํ๋ add(i, n) ๋ฐฉ์์ ์ฌ์ฉํ๋ค. ํ์ง๋ง ์ด๋ ์ง์ง ๊ทธ ์์น์ ๊ฐ์ ์ถ๊ฐํ๋ ๊ฑฐ์ง ๊ธฐ์กด ๊ฐ์ ํ ์นธ์ฉ ๋ฐ๋ฆฐ์ํ๋ก ๊ทธ๋๋ก ๋จ์ ์๋ค. ์ฆ, ๋์ฒด๊ฐ ๋์ง ์๋ ๊ฒ์ด๋ค. ์ด๋ฌํ ๊ธฐ๋ฅ๋ ์ ์ธ์งํ์.
(์ฌ์ค ๋ฐฐ์ด๋ก ์ฝ๊ฒ ํ ์ ์๋๊ฑด๋ฐ ใ ใ ๋๋ฌด ์ด๋ ต๊ฒ ์๊ฐํ๋ค.. ์ด ๋ํ ์์ง ์ค๋ ฅ์ด ๋ถ์กฑํ๋ค๋ ์ฆ๊ฑฐ๋ค ใ )
๋ ์ด์ฌํ ๊ผผ๊ผผํ ์ ์ ๋ฆฌํ์