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

문제 설명

코드

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

public class sec05_01 {
    public static String solution(String str) {
        int left = 0;
        for(int i = 0; i < str.length(); ++i)
        {
            if(str.charAt(i) == '(') ++left;
            else
            {
                --left;
                if(left < 0) return "NO";
            }
        }
        return (left == 0) ? "YES" : "NO";
    }


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

설명

주어진 문자열 str의 각 문자를 순회하면서 열린 괄호 ’(’의 개수를 카운트하고, 닫힌 괄호 ’)’를 만나면 카운트를 감소시킨다. 이때, 닫힌 괄호가 열린 괄호보다 먼저 나오는 경우(즉, left < 0이 되는 경우) “NO”를 반환한다. 최종적으로, 열린 괄호와 닫힌 괄호의 개수가 일치하는지 (left == 0) 확인하여 일치하면 “YES”를 반환하고, 그렇지 않으면 “NO”를 반환한다.

• 변수 left: 열린 괄호 ’(’의 수를 카운트하는 변수이다. 닫힌 괄호 ’)’를 만나면 이 값을 감소시킨다.
• 문자 순회: 문자열의 각 문자를 순회하며, 열린 괄호를 만나면 left를 증가시키고, 닫힌 괄호를 만나면 left를 감소시킨다.
• left < 0 체크: 닫힌 괄호가 열린 괄호보다 많아지면, “NO”를 반환한다. 이는 올바른 괄호 문자열이 아니기 때문이다.
• 최종 결과: 모든 문자열을 순회한 후, left가 0이면 모든 괄호가 짝을 이루는 것이므로 “YES”를 반환하고, 그렇지 않으면 “NO”를 반환한다.

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

문제 설명

코드

package inflearn_algorithm.chapter4;

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

public class sec04_05 {
    public static int solution(int N, int K , Integer[] arr) {
        int count = 1;
        TreeSet<Integer> reverseTreeSet = new TreeSet<>(Comparator.reverseOrder());
        for(int i = 0 ; i < N - 2 ; ++i)
        {
            for(int j = i + 1 ; j < N - 1 ; ++j)
            {
                for(int k = j + 1 ; k < N ; ++k) reverseTreeSet.add(arr[i] + arr[j] + arr[k]);
            }
        }

        for(Integer i : reverseTreeSet) if(count++ == K) return i;
        return -1;
    }

    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 K = Integer.parseInt(st.nextToken());
        Integer[] arr = new Integer[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, K, arr));
    }
}

설명

• TreeSet<Integer> reverseTreeSet = new TreeSet<>(Comparator.reverseOrder());를 사용하여 내림차순으로 정렬된 트리셋을 생성한다. 트리셋은 중복된 값을 허용하지 않으며, 자동으로 정렬된 상태를 유지한다.
  
  
• 중첩된 for 루프를 사용하여 배열에서 가능한 모든 세 숫자의 조합을 순회한다.
  arr[i] + arr[j] + arr[k]를 계산하여 그 합을 트리셋에 추가한다. 이는 i, j, k가 서로 다른 인덱스여야 한다. 트리셋에 추가되면서 자동으로 중복된 합이 제거되고, 내림차순으로 정렬된다.
  
  
• 트리셋의 요소들을 순회하면서, count 변수를 증가시킨다. count가 K와 같아지는 순간 해당 값을 반환한다.
  만약 K번째로 큰 값을 찾지 못하면 -1을 반환한다.

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

문제 설명

코드

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

