문제설명

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_10986 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long count = 0;

        long[] prefixSum = new long[N + 1];
        long[] remainArr = new long[M];
        for (int i = 1; i <= N; ++i) {
            prefixSum[i] = arr[i - 1] + prefixSum[i - 1];
            int remainder = (int) (prefixSum[i] % M);
            if(remainder == 0) ++count;
            ++remainArr[remainder];
        }

        for(int i = 0; i < M; ++i){
            if(remainArr[i] >= 2) count += (remainArr[i] * (remainArr[i] - 1) / 2);
        }

        System.out.println(count);
    }
}

설명

아래의 영상을 보고 이해하는 것이 글로 이해하는 것보다 훨씬 빠를 것이다.

https://www.youtube.com/watch?v=Ud-qe0t5KA8&ab_channel=%ED%95%98%EB%A3%A8%EC%BD%94%EB%94%A9

문제설명

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_11660 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        String NM = br.readLine();
        st = new StringTokenizer(NM);
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] nxn = new int[N + 1][N + 1];
        int[][] prefixSum = new int[N + 1][N + 1];

        for (int i = 1; i <= N; ++i) {
            String inputRow = br.readLine();
            st = new StringTokenizer(inputRow);
            for (int j = 1; j <= N; ++j) {
                nxn[i][j] = Integer.parseInt(st.nextToken());
                prefixSum[i][j] = nxn[i][j] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
            }
        }

        for (int i = 0; i < M; ++i) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int result = prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1];
            sb.append(result).append('\n');
        }
        System.out.print(sb);
    }
}

설명

• 이 문제의 핵심 개념은 누적 합이다.
• 부분합(prefix sum) 배열을 이해하려면, 이 배열이 무엇을 하는지부터 이해하는 것이 중요하다. 이 배열은 특정 구간의 합을 빠르게 계산할 수 있도록 도와준다. 이차원 배열에서는 특정 영역의 합을 효율적으로 계산하기 위해 부분합 배열을 사용한다.
• prefixSum[i][j]=nxn[i][j]+prefixSum[i−1][j]+prefixSum[i][j−1]−prefixSum[i−1][j−1]
  이 공식은 현재 위치까지의 누적 합을 계산하는 데 사용된다. 각 항목의 의미는 아래와 같다.
  nxn[i][j]: 현재 위치의 원래 배열 값
  prefixSum[i-1][j]: 현재 위치의 윗줄까지의 누적합
  prefixSum[i][j-1]: 현재 위치의 왼쪽 열까지의 누적합
  prefixSum[i-1][j-1]: 윗줄과 왼쪽 열의 겹치는 부분을 두 번 더했기 때문에 한 번 빼줌
• prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1]
  이 공식의 누적 합을 이용하여 구간 합을 계산하는데 사용된다. 각 부분의 의미는 아래와 같다.
  prefixSum[x2][y2]: (1,1)부터 (x2,y2)까지의 부분 합이다.
  prefixSum[x1 - 1][y2]: (1,1)부터 (x1-1,y2)까지의 부분 합을 빼준다. 이는 x1보다 위쪽의 구간을 빼주는 역할을 한다.
  prefixSum[x2][y1 - 1]: (1,1)부터 (x2,y1-1)까지의 부분 합을 빼준다. 이는 y1보다 왼쪽의 구간을 빼주는 역할을 한다.
  prefixSum[x1 - 1][y1 - 1]: (1,1)부터 (x1-1,y1-1)까지의 부분 합을 더해준다. 이는 두 번 빼진 겹치는 구간을 다시 더해주는 역할을 한다.

아직 이해가 되지 않는다면, 아래의 예시를 통해 이해할 수 있다.

1. 누적 합 배열 만들기

2. 누적 합 배열을 이용하여 구간 합 계산하기

예를 들어 질의가 2 2 3 4 라면

(3, 4) 구간 합에서 (1, 4) 구간합, (3, 1) 구간 합을 뺀 다음 중복하여 뺀(1, 1) 구간합을 더하면 된다.

그림 출처 : Do It! 알고리즘 코딩 테스트 - 자바편

