본문 바로가기
코딩테스트/JAVA

[백준 JAVA] 알고리즘 재활훈련 (기초)

신동운 2025. 9. 17. 03:05

알고리즘 재활소에 있는 문제들로 알고리즘 재활훈련을 하려고한다.

 

단순한 문제는 설계를 하지 않고 최대한 빨리 푸는것을 목적으로 하려하고 한다.

 

최소, 최대

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

풀이시간 : 1분

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

public class Main {
    public static int N, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

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

        for(int i = 0; i < N; i++){
            int cur = Integer.parseInt(st.nextToken());
            min = Math.min(cur, min);
            max = Math.max(cur, max);
        }

        System.out.println(min + " " + max);

    }
}

 

단어공부

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

풀이시간 : 9분

 

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

public class Main {
    public static int max = -1;
    public static char c = '?';
    public static int[] alp = new int[26];
    public static String str;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        str = br.readLine();
        for(int i = 0; i < str.length(); i++){
            int cur = str.charAt(i) - 'A';
            if(cur > 26) cur = cur - 32;
            alp[cur]++;
        }

        for(int i = 0; i < 26; i++){
            if(max < alp[i]){
                max = alp[i];
                c = (char) (i + 'A');
            } else if (max == alp[i]){
                c = '?';
            }
        }

        System.out.println(c);

    }
}

 

괄호

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

풀이시간 : 7분

 

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

public class Main {
    public static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for(int T = 0; T < N; T++) {
            String str = br.readLine();
            int cnt = 0;
            boolean ans = true;

            for(int i = 0; i < str.length(); i++){
                char c = str.charAt(i);
                if(c == '('){
                    cnt++;
                }else{
                    if(cnt > 0){
                        cnt--;
                    } else {
                        ans = false;
                        break;
                    }
                }
            }

            if(cnt != 0){
                ans = false;
            }

            if(ans){
                System.out.println("YES");
            } else{
                System.out.println("NO");
            }

        }

    }
}

 

큐

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

풀이시간 : 8분

 

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

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

        Deque<Integer> dq = new ArrayDeque<>();

        for(int T = 0; T < N; T++) {
            st = new StringTokenizer(br.readLine());
            String order = st.nextToken();

            if(order.equals("push")){
                int a = Integer.parseInt(st.nextToken());
                dq.offer(a);
            }else if(order.equals("pop")){
                if(!dq.isEmpty()){
                    System.out.println(dq.pollFirst());
                } else{
                    System.out.println(-1);
                }
            }else if(order.equals("size")){
                System.out.println(dq.size());
            }else if(order.equals("empty")){
                if(dq.isEmpty()){
                    System.out.println(1);
                } else{
                    System.out.println(0);
                }
            }else if(order.equals("front")){
                if(!dq.isEmpty()){
                    System.out.println(dq.peekFirst());
                } else{
                    System.out.println(-1);
                }
            }else if(order.equals("back")){
                if(!dq.isEmpty()){
                    System.out.println(dq.peekLast());
                } else{
                    System.out.println(-1);
                }
            }

        }

    }
}

 

직접구현 버전

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

public class Main {
    public static int N, first = 0, last = 0;
    public static int[] q = new int[10001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());

        for(int T = 0; T < N; T++) {
            st = new StringTokenizer(br.readLine());
            String order = st.nextToken();

            switch(order) {
                case "push" :
                    int a = Integer.parseInt(st.nextToken());
                    push(a);
                    break;
                case "pop" :
                    sb.append(pop()).append("\n");
                    break;
                case "size" :
                    sb.append(size()).append("\n");
                    break;
                case "empty" :
                    sb.append(empty()).append("\n");
                    break;
                case "front" :
                    sb.append(front()).append("\n");
                    break;
                case "back" :
                    sb.append(back()).append("\n");
                    break;
            }

        }