public class sec04_04 {
    public static int solution(String S, String T) {
        int count = 0;
        HashMap<Character, Integer> sMap = new HashMap<>();
        HashMap<Character, Integer> tMap = new HashMap<>();

        for (char c : T.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1); //T를 관리하는 맵 초기화
        for (int i = 0; i < T.length() - 1; ++i) sMap.put(S.charAt(i), sMap.getOrDefault(S.charAt(i), 0) + 1); //S를 관리하는 맵 초기화

        int lPtr = 0;
        for (int rPtr = T.length() - 1; rPtr < S.length(); ++rPtr)
        {
            sMap.put(S.charAt(rPtr), sMap.getOrDefault(S.charAt(rPtr), 0) + 1);
            if (sMap.equals(tMap)) ++count;
            sMap.put(S.charAt(lPtr), sMap.get(S.charAt(lPtr)) - 1);
            if (sMap.get(S.charAt(lPtr)) == 0) sMap.remove(S.charAt(lPtr));
            ++lPtr;
        }

        return count;
    }

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

설명

• 해시맵 초기화
  -> tMap: 문자열 T의 각 문자 빈도수를 저장.
  -> sMap: 초기 슬라이딩 윈도우에 해당하는 S의 첫 T.length() - 1 만큼의 문자 빈도수를 저장.
  
  
• 슬라이딩 윈도우 설정
  -> lPtr과 rPtr 두 개의 포인터를 사용하여 윈도우를 이동시키면서 S의 각 부분 문자열을 탐색한다.
  -> rPtr이 가리키는 문자를 sMap에 추가하고, lPtr이 가리키는 문자의 빈도수를 감소시키며 윈도우를 한 칸 오른쪽으로 이동한다.
  -> sMap과 tMap이 동일한지 비교하여, 같으면 애너그램이므로 count를 증가시킨다.
  
  
• 마지막으로 애너그램의 수를 의미하는 count를 반환한다.

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

문제 설명

코드

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

public class sec04_03 {
    public static int[] solution(int[] arr, int K) {
        int[] result = new int[arr.length - K + 1];
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < K; i++) map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        result[0] = map.size();

        int lPtr = 0;
        for (int rPtr = K; rPtr < arr.length; ++rPtr)
        {
            map.put(arr[rPtr], map.getOrDefault(arr[rPtr], 0) + 1);
            map.put(arr[lPtr], map.get(arr[lPtr]) - 1);
            if (map.get(arr[lPtr]) == 0) map.remove(arr[lPtr]);
            ++lPtr;
            result[rPtr - K + 1] = map.size();
        }

        return result;
    }

    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 K = 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());
        for (int i : solution(arr, K)) System.out.print(i + " ");
    }
}

설명

• 해시맵과 슬라이딩 윈도우 알고리즘을 사용한다.
• 배열의 처음 K개 원소를 HashMap에 추가하여 각 원소의 빈도를 기록하고, 첫 번째 결과를 result[0]에 저장한다.
• 왼쪽 포인터(lPtr)와 오른쪽 포인터(rPtr)를 사용하여 윈도우를 한 칸씩 이동한다.
• 오른쪽 포인터가 가리키는 새로운 원소를 HashMap에 추가하고, 왼쪽 포인터가 가리키는 원소를 제거하여 HashMap을 업데이트한다.
• 현재 HashMap의 크기를 result 배열에 저장한다.

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

문제 설명

코드

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

