star, 시간복잡도, 빈도수, 규칙 찾기, swap, 순환, scanner 및 BufferedReader

문제 1.

*
**
***
****
*****

for(int i=1;i<=5;i++){
    for(int j=0;j<i;j++){
       System.out.print("*");
    }
    System.out.println();
}

강사님 답

for(int i=0;i<5;i++){
    for(int j=0;j<=i;j++){
       System.out.print("*");
    }
    System.out.println();
}

문제 2.

*****
 ****
  ***
   **
    *

int n = 5;
for(int i=n;i>0;i--){
    for(int j=n-i;j>0;j--){
        System.out.print(" ");
    }
    for(int j=0;j<i;j++){
        System.out.print("*");
    }
    System.out.println();
}

강사님 답

for(int i=0; i<5;i++){
    for(int j=0;j<5;j++){
        if(j<i){
            System.out.print(" ");
        }
        else{
            System.out.print("*");
        }
    }
    System.out.println();
}

문제 3.

*******
 ***** 
  ***  
   *   
  ***  
 ***** 
*******

int n = 7;

for(int i=n;i>0;i=i-2){
    for(int j=(n-i)/2;j>0;j--){
        System.out.print(" ");
    }
    for(int j=0;j<i;j++){
        System.out.print("*");
    }
    for(int j=(n-i)/2;j>0;j--){
        System.out.print(" ");
    }
    System.out.println();
}

for(int i=3;i<=n;i=i+2){
    for(int j=(n-i)/2;j>0;j--){
        System.out.print(" ");
    }
    for(int j=0;j<i;j++){
        System.out.print("*");
    }
    for(int j=(n-i)/2;j>0;j--){
        System.out.print(" ");
    }
    System.out.println();
}

강사님 답

// 공백문자 수 증감, 공백문자 증감 변화
int turnCnt = 7/2; // 공백 문자 수 증감이 변화되는 시점
int spaceCnt = 0;
boolean spaceIncrease = true;

for(int i=0;i<7;i++){
    for(int j=0;j<7; j++){
        if(j<spaceCnt){
            System.out.print(" ");
        } else if (j<7-spaceCnt) {
            System.out.print("*");
        }
    }
    System.out.println();

    // 매행마다 공백 증감
    if(spaceIncrease){
        spaceCnt++;
    }else {
        spaceCnt--;
    }

    // spaceCnt가 변화지점에 도달
    if(spaceCnt == turnCnt){
        spaceIncrease = false;
    }
}

알고리즘 문제 : input 제시 -> 조건과 규칙을 가지고 -> output 출력 시키기
효율적인 코드 = 시간 적게 걸리고, 자원을 적게 사용 => 시간 복잡도를 더 신경 씀

시간 복잡도 별 예시>

O(1) - 상수 시간 (Constant Time)

int[] arr = {10, 20, 30, 40};
System.out.println(arr[2]);

O(logN) - 로그 시간 (Logarithmic time)

이진탐색

public class BinarySearchExample {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) return mid;      // 찾음
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1; // 못 찾음
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        System.out.println(binarySearch(arr, 7)); // 출력: 3
    }
}

O(n) - 선형 시간 (Linear time)

선형탐색

public class LinearSearchExample {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        System.out.println(linearSearch(arr, 30)); // 출력: 2
    }
}

O(N logN) - 선형 로그 시간 (Linear Logarithmic time)

Merge Sort

import java.util.Arrays;

public class MergeSortExample {
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) return;

        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) arr[k++] = left[i++];
            else arr[k++] = right[j++];
        }

        while (i < left.length) arr[k++] = left[i++];
        while (j < right.length) arr[k++] = right[j++];
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr)); // [1, 2, 5, 5, 6, 9]
    }
}

O(n²) - 2차 시간 (Quadratic time)

선택 정렬

import java.util.Arrays;

public class SelectionSortExample {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 최소값 인덱스

            // i 이후 구간에서 최소값 찾기
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 최소값을 i번째와 교환
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 10, 14, 37, 13};
        System.out.println("정렬 전: " + Arrays.toString(arr));

        selectionSort(arr);

        System.out.println("정렬 후: " + Arrays.toString(arr));
    }
}

O(2^n) – 지수 시간 (Exponential Time)

피보나치 수열 재귀

public class FibonacciExponential {
    public static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2); // 두 번씩 재귀 → O(2^n)
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 55
    }
}

O(n!) – 팩토리얼 시간 (Factorial Time)

순열

import java.util.*;

public class PermutationExample {
    public static void permute(List<Integer> nums, int l, int r) {
        if (l == r) {
            System.out.println(nums);
            return;
        }
        for (int i = l; i <= r; i++) {
            Collections.swap(nums, l, i);
            permute(nums, l + 1, r); // n! 경우 탐색
            Collections.swap(nums, l, i);
        }
    }

    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1, 2, 3);
        permute(nums, 0, nums.size() - 1);
    }
}

문제 4.

글자 빈도수 배열로 체크

String str = "abbcccddddeeeeeffffggghhiabbcccddddeeeeeffffggghhi";
int[] alpha = new int[26];