문제설명

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String NM = br.readLine();
        StringTokenizer st = new StringTokenizer(NM);
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String inputArr = br.readLine();
        st = new StringTokenizer(inputArr);

        int[] numArr = new int[N];
        for (int i = 0; i < numArr.length; i++) {
                numArr[i] = Integer.parseInt(st.nextToken());
        }

        int[] prefixSum = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            prefixSum[i] = numArr[i - 1] + prefixSum[i-1];
        }
        for(int i = 0; i < M ; ++i){
            String inputTwo = br.readLine();
            st = new StringTokenizer(inputTwo);
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int sum = prefixSum[end] - prefixSum[start - 1];

            sb.append(sum).append("\n");
        }
        System.out.println(sb);
    }
}

설명

이 문제의 시간 초과를 방지하는 핵심 아이디어는 누적 합 배열을 구하는 것이다.

먼저, BufferedReader를 사용하여 입력을 받고, 이를 처리한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String NM = br.readLine();
StringTokenizer st = new StringTokenizer(NM);
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

다음으로, 배열의 원소들을 입력 받는다.

String inputArr = br.readLine();
st = new StringTokenizer(inputArr);

int[] numArr = new int[N];
for (int i = 0; i < numArr.length; i++) {
    numArr[i] = Integer.parseInt(st.nextToken());
}

배열의 각 구간 합을 빠르게 계산하기 위해 Prefix Sum 배열을 만든다.

int[] prefixSum = new int[N + 1];
for (int i = 1; i <= N; i++) {
    prefixSum[i] = numArr[i - 1] + prefixSum[i-1];
}

구간 합을 계산하고, 결과를 저장한다.

for(int i = 0; i < M ; ++i){
    String inputTwo = br.readLine();
    st = new StringTokenizer(inputTwo);
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());
    int sum = prefixSum[end] - prefixSum[start - 1];

    sb.append(sum).append("\n");
}

• 각 계산마다 start와 end 값을 읽어온다.
• prefixSum[end] - prefixSum[start - 1]을 계산하여 start부터 end까지의 구간 합을 구한다.
• 결과를 StringBuilder에 저장한다.

예를 들어, 입력 배열이 다음과 같다고 가정하자.

numArr = [5, 4, 3, 2, 1]

구간 합을 저장하는 배열은 아래와 같이 계산된다.

prefixSum[0] = 0
prefixSum[1] = 5 + 0 = 5
prefixSum[2] = 4 + 5 = 9
prefixSum[3] = 3 + 9 = 12
prefixSum[4] = 2 + 12 = 14
prefixSum[5] = 1 + 14 = 15

결과적으로, 구간 합 배열은 아래와 같다.

prefixSum = [0, 5, 9, 12, 14, 15]

따라서 문제의 예제를 다시 보면 아래와 같은 계산과정이 도출된다.

start = 1, end = 3

int sum1 = prefixSum[3] - prefixSum[0];
//sum = 12 - 0 = 12

start = 2. end = 4

int sum2 = prefixSum[4] - prefixSum[1];
//sum = 14 - 5 = 9

start = 5. end = 5

int sum2 = prefixSum[5] - prefixSum[4];
//sum = 15 - 14 = 1

현재 구간 합으로 구현한 코드의 시간 복잡도는 O(N + M)이다.

구간 합을 사용하지 않는다면 시간 복잡도는 O(N * M)이 된다.

문제설명

소스코드

import java.util.Scanner;

public class Boj_5988 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N =  sc.nextInt();

        if(N != 0){
            for (int i = 0; i < N; i++) {
                String[] arr = sc.next().split("");
                System.out.println(Integer.parseInt(arr[arr.length - 1]) % 2 == 1 ? "odd": "even");
            }
        }
    }
}

설명

• 가장 주의해야 할 점은 K의 범위가 10^60이라는 점이다.
• 따라서 숫자로 처리하기 보다는 문자로 처리해야한다.