public class sec04_02 {
    public static String solution(String str1, String str2)
    {
        if(str1.length() != str2.length()) return "NO";
        HashMap<Character, Integer> map1 = new HashMap();
        HashMap<Character, Integer> map2 = new HashMap();
        
        for(int i = 0; i < str1.length(); ++i)
        {
            map1.put(str1.charAt(i), map1.getOrDefault(str1.charAt(i), 0) + 1);
            map2.put(str2.charAt(i), map2.getOrDefault(str2.charAt(i), 0) + 1);
        }

        for(char c : map1.keySet()) if(!(map2.containsKey(c) && (map2.get(c).equals(map1.get(c))))) return "NO";

        return "YES";
    }

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

설명

• str1과 str2의 길이가 다르면, “NO”를 반환하여 아나그램이 아님을 바로 확인할 수 있다.
  
  
• HashMap<Character, Integer> map1와 HashMap<Character, Integer> map2를 사용하여 각 문자열의 문자를 카운팅한다.
  각 문자는 map1과 map2에 저장되며, 이미 존재하는 문자일 경우 값을 증가시킨다.
  
  
• map1의 각 키(문자)를 순회하면서, map2에 해당 키가 있는지 확인하고, 그 키에 대한 값(문자의 개수)이 동일한지 비교한다.
  조건에 맞지 않으면 “NO”를 반환한다.
  
  
• 모든 조건을 만족하면 “YES”를 반환하여 두 문자열이 아나그램임을 나타낸다.

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

문제 설명

코드

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

public class sec04_01 {
    public static char solution(String str) {
        HashMap<Character, Integer> map = new HashMap<>();
        char result = 0;
        int max = 0;

        for (char c : str.toCharArray())
        {
            int count = map.getOrDefault(c, 0) + 1;
            map.put(c, count);

            if (count > max)
            {
                max = count;
                result = c;
            }
        }

        return result;
    }

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

설명

• map.getOrDefault(c, 0)는 map에서 문자 c의 현재 값(value)을 가져오며, 만약 map에 c가 없으면 기본값 0을 반환
• map의 각 키를 순회하면서 가장 큰 빈도(max)를 찾고, 그에 해당하는 문자를 result에 저장

Map의 주요 메서드

put(K key, V value) 지정된 키와 값을 맵에 추가하거나, 키가 이미 존재하면 그 값을 갱신

get(Object key) 지정된 키에 대응하는 값을 반환한다. 키가 없으면 null을 반

getOrDefault(Object key, V defaultValue) 지정된 키에 대응하는 값을 반환한다. 키가 없으면 기본값을 반환

containsKey(Object key) 맵에 지정된 키가 존재하는지 확인

containsValue(Object value) 맵에 지정된 값이 존재하는지 확인

remove(Object key) 지정된 키와 그에 대응하는 값을 맵에서 제거

size() 맵에 저장된 키-값 쌍의 개수를 반환

isEmpty() 맵이 비어 있는지 확인 clear() 맵의 모든 키-값 쌍을 제거

keySet() 맵에 있는 모든 키를 Set 형태로 반환

Set<String> keys = map.keySet();  // keys는 ["apple"]​

values() 맵에 있는 모든 값을 Collection 형태로 반환

Collection<Integer> values = map.values();  // values는 [1]​

entrySet() 맵의 모든 키-값 쌍을 Set 형태로 반환

Set<Map.Entry<String, Integer>> entries = map.entrySet();
for (Map.Entry<String, Integer> entry : entries) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}​

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

문제 설명

코드

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

public class sec03_06 {
    public static int solution(int[] arr, int N, int K) {
        int maxLength = 0;
        int lPtr = 0, count = 0;
        for(int rPtr = 0; rPtr < N; ++rPtr)
        {
            if(arr[rPtr] == 0) ++count;
            while(count > K) if(arr[lPtr++] == 0) --count;
            if(rPtr - lPtr + 1 > maxLength) maxLength = rPtr - lPtr + 1;
        }


        return maxLength;
    }

    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 K = 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());
        System.out.println(solution(arr, N, K));
    }
}

설명

• 투 포인터와 슬라이딩 윈도우 알고리즘 사용
  -lPtr과 rPtr 두 개의 포인터를 사용하여 현재 윈도우를 관리한다.
  -count는 현재 윈도우 내에 있는 0의 개수를 저장한다.
  -rPtr을 증가시키면서 윈도우를 오른쪽으로 확장한다.
  -윈도우 내의 0의 개수가  K 를 초과하면 lPtr을 증가시켜 윈도우를 축소한다.
  -윈도우의 길이가 최대 길이를 갱신할 때마다 maxLength를 업데이트한다.
• 슬라이딩 윈도우 확장
  -배열의 시작부터 끝까지 반복 (rPtr 오른쪽 포인터를 0부터 N-1까지 이동).
  -현재 요소(arr[rPtr])가 0이면, count를 증가시킨다.
• 윈도우 축소
  -만약 count가  K 보다 커지면, 즉 윈도우 내의 0의 개수가  K 를 초과하면:
  -윈도우의 왼쪽 끝(lPtr)을 오른쪽으로 이동하여 윈도우를 축소한다.
  -만약 lPtr이 가리키는 요소가 0이면, count를 감소시킨다.
• 최대 길이 갱신
  -현재 윈도우의 길이(rPtr - lPtr + 1)가 maxLength보다 크면, maxLength를 갱신한다.

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