        System.out.println(sb);

    }

    public static void push(int a) {
        q[last++] = a;
    }

    public static int pop() {
        if(last - first == 0) return -1;
        else return q[first++];
    }

    public static int size() {
        return last - first;
    }

    public static int empty() {
        if(last - first == 0) return 1;
        else return 0;
    }

    public static int front() {
        if(last - first == 0) return -1;
        else return q[first];
    }

    public static int back() {
        if(last - first == 0) return -1;
        else return q[last - 1];
    }

}

 

덱

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

풀이시간 : 7분

 

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

public class Main {
    public static int N;
    public static Deque<Integer> dq = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        int last = 0;

        for(int T = 0; T < N; T++) {
            st = new StringTokenizer(br.readLine());
            String order = st.nextToken();

            switch(order) {
                case "push_front" :
                    last = Integer.parseInt(st.nextToken());
                    dq.offerFirst(last);
                    break;
                case "push_back" :
                    last = Integer.parseInt(st.nextToken());
                    dq.offerLast(last);
                    break;
                case "pop_front" :
                    if(dq.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(dq.pollFirst()).append("\n");
                    break;
                case "pop_back" :
                    if(dq.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(dq.pollLast()).append("\n");
                    break;
                case "size" :
                    sb.append(dq.size()).append("\n");
                    break;
                case "empty" :
                    if(dq.isEmpty()) sb.append(1).append("\n");
                    else sb.append(0).append("\n");
                    break;
                case "front" :
                    if(dq.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(dq.peekFirst()).append("\n");
                    break;
                case "back" :
                    if(dq.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(dq.peekLast()).append("\n");
                    break;
            }

        }

        System.out.println(sb);

    }
}

 

직접구현

 

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

public class Main {
    public static int N, first = 0, last = 0, size = 10000;
    public static int[] dq = new int[10001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        int a = 0;

        for(int T = 0; T < N; T++) {
            st = new StringTokenizer(br.readLine());
            String order = st.nextToken();

            switch(order) {
                case "push_front" :
                    a = Integer.parseInt(st.nextToken());
                    push_front(a);
                    break;
                case "push_back" :
                    a = Integer.parseInt(st.nextToken());
                    push_back(a);
                    break;
                case "pop_front" :
                    sb.append(pop_front()).append("\n");
                    break;
                case "pop_back" :
                    sb.append(pop_back()).append("\n");
                    break;
                case "size" :
                    sb.append(size()).append("\n");
                    break;
                case "empty" :
                    sb.append(empty()).append("\n");
                    break;
                case "front" :
                    sb.append(front()).append("\n");
                    break;
                case "back" :
                    sb.append(back()).append("\n");
                    break;
            }

        }

        System.out.println(sb);

    }

    public static void push_front(int a) {
        first = (first - 1 + size) % size;
        dq[first] = a;
    }

    public static void push_back(int a) {
        dq[last] = a;
        last = (last + 1) % size;
    }

    public static int pop_front() {
        if(first == last) return -1;
        int val = dq[first];
        first = (first + 1) % size;
        return val;
    }

    public static int pop_back() {
        if(first == last) return -1;
        last = (last - 1 + size) % size;
        return dq[last];
    }

    public static int size() {
        return (last - first + size) % size;
    }

    public static int empty() {
        return (first == last) ? 1 : 0;
    }

    public static int front() {
        if(first == last) return -1;
        return dq[first];
    }

    public static int back() {
        if (first == last) return -1;
        int idx = (last - 1 + size) % size;
        return dq[idx];
    }

}

 

나는야 포켓몬 마스터 이다솜

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

풀이시간 : 8분

 

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

public class Main {
    public static int N, M;
    public static HashMap<Integer, String> number = new HashMap<>();
    public static HashMap<String, Integer> name = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        String str = "";

        for(int i = 1; i <= N; i++){
            str = br.readLine();
            number.put(i, str);
            name.put(str, i);
        }

        for(int i = 0; i < M; i++){
            str = br.readLine();
            if(str.charAt(0) >= '0' && str.charAt(0) <= '9'){
                sb.append(number.get(Integer.parseInt(str))).append("\n");
            } else{
                sb.append(name.get(str)).append("\n");
            }
        }

        System.out.println(sb);

    }
}

 

수 정렬하기

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

풀이시간 : 4분

 

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

public class Main {
    public static int N;
    public static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++){
            int a = Integer.parseInt(br.readLine());
            list.add(a);
        }

        list.sort(Integer::compareTo);

        for(int a : list){
            sb.append(a).append("\n");
        }

        System.out.println(sb);

    }
}

 

