이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(https://cote.inflearn.com/contest/10/problems) (김태원)의 문제입니다.

문제 설명

코드

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

public class sec01_05 {
    public static String solution(String str) {
        char[] temp = str.toCharArray();
        int lp = 0; int rp = str.length() - 1;
        while (lp < rp){
            if(!Character.isAlphabetic(temp[lp])) ++lp;
            else if(!Character.isAlphabetic(temp[rp])) --rp;
            else {
                char tmp = temp[lp];
                temp[lp] = temp[rp];
                temp[rp] = tmp;
                ++lp; --rp;
            }
        }
        return String.valueOf(temp);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(solution(br.readLine()));
    }
}

설명

초기 설정

• char[] temp = str.toCharArray();: 입력 문자열을 문자 배열로 변환한다. 문자열은 불변 객체이므로, 배열로 변환하여 개별 문자에 접근하고 수정하기 위함이다.
• int lp = 0; int rp = str.length() - 1;: 두 개의 포인터 lp와 rp를 설정한다. lp는 배열의 시작을, rp는 배열의 끝을 가리킨다.

반복문

• while (lp < rp): 두 포인터가 교차할 때까지 반복한다.
• if (!Character.isAlphabetic(temp[lp])) ++lp;: lp가 가리키는 문자가 알파벳이 아니면 lp를 오른쪽으로 이동한다.
• else if (!Character.isAlphabetic(temp[rp])) --rp;: rp가 가리키는 문자가 알파벳이 아니면 rp를 왼쪽으로 이동한다.
• else: 두 포인터가 가리키는 문자가 모두 알파벳이면 두 문자를 교환하고, lp와 rp를 각각 오른쪽과 왼쪽으로 이동한다.

문자열 변환

• return String.valueOf(temp);: 변환된 문자 배열을 문자열로 다시 변환하여 반환한다.

char[]의 toString() 메서드

char[] 배열에 대해 toString() 메서드를 호출하면, 배열의 요소를 문자열로 변환하는 것이 아니라, 배열 객체의 메모리 주소를 나타내는 해시코드를 포함한 문자열을 반환하게 된다.
이는 Object 클래스의 toString() 메서드가 호출되기 때문이다.
char[] 배열은 Object 클래스를 상속받기 때문에, 특별히 오버라이드된 toString() 메서드가 없다면 기본적으로 Object의 toString() 메서드가 사용된다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(https://cote.inflearn.com/contest/10/problems) (김태원)의 문제입니다.

문제 설명

코드

import java.io.IOException;
import java.util.Scanner;

public class sec01_04 {
    public static void solution(String[] str) {
        StringBuilder sb = new StringBuilder(new String(""));
        for (String s : str) {
            sb.append(new StringBuilder(s).reverse()).append("\n");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] strings = new String[N];
        for (int i = 0; i < N; i++) {
            strings[i] = sc.next();
        }
        solution(strings);
    }
}

설명

• solution 메소드는 문자열 배열을 입력으로 받아, 각 문자열을 역순으로 변환한 후, 모든 결과를 StringBuilder에 저장하여 출력한다.
• StringBuilder sb = new StringBuilder(new String(""))로 초기화한다.
• 배열 str의 각 문자열 s에 대해 new StringBuilder(s).reverse()를 통해 역순으로 변환하고, 이를 sb에 추가하고 줄바꿈 문자를 추가한다.
• System.out.println(sb)를 통해 최종 결과를 출력한다.

문제설명

소스코드

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! 알고리즘 코딩 테스트 - 자바편

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(https://cote.inflearn.com/contest/10/problems) (김태원)의 문제입니다.

문제 설명

코드

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

public class sec01_03 {
    public static String solution(String str) {
        StringTokenizer st = new StringTokenizer(str);
        int max = 0;
        String text = "";
        while (st.hasMoreTokens()){
            String temp = st.nextToken();
            int length = temp.length();
            if(length > max) {
                max = length;
                text = temp;
            }
        }
        return text;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String text = br.readLine();
        System.out.println(solution(text));
    }
}

설명

• StringTokenizer 로 공백을 기준으로 문자열을 자른다.
• 잘라진 단어 갯수만큼 루프를 돌면서 단어의 길이를 측정하고, 단어의 길이가 가장 길다면 temp 변수에 저장한다.
• 루프가 종료되면 가장 길이가 긴 단어는 temp 변수에 저장된다.
• temp 변수의 값을 출력한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(https://cote.inflearn.com/contest/10/problems) (김태원)의 문제입니다.

문제 설명

코드

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

public class sec01_02 {
    public static String solution(String str) {
        StringBuilder sb = new StringBuilder();
        for (char c : str.toCharArray()) {
            if(Character.isLowerCase(c)) sb.append(Character.toUpperCase(c));
            else sb.append(Character.toLowerCase(c));
        }
        return new String(sb);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String text = br.readLine();
        System.out.println(solution(text));
    }
}

설명

• Character 클래스의 isUpperCase() 메서드는 문자가 대문자인지 확인하고, isLowerCase() 메서드는 문자가 소문자인지 확인한다.(리턴 타입 = Boolean)
• isUpperCase(), isLowerCase() 를 활용하여 대문자는 소문자로, 소문자는 대문자로 변환하여 문자열을 만든다.

문제설명

소스코드

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)이 된다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(https://cote.inflearn.com/contest/10/problems) (김태원)의 문제입니다.

문제 설명

코드

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

class Main {
    public static int solution(String fullText, char character) {
        String lowerFullText = fullText.toLowerCase();
        char lowerChar = Character.toLowerCase(character);
        int count = 0;

        for (int i = 0; i < lowerFullText.length(); i++) {
            if (lowerFullText.charAt(i) == lowerChar) {
                count++;
            }
        }
        
        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String fullText = br.readLine();
        char character = br.readLine().charAt(0);
        System.out.println(solution(fullText, character));
    }
}

설명

• 문자열과 문자를 입력받는다.
• 문자열과 문자를 모두 소문자로 변환한다.
• 문자열을 순회하면서 문자를 찾고, 찾을 때마다 count의 수를 +1 시킨다.

문제설명

소스코드

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이라는 점이다.
• 따라서 숫자로 처리하기 보다는 문자로 처리해야한다.