문제 설명

코드

첫 번째 코드(투 포인터 + 슬라이딩 윈도우)

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

public class sec03_05 {
    public static int solution(int N) {
        int count = 0, sum = 0;
        int lPtr = 0, halfPlusOne = (N / 2) + 1;
        int[] arr = new int[halfPlusOne];

        for(int i = 0; i < halfPlusOne; ++i) arr[i] = i + 1;

        for(int rPtr = 0; rPtr < halfPlusOne; ++rPtr)
        {
            sum += arr[rPtr];
            while (sum > N) sum -= arr[lPtr++];
            if(sum == N) ++count;
        }

        return count;
    }

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

두 번째 코드(수학적 접근)

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

public class sec03_05 {
    public static int solution(int N) {
        int count = 0, temp = 1;
        --N;
        while (N > 0)
        {
            N = N - (++temp);
            if(N % temp == 0) ++count;
        }

        return count;
    }

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

설명

첫 번째 코드 설명

• 투 포인터와 슬라이딩 윈도우 알고리즘을 사용한다.
• (N / 2) + 1 까지의 배열을 생성한다.
• 두 개의 포인터(lPtr, rPtr)와 합(sum)을 사용하여 연속된 수의 합을 구한다.
• sum이  N 보다 크면 lPtr을 오른쪽으로 이동시켜 sum을 줄인다.
• sum이  N 과 같아지면 경우의 수를 증가시킨다.

(N / 2) + 1 까지의 배열을 생성하는 이유는, 연속된 자연수의 합으로 숫자 N 을 표현할 때, 최소 두 개의 숫자의 합이 N 이 되어야 하기 때문이다. 이를 통해 불필요한 계산을 줄이고, 효율적으로 답을 찾을 수 있다.
1.어떤 자연수 N 을 연속된 자연수의 합으로 나타낼 때, 최소 두 개 이상의 수가 필요하다.
예를 들어, N = 15 인 경우, 최소 두 개의 연속된 수가 합쳐져서 15가 되어야 한다.

2.만약 N 이 15라면, 15 를 넘지 않으면서 연속된 수의 합으로 나타낼 수 있는 가장 큰 자연수는 15의 절반인 7.5이다. 실제로 N/2 를 넘는 숫자부터는 N 을 넘지 않으면서 연속된 자연수의 합으로 표현할 수 없다.
예를 들어, N = 15 일 때 8 이상의 수를 시작점으로 연속된 합을 만들 수 없다.

3.N/2 까지만 배열을 생성하면, 불필요한 연산을 줄일 수 있다. 예를 들어, N = 15 인 경우 N/2 = 7.5 이고, 여기에 1을 더해 8까지의 배열을 생성하면 충분하다.
따라서 halfPlusOne = (N / 2) + 1은 최적화된 범위이다.

두 번째 코드 설명

• 초기설정
  -count는 연속된 자연수의 합으로  N 을 나타낼 수 있는 방법의 수를 세는 변수이다.
  -temp는 현재 연속된 자연수의 개수를 나타내는 변수로, 초기값은 1이다.
  -N 에서 1을 뺀 값으로 시작한다.
• 루프
  -N 이 0보다 클 때까지 반복한다.
  -N 에서 temp를 증가시킨 값을 뺀다.
  -현재  N  값이 temp로 나누어 떨어지면, 연속된 자연수의 합으로  N 을 나타낼 수 있는 경우이므로 count를 증가시킨다.
• 예를 들어,  N = 15 일 때:
  -초기값:  N = 14 , temp = 1
  -첫 번째 루프:  N = 14 - 2 = 12 , temp = 2, 12 % 2 == 0 -> count = 1
  -두 번째 루프:  N = 12 - 3 = 9 , temp = 3, 9 % 3 == 0 -> count = 2
  -세 번째 루프:  N = 9 - 4 = 5 , temp = 4, 5 % 4 != 0
  -네 번째 루프:  N = 5 - 5 = 0 , temp = 5, 0 % 5 == 0 -> count = 3