문제설명

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main
{	
	static public boolean KMP(String str, String pattern)
	{
		int LPS[] = new int[pattern.length()]; //LPS 배열 생성
        int index = 0; //IDX, 찾을 문자열의 비교 인덱스를 뜻하기도 하며, 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 함
        for (int i = 1; i < pattern.length(); i++) //LPS배열의 값을 입력
        {
            if (pattern.charAt(i) == pattern.charAt(index)) LPS[i] = ++index; //접두사와 접미사가 같을 때, index를 1 증가
            else  //접두사와 접미사가 같지 않을 때
            {
                if (index != 0) //0이면 더 이상 돌아갈 위치가 없음
                {
                    index = LPS[index - 1]; //LPS[index - 1] : 이전 위치로 돌아가야 할 위치를 나타냄, 이 위치에서부터 비교를 다시 시작하여 일치하는 부분을 찾음
                    --i; // 현재 위치에서부터 다시 패턴 매칭을 시도(여기서 --i하고 이후 루프에서 ++i가 될테니)
                }
            }
        }
    	index = 0; //0으로 초기화
    	for(int i = 0; i < str.length(); i++) //문자열 탐색 시작
    	{
    		while(index > 0 && str.charAt(i) != pattern.charAt(index)) index = LPS[index - 1]; //LPS[index - 1] : 이전으로 돌아가야할 위치
    		if(str.charAt(i) == pattern.charAt(index)) //접두사와 접미사가 같을 때
    		{
    			 //IDX는 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 하는데, 이것이 pattern의 길이와 같다면 탐색 성공
    			if(index == pattern.length() - 1) return true;
    			else ++index; //길이가 같지 않다면 index를 1증가
    		}
    	}
    	return false;
    }
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String pattern = br.readLine();
		boolean flag = KMP(str, pattern);
		System.out.print(flag ? 1 : 0);
	}
}

설명

• KMP 알고리즘 사용
• 주석 참고
• 자세한 내용은 아래의 글 참고

2023.11.28 - [자료구조 & 알고리즘/알고리즘] - [Java]KMP 문자열 탐색 알고리즘

문제설명

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main
{	
	static public ArrayList<Integer> KMP(String str, String pattern)
	{
        ArrayList<Integer> idxList = new ArrayList<>(); //찾는 문자열을 발견시 해당 문자열의 시작 인덱스를 저장하는 리스트
        int LPS[] = new int[pattern.length()]; //LPS 배열 생성
        int index = 0; //IDX, 찾을 문자열의 비교 인덱스를 뜻하기도 하며, 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 함
        for (int i = 1; i < pattern.length(); i++) //LPS배열의 값을 입력
        {
            if (pattern.charAt(i) == pattern.charAt(index)) LPS[i] = ++index; //접두사와 접미사가 같을 때, index를 1 증가
            else  //접두사와 접미사가 같지 않을 때
            {
                if (index != 0) //0이면 더 이상 돌아갈 위치가 없음
                {
                    index = LPS[index - 1]; //LPS[index - 1] : 이전 위치로 돌아가야 할 위치를 나타냄, 이 위치에서부터 비교를 다시 시작하여 일치하는 부분을 찾음
                    --i; // 현재 위치에서부터 다시 패턴 매칭을 시도(여기서 --i하고 이후 루프에서 ++i가 될테니)
                }
            }
        }
    	index = 0; //0으로 초기화
    	for(int i = 0; i < str.length(); i++) //문자열 탐색 시작
    	{
    		while(index > 0 && str.charAt(i) != pattern.charAt(index)) index = LPS[index - 1]; //LPS[index - 1] : 이전으로 돌아가야할 위치
    		if(str.charAt(i) == pattern.charAt(index)) //접두사와 접미사가 같을 때
    		{
    			if(index == pattern.length() - 1) //IDX는 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 하는데, 이것이 pattern의 길이와 같다면 탐색 성공
    			{
    				idxList.add(i - index); //일치하는 첫 번째 인덱스를 추가
    				index = LPS[index]; //LPS[index] : 현재 일치하는 부분의 최대 길이를 나타내며, 이 길이만큼은 이미 패턴과 일치함이 보장
    			}
    			else ++index; //길이가 같지 않다면 index를 1증가
    		}
    	}
    	System.out.println(idxList.size()); //리스트의 사이즈 = 몇 번 나오는지 횟수
    	return idxList;
    }
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String pattern = br.readLine();
		ArrayList<Integer> list = KMP(str, pattern); //시작 인덱스들을 받아옴
		for (Integer i : list) System.out.print(i + 1 + " "); //시작 인덱스들을 출력
	}
}

설명

• KMP 알고리즘 사용
• 주석 참고
• 자세한 설명은 아래의 글 참고

2023.11.28 - [자료구조 & 알고리즘/알고리즘] - [Java]KMP 문자열 탐색 알고리즘

