[백준 JAVA] 21921 블로그

21921 블로그

https://www.acmicpc.net/problem/21921

문제설명

주어진 기간 동안 최대 방문자 수를 가지는 구간을 찾고

그 구간의 방문자 수와 구간의 개수를 출력한다.

접근방식

O(N) 선형 시간복잡도

 

슬라이딩 윈도우 연산은 상수 시간이 소요되므로, 

입력받은 배열만큼의 합을 계산하는데 O(N)의 시간이 소요된다.

문제 조건 분석 과정

 

• 입력 처리:
  • 배열의 크기 NNN과 부분 배열의 길이 MMM을 읽는다.
  • 방문자 수를 배열에 저장한다.
  • 배열의 길이에 맞게 슬라이딩 윈도우 기법을 사용하여 부분 배열의 합을 계산한다.
• 슬라이딩 윈도우:
  • 처음 MMM개의 요소의 합을 계산한다.
  • 그 다음에는 윈도우를 오른쪽으로 이동하면서 합을 갱신한다.
  • 이동 시, 왼쪽 끝 요소를 빼고 오른쪽 끝 요소를 추가한다.
  • 최대 합을 갱신하며, 최대 합과 같은 합을 가지는 구간의 개수를 카운트한다.
• 결과 출력:
  • 최대 합이 0이면 "SAD"를 출력한다.
  • 그렇지 않으면 최대 합과 구간의 개수를 출력한다.

전체코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 437674; //변환할 수
        int k = 3; //변환할 진법 (3진법)

        //solution메서드 호출
        System.out.println(solution(n, k));
    }

    public static int solution(int n, int k) {

        int result = 0;
        //정수 n을 진법 k로 변환한 문자열
        String re = Integer.toString(n, k);

        //문자열을 0으로 구분하여 분리
        for(String rea : re.split("0")){
            //빈 문자열 무시
            if(rea.equals("")) continue;
            //문자열이 소수인지 확인
            if(isPrime(rea) == false){
                result++; //소수가 아닌 경우 result 증가
            }
        }

        return result;

    }

    public static boolean isPrime(String num){
        long n = Long.parseLong(num);

        //1은 소수가 아님
        if(n == 1){
            return true;
        }

        //2부터 n의 제곱근까지 나눠서 소수 여부 판별
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0){
                return true; //나누어 떨어지면 소수가 아님
            }
        }

        return false;
    }
}