배열로 푸는법

Arrays.sort(arr);

 

시간복잡도는 다음과 같다 배열이 위에 리스트가 아래이다.

 

항상 정렬하는게 좀 헷갈리는데 한번더 정리해본다.

 

1) 배열 오름차순 정렬

 
Arrays.sort(a); // int[] 배열
  • 시간복잡도: O(N log N)
  • 내부 알고리즘:
    • int[], long[] 등 primitive 배열 → Dual-Pivot QuickSort (in-place, 불안정 정렬)
    • Integer[], String[] 등 객체 배열 → TimSort (merge + insertion hybrid, 안정 정렬)

2) 배열 내림차순 정렬

 
Arrays.sort(a); // 오름차순 정렬 for (int i = 0, j = a.length - 1; i < j; i++, j--) { int t = a[i]; a[i] = a[j]; a[j] = t; // 배열 뒤집기 }
  • 시간복잡도: O(N log N) (정렬) + O(N) (뒤집기) = O(N log N)
  • 내부 알고리즘: 위와 동일 (primitive → Dual-Pivot QuickSort)

3) 리스트 오름차순 / 내림차순

 
Collections.sort(list); // 오름차순 list.sort(Comparator.reverseOrder()); // 내림차순
  • 시간복잡도: O(N log N)
  • 내부 알고리즘: TimSort (안정 정렬)
  • 주의: ArrayList<Integer> 같은 경우 오토박싱/언박싱 비용이 발생 (배열보다 느림).

4) 사용자 정의 비교 (리스트 전용)

 
list.sort( Comparator.<Integer>comparingInt(Math::abs) .thenComparingInt(x -> x) );
  • 시간복잡도: O(N log N) (비교 함수 호출이 추가되므로 상수 시간은 커짐)
  • 내부 알고리즘: TimSort
  • 활용 예시: 절댓값 기준 오름차순 정렬, 절댓값 같으면 원래 값 기준 오름차순

5) 2차원 배열 정렬 (예: (x, y) 오름차순)

 
Arrays.sort(points, (p1, p2) -> { if (p1[0] != p2[0]) return Integer.compare(p1[0], p2[0]); return Integer.compare(p1[1], p2[1]); });
  • 시간복잡도: O(N log N)
  • 내부 알고리즘: TimSort (객체 배열)
  • 활용 예시: 좌표 정렬, (x좌표 기준 → 같으면 y좌표 기준)

6) 병렬 정렬

 
Arrays.parallelSort(a); // int[] 배열
  • 시간복잡도: 평균 O(N log N)
  • 내부 알고리즘: 병렬 Merge Sort 기반
  • 특징: 멀티코어 활용, 큰 배열에서만 이득 → 작은 배열에서는 오히려 Arrays.sort보다 느릴 수 있음.

✅ 정리: 어떤 정렬을 쓰면 좋을까?

자료구조코드정렬 알고리즘시간복잡도안정성
int[] (기본형 배열) Arrays.sort(a) Dual-Pivot QuickSort O(N log N) ❌ 불안정
Integer[], String[] (객체 배열) Arrays.sort(a) TimSort O(N log N) ✅ 안정
ArrayList<Integer> Collections.sort(list) TimSort O(N log N) ✅ 안정
ArrayList<Integer> 내림차순 list.sort(Comparator.reverseOrder()) TimSort O(N log N) ✅ 안정
2D 배열 Arrays.sort(points, comp) TimSort O(N log N) ✅ 안정
병렬 정렬 Arrays.parallelSort(a) 병렬 Merge Sort O(N log N) ❌ 불안정

 