for(int i = 0; i<str.length();i++){
    char now = str.charAt(i);
    if( now >= 'a' && now <= 'z'){
        alpha[now-'a']++;
    }
}
for (int i = 0; i < alpha.length; i++) {
    if (alpha[i] > 0) {
        System.out.println((char) (i + 'a') + " : " + alpha[i]);
    }
}

강사님 답

String str = "abbcccddddeeeeeffffggghhiabbcccddddeeeeeffffggghhi";
int[] alphaCnt = new int[26];
int strLen = str.length();

for(int i=0;i<strLen;i++){
    alphaCnt[str.charAt(i)-'a']++;
}

System.out.println(Arrays.toString(alphaCnt));
for(int i=0;i<strLen;i++){
    System.out.println((char)(i+'a') + " : " + alphaCnt[i]);
}

문제 5.

규칙 점검(1번째 값*2번째 값 = 3번째 값의 쌍으로 이루어진 배열)

int[] intArray = {3,2,6, 3,4,4, 1,4,2, 2,3,6, 1,3,5, 1,5,1, 1,1,1, 2,4,2, 2,2,4};
int e = 0;

for(int i=2;i< intArray.length;i=i+3){
    if(intArray[i] != intArray[i-1] * intArray[i-2]){
        e++;
    }
}
System.out.println("곱셉 결과가 잘못된 쌍의 수 : "+e);

강사님 답

int[] intArray = {3,2,6, 3,4,4, 1,4,2, 2,3,6, 1,3,5, 1,5,1, 1,1,1, 2,4,2, 2,2,4};
int wrongCnt = 0;
int intLenth = intArray.length - 2;

for(int i=0;i<intLenth;i=i+3){
    if(intArray[i]*intArray[i+1] != intArray[i+2]){
        wrongCnt++;
    }
}
System.out.println("곱셉 결과가 잘못된 쌍의 수 : "+wrongCnt);

문제 6.

charArray 짝수 보장

char[] charArray = "XYZEBFFGQOVVPWGFFCEAYX".toCharArray();
int wrongCnt = 0;

for(int i=0;i<charArray.length/2;i++){
    if(charArray[i] != charArray[charArray.length-1-i]){
        wrongCnt++;
        System.out.println("비대칭 - "+(i+1)+"번째 : "+charArray[i]+charArray[charArray.length-1-i]);
    }
}
System.out.println("비대칭 개수 : "+wrongCnt);

강사님 답

char[] charArray = "XYZEBFFGQOVVPWGFFCEAYX".toCharArray();
int wrongCnt = 0;

int center = charArray.length/2;
for(int l=0, r=charArray.length-1;l<center;l++, r--){
    if(charArray[l] != charArray[r]){
        wrongCnt++;
    }
}
System.out.println("비대칭 개수 : "+wrongCnt);

문제 7.

swap

String[] strArray = {"111", "222", "333", "444", "555", "666"}; // 개수 - 짝수
//String[] strArray = {"111", "222", "333", "444", "555", "666", "777"}; // 개수 - 홀수

String temp = "";
for(int i=0;i<strArray.length/2;i++){
    temp = strArray[i];
    strArray[i] = strArray[strArray.length-1-i];
    strArray[strArray.length-1-i] = temp;
}
for(String s:strArray){
    System.out.print(s+" ");
}

강사님 답

// 1. 기본적인 swap 방식
int center = strArray.length/2;
for(int l=0, r=strArray.length-1;l<center;l++, r--){
    String temp = strArray[l];
    strArray[l] = strArray[r];
    strArray[r] = temp;
}
System.out.println(Arrays.toString(strArray));

// 2. Collections.reverse()
List<String> strList = Arrays.asList(strArray);
Collections.reverse(strList);

System.out.println(Arrays.toString(strArray));

문제 8.

for문 1개로 원하는 만큼 반복시키기

// Circular Array
char[] input = {'A','B','C','D','E','F','G'};
int n = input.length;

for(int i=0;i<n*2;i++){
    System.out.print(input[i%n]+" ");
}

문제 9.

while로 하기

int total = 20;
int i=0;

while (total-- != 0){
    System.out.print(input[(i++)%n]+" ");
}

강사님 답

int total = 20;
int i=0;

while (true){
    if(i==total) break;
    System.out.print(input[i%n]+" ");
    i++;
}

Scanner

canner sc = new Scanner(System.in);

int[] intput = new int[5];
char[] intputC = new char[5];

//for(int i=0;i<5;i++){
//    intput[i] = sc.nextInt();
//    intputC[i] = sc.next().charAt(0);
//}

char[] intputC2 = sc.nextLine().toCharArray();

System.out.println(Arrays.toString(intputC2));

BufferedReader

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

System.out.println(Arrays.toString(input));

2차원 배열 만들기

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());
int[][] input = new int[N][m];


for(int i=0;i<N;i++){
    st = new StringTokenizer(br.readLine());
    for(int j=0;j<m;j++){
        input[i][j] = Integer.parseInt(st.nextToken());
    }
}

for (int i = 0; i < N; i++) {
    System.out.println(Arrays.toString(input[i]));
}

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

https://school.programmers.co.kr/learn/courses/30/lessons/60062?language=java