[JAVA] 백준 1593번 - 문자 해독

1593번: 문자 해독 (acmicpc.net)

1593번: 문자 해독

package baekjoon;
import java.util.*;
import java.io.*;

public class b1593 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
        int w = Integer.parseInt(input[0]);
        int g = Integer.parseInt(input[1]);
		
		char arr[] = br.readLine().toCharArray();
		sort(arr);
		
		String ginputArr = br.readLine();
		
		int cnt = 0;
		boolean flag = false;
		for(int i = 0 ; i < g-w ; i++)
		{
			char arr2[] = ginputArr.substring(i,i+w).toCharArray();
			sort(arr2);
			flag = true;
			for(int j = 0 ; j < w ; j++)
			{
				if(arr[j] != arr2[j])
					flag = false;
			}
			if(flag)
				cnt++;
		}
		bw.write(cnt+"");
		
		bw.newLine(); // 줄바꿈
		bw.flush(); // 남아있는 데이터 모두 출력
		bw.close();
	}
	private static void sort(char[] arr) {
	    int n = arr.length;
	    for (int i = 1; i < n; ++i) {
	        char key = arr[i];
	        int j = i - 1;
	        while (j >= 0 && arr[j] > key) {
	            arr[j + 1] = arr[j];
	            j = j - 1;
	        }
	        arr[j + 1] = key;
	    }
	}
}

메모리 초과나는 코드임니다

ㅠ 화딱지날거 같음

package baekjoon;
import java.util.*;
import java.io.*;

public class b1593 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
        int w = Integer.parseInt(input[0]);
        int g = Integer.parseInt(input[1]);
		
		char arr[] = br.readLine().toCharArray();
		
		String ginputArr = br.readLine();
		
		int cnt = 0;
		boolean flag = false;
		for(int i = 0 ; i < g-w ; i++)
		{
			String arr2 = ginputArr.substring(i,i+w);
			flag = true;
			for(char j : arr)
			{
				if(arr2.indexOf(j)<0)
					flag = false;
			}
			if(flag)
				cnt++;
		}
		bw.write(cnt+"");
		
		bw.newLine(); // 줄바꿈
		bw.flush(); // 남아있는 데이터 모두 출력
		bw.close();
	}
}

아직도 초과뜸

ㅋ ㅠ ㅋ 

 

근데 뭔가 느낌은 알겟어서 혼자 힘으로 해보려는데 자꾸 이러니까 화나네요 약간 히로아카 캇짱이 왜 그리 화를 내는지 알 거 같은 느낌임니다 💫 

 

dhdld오잉 지금 지씨한테 코드 보내주면서 시간초과랑 메모리 둘다 신경써서 코드 좀 고쳐달라하니까 뭐 되게 길게 보내길래 걍 일단 제출했는데 정답이라네요

package baekjoon;
import java.util.*;
import java.io.*;

public class b1593 {

    public static void main(String[] args) throws IOException{
    	Scanner sc = new Scanner(System.in);

        int w = sc.nextInt();
        int g = sc.nextInt();

        String arr = sc.next();
        String ginputArr = sc.next();

        int cnt = 0;

        // arr 문자열의 빈도수를 저장하는 해시맵 생성
        Map<Character, Integer> arrFrequency = new HashMap<>();
        for (char c : arr.toCharArray()) {
            arrFrequency.put(c, arrFrequency.getOrDefault(c, 0) + 1);
        }

        // 초기 슬라이딩 윈도우의 빈도수 계산
        Map<Character, Integer> windowFrequency = new HashMap<>();
        for (int i = 0; i < w; i++) {
            char c = ginputArr.charAt(i);
            windowFrequency.put(c, windowFrequency.getOrDefault(c, 0) + 1);
        }

        // 첫 번째 윈도우에서 빈도수 비교 후 cnt 증가 여부 결정
        if (checkFrequencies(arrFrequency, windowFrequency)) {
            cnt++;
        }

        // 슬라이딩 윈도우를 오른쪽으로 이동하며 빈도수 비교
        for (int i = w; i < g; i++) {
            char leftChar = ginputArr.charAt(i - w);
            char rightChar = ginputArr.charAt(i);

            // 왼쪽 문자의 빈도수 감소
            windowFrequency.put(leftChar, windowFrequency.get(leftChar) - 1);
            if (windowFrequency.get(leftChar) == 0) {
                windowFrequency.remove(leftChar);
            }

            // 오른쪽 문자의 빈도수 증가
            windowFrequency.put(rightChar, windowFrequency.getOrDefault(rightChar, 0) + 1);

            // 빈도수 비교 후 cnt 증가 여부 결정
            if (checkFrequencies(arrFrequency, windowFrequency)) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    private static boolean checkFrequencies(Map<Character, Integer> arrFrequency, Map<Character, Integer> windowFrequency) {
        for (Map.Entry<Character, Integer> entry : arrFrequency.entrySet()) {
            char c = entry.getKey();
            int freq = entry.getValue();
            if (windowFrequency.getOrDefault(c, 0) < freq) {
                return false;
            }
        }
        return true;
    }
}

저는 

package baekjoon;
import java.util.*;
import java.io.*;

public class b1593 {

    public static void main(String[] args) throws IOException{
    	Scanner sc = new Scanner(System.in);

        int w = sc.nextInt();
        int g = sc.nextInt();

        String arr = sc.next();
        String ginputArr = sc.next();

        int cnt = 0;
        boolean flag = false;
        for(int i = 0 ; i < g-w ; i++)
        {
            flag = true;
            for(int j = 0 ; j < w ; j++)
            {
                if(arr.indexOf(ginputArr.charAt(i+j)) < 0)
                    flag = false;
            }
            if(flag)
                cnt++;
        }
        System.out.println(cnt);
    }
}

이 코드 주면서 물어본거긴한데 뭐가 많이 바뀌었네요

일단 올리고서 이해하겠습니다

이 풍경 오랜만이네요 ㅠ