수 찾기

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

풀이시간 : 5분

 

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

public class Main {
    public static int N, M;
    public static HashSet<Integer> set = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            int a = Integer.parseInt(st.nextToken());
            set.add(a);
        }

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < M; i++){
            int a = Integer.parseInt(st.nextToken());
            if(set.contains(a)){
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }

        System.out.println(sb);

    }
}

 

예전에 풀었던 방식을 보았는데 이분탐색으로 풀었었다.

 

뭐 당연히 Hashset 을 사용하는 방식이 더 빠르지만 이 방법도 가능하니 올려본다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

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

        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int cur = Integer.parseInt(st.nextToken());
            System.out.println(bs(arr, cur));
        }
    }

    public static int bs(int[] arr, int key) {
        int lo = 0;
        int hi = arr.length -1;
        while(lo <= hi) {
            int mid = (lo+hi) / 2;
            if(key < arr[mid]) {
                hi = mid-1;

            }else if(key > arr[mid]) {
                lo = mid + 1;
            } else {
                return 1;
            }
        }

        return 0;
    }
}

 

N과 M(1)

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

풀이시간 : 4분

 

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

public class Main {
    public static int N, M;
    public static int[] arr, visited;
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];
        visited = new int[N + 1];

        dfs(0);

        System.out.println(sb);

    }
    public static void dfs(int depth){
        if(depth == M){
            for(int a : arr){
                sb.append(a).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i = 1; i <= N; i++){
            if(visited[i] == 1) continue;
            visited[i] = 1;
            arr[depth] = i;
            dfs(depth  + 1);
            visited[i] = 0;
        }
    }
}

 

구간 합 구하기 4

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

풀이시간 : 6분

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

public class Main {
    public static int N, M;
    public static long[] arr;
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new long[N + 1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++){
            int x = Integer.parseInt(st.nextToken());
            arr[i] = arr[i - 1] + x;
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            sb.append(arr[r] - arr[l - 1]).append("\n");
        }

        System.out.println(sb);
    }
}

 

 

두 수의 합

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

풀이시간: 9분

 

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

public class Main {
    public static int N, X, ans = 0;
    public static int[] arr;
    public static HashSet<Integer> set = new HashSet<>();
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            int a = Integer.parseInt(st.nextToken());
            set.add(a);
            arr[i] = a;
        }

        X = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++){
            int cur = X - arr[i];
            if(cur <= 0) continue;
            if(set.contains(cur)) ans++;
        }

        sb.append(ans / 2);

        System.out.println(sb);
    }
}

 

뭔가 야매로 푼 느낌이라 다른 풀이를 찾아봤다.

 

이 문제에서는 서로 다른 수만 주어지기 때문에 이 방법으로도 풀이가 가능하지만 만약 서로 다른 수라는 조건이 없다면 투포인터를 고려해봐야 한다.

 

투 포인터 풀이

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

public class Main {
    public static int N, X, ans = 0;
    public static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        X = Integer.parseInt(br.readLine());
        Arrays.sort(arr);
        int l = 0, r = N - 1, cnt = 0;

        while(l < r){
            int sum = arr[l] + arr[r];
            if(sum == X) {
                cnt++;
                l++;
                r--;
            } else if(sum < X){
                l++;
            } else{
                r--;
            }
        }

        System.out.println(cnt);
    }
}

 

위에가 투포인터 풀이 아래가 HashSet 을 이용한 풀이 투포인터가 조금 빠른것을 알 수 있다.

 

 

 

DFS 와 BFS

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

풀이시간 : 15분

 

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

public class Main {
    public static int N, M, V;
    public static List<Integer>[] list;
    public static int[] visited;
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        visited = new int[N + 1];
        