문제설명

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String input = br.readLine();
		String[] arr = {"000","001","010","011","100","101","110","111"};
		for(int i = 0; i < input.length(); ++i)
		{
			int tmp = input.charAt(i) - '0'; //'0'의 아스키코드 값은 48, 이렇게하면 원하는 정수를 얻을 수 있음
			sb.append(arr[tmp]);
		}
		if (input.equals("0")) System.out.print(0);
		else
		{
			while(sb.charAt(0) == '0') sb = new StringBuilder(sb.substring(1)); //0이 없어질때까지 0을 제거
			System.out.println(sb);
		}
	}
}

설명

• 8진수를 2진수로 바꾸려면 아래와 같은 과정을 거친다.
  314 : 3->011, 1->001, 4->100
  합치면 011001100
• 맨 앞의 수가 0이면 제거해줘야한다.
  즉, 11001100이어야 한다.
  만약 001100000 이런 이진수는 앞의 두 개의 0을 제거해줘야한다.
• 0의 값이 들어오면 000이 출력되는 것이 아니라 0이 출력되어야 한다.

문제설명

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main
{
	static StringBuilder sb = new StringBuilder();
	static Node root = new Node(null, null, null); //루트노드
	static class Node //노드 클래스
	{
		String value; //현재 노드의 값을 저장
		Node left; //왼쪽 자식 노드의 레퍼런스를 저장
		Node right; //오른쪽 자식 노드의 레퍼런스를 저장
		Node(String value, Node left, Node right)
		{
			this.left = left;
			this.right = right;
			this.value = value;
		}
	}
	
	static void insertNode(Node node, String value, String left, String right)
	{
        if(node == null) return; //재귀 종료조건, 리프 노드를 만나면 종료
        if(root.value == null) //루트노드 값이 null이라면
        {
        	root.value = value; //루트노드 값을 저장
        	 if(!left.equals(".")) root.left = new Node(left, null, null); //왼쪽 노드를 생성하고 가리킴
             if(!right.equals(".")) root.right = new Node(right, null, null); //오른쪽 노드를 생성하고 가리킴
        }
        else if(node.value.equals(value)) //삽입할 위치라면
        {
            if(!left.equals(".")) node.left = new Node(left, null, null); //왼쪽 노드를 생성하고 가리킴
            if(!right.equals(".")) node.right = new Node(right, null, null); //오른쪽 노드를 생성하고 가리킴
        } 
        else //삽입할 위치가 아니라면
        {
            insertNode(node.left, value, left, right); //왼쪽 자식노드로 이동(재귀)
            insertNode(node.right, value, left, right); //오른쪽 자식노드로 이동(재귀)
        }
    }
	
	public static void preOrder(Node node) //전위 순회
	{
		if(node == null) return; //재귀 종료조건, 리프 노드라면 종료
		sb.append(node.value); //현재 노드 방문(출력)
		preOrder(node.left); //왼쪽 노드로 이동(재귀)
		preOrder(node.right); //오른쪽 노드로 이동(재귀)
	}
	
	public static void inOrder(Node node) //중위 순회
	{
		if(node == null) return; //재귀 종료조건, 리프 노드라면 종료
		inOrder(node.left); //왼쪽 노드로 이동(재귀)
		sb.append(node.value); //현재 노드 방문(출력)
		inOrder(node.right); //오른쪽 노드로 이동(재귀)
	}
	
	public static void postOrder(Node node) //후위 순회
	{
		if(node == null) return; //재귀 종료조건, 리프 노드라면 종료
		postOrder(node.left); //왼쪽 노드로 이동(재귀)
		postOrder(node.right); //오른쪽 노드로 이동(재귀)
		sb.append(node.value); //현재 노드 방문(출력)
	}
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		for(int i = 0; i < N; ++i)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			String value = st.nextToken();
			String left = st.nextToken();
			String right = st.nextToken();
			insertNode(root, value, left, right); //노드 삽입, 루트 노드부터 삽입 위치를 재귀적으로 찾아감
		}
		preOrder(root); //전위 순회 메소드 호출
		sb.append("\n");
		inOrder(root); //중위 순회 메소드 호출
		sb.append("\n");
		postOrder(root); //후위 순회 메소드 호출
		sb.append("\n");
		System.out.print(sb.toString());
	}
}

설명

• 재귀를 이용한 방법
• 자세한 코드 설명은 주석 참고