์ฝ”๋”ฉํ…Œ์ŠคํŠธ

[๋ฌธ์ž์—ด] 10.๊ฐ€์žฅ ์งง์€ ๋ฌธ์ž๊ฑฐ๋ฆฌ

์‹œํ๋ฆฌํ‹ฐ์ง€ํ˜ธ 2023. 12. 3. 17:12
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) ๋ฐฉ์‹์„ ์‚ฌ์šฉํ–ˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด๋Š” ์ง„์งœ ๊ทธ ์œ„์น˜์— ๊ฐ’์„ ์ถ”๊ฐ€ํ•˜๋Š” ๊ฑฐ์ง€ ๊ธฐ์กด ๊ฐ’์€ ํ•œ ์นธ์”ฉ ๋ฐ€๋ฆฐ์ƒํƒœ๋กœ ๊ทธ๋Œ€๋กœ ๋‚จ์•„ ์žˆ๋‹ค. ์ฆ‰, ๋Œ€์ฒด๊ฐ€ ๋˜์ง€ ์•Š๋Š” ๊ฒƒ์ด๋‹ค. ์ด๋Ÿฌํ•œ ๊ธฐ๋Šฅ๋„ ์ž˜ ์ธ์ง€ํ•˜์ž. 

 

(์‚ฌ์‹ค ๋ฐฐ์—ด๋กœ ์‰ฝ๊ฒŒ ํ•  ์ˆ˜ ์žˆ๋Š”๊ฑด๋ฐ ใ…‹ใ…‹ ๋„ˆ๋ฌด ์–ด๋ ต๊ฒŒ ์ƒ๊ฐํ–ˆ๋‹ค.. ์ด ๋˜ํ•œ ์•„์ง ์‹ค๋ ฅ์ด ๋ถ€์กฑํ•˜๋‹ค๋Š” ์ฆ๊ฑฐ๋‹ค ใ…Ž)

 

๋” ์—ด์‹ฌํžˆ ๊ผผ๊ผผํžˆ ์ž˜ ์ •๋ฆฌํ•˜์ž