        list = new List[N + 1];
        for(int i = 1; i <= N; i++) list[i] = new ArrayList<>();

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            list[v1].add(v2);
            list[v2].add(v1);
        }

        for(int i = 1; i <= N; i++) Collections.sort(list[i]);

        dfs(V);

        sb.append("\n");

        bfs();

        System.out.println(sb);
    }

    public static void dfs(int cur){
        visited[cur] = 1;
        sb.append(cur).append(" ");
        for(int a : list[cur]){
            if(visited[a] == 1) continue;
            dfs(a);
        }
    }

    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(V);
        visited[V] = 0;
        
        while(!q.isEmpty()){
            int cur = q.poll();
            sb.append(cur).append(" ");
            for(int a : list[cur]){
                if(visited[a] == 0) continue;
                visited[a] = 0;
                q.offer(a);
            }
        }
    }
}

 

아직도 어렵다 빨리 짜기가

 

에디터

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

풀이시간 : 13분

 

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

public class Main {
    public static int M;
    public static Deque<Character> left, right;
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        sb = new StringBuilder();

        left = new ArrayDeque<>();
        right = new ArrayDeque<>();

        String str = br.readLine();
        for(int i = 0; i < str.length(); i++){
            left.offerLast(str.charAt(i));
        }

        M = Integer.parseInt(br.readLine());
        char tmp;
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            char order = st.nextToken().charAt(0);
            switch (order){
                case 'L' :
                    if(left.isEmpty()) continue;
                    tmp = left.pollLast();
                    right.offerFirst(tmp);
                    break;
                case 'D' :
                    if(right.isEmpty()) continue;
                    tmp = right.pollFirst();
                    left.offerLast(tmp);
                    break;
                case 'B' :
                    if(left.isEmpty()) continue;
                    left.pollLast();
                    break;
                case 'P' :
                    tmp = st.nextToken().charAt(0);
                    left.offerLast(tmp);
                    break;
            }
        }
        int size = left.size();
        for(int i = 0; i < size; i++){
            sb.append(left.pollFirst());
        }
        size = right.size();
        for(int i = 0; i < size; i++){
            sb.append(right.pollFirst());
        }

        System.out.println(sb);
    }
}

 

최대힙

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

풀이시간 : 4분

 

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

public class Main {
    public static int N;
    public static PriorityQueue<Integer> pq;
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));

        for(int i = 0; i < N; i++){
            int tmp = Integer.parseInt(br.readLine());
            if(tmp == 0){
                if(pq.isEmpty()) sb.append(0).append("\n");
                else sb.append(pq.poll()).append("\n");
            } else if (tmp > 0){
                pq.offer(tmp);
            }
        }

        System.out.println(sb);
    }
}

 

 

 

1로 만들기

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

풀이시간 : 12분

 

범위를 착각해 찾는데 오래걸렸다.

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

public class Main {
    public static int N, ans = 0;
    public static int[] visited = new int[1000001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        bfs();

        System.out.println(ans);
    }
    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        visited[N] = 1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                int cur = q.poll();

                if(cur == 1) return;

                if(cur % 3 == 0 && visited[cur / 3] == 0) {
                    visited[cur / 3] = 1;
                    q.offer(cur / 3);
                }
                if(cur % 2 == 0 && visited[cur / 2] == 0) {
                    visited[cur / 2] = 1;
                    q.offer(cur / 2);
                }
                if(cur - 1 > 0 && visited[cur - 1] == 0) {
                    visited[cur - 1] = 1;
                    q.offer(cur - 1);
                }
            }

            ans++;
        }
    }
}

 

 

저작자표시 비영리 변경금지 (새창열림)

'코딩테스트 > JAVA' 카테고리의 다른 글

[백준 JAVA] 3190번: 뱀  (0) 2025.09.23
[백준 JAVA] 알고리즘 재활훈련 (심화)  (0) 2025.09.19
[백준 JAVA] 회귀한 프로그래머의 최소신장트리 다시풀기  (0) 2025.09.16
[백준 JAVA] 회귀한 프로그래머의 BFS 다시풀기  (0) 2025.09.11
[백준 JAVA] 회귀한 프로그래머의 그래프 1 다시풀기  (0) 2025.09.05

'코딩테스트/JAVA' Related Articles

티스토리툴바