난이도: ★★☆☆☆ • solved on: 2026-01-20

문제 요약

• 문제 유형: 백트래킹(Backtracking), 순열
• 요구사항: 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 모든 순열을 출력해야 한다.

사용 개념

1. 자료구조

   • int[] : 현재 선택된 수열을 저장
   • boolean[] : 숫자 사용 여부(중복 방지) 체크
   • StringBuilder : 출력 성능 최적화

2. 알고리즘/기법

   • 재귀 (recursion)
   • 백트래킹 (backtracking)

3. 핵심 키워드

   • 순열 (permutation)
   • 깊이 (depth)
   • 상태 복원 (backtracking)

풀이 아이디어

1. 문제 분해

• 길이가 M인 수열을 만든다.
• 각 자리에 1부터 N까지의 숫자를 하나씩 시도한다.
• 이미 사용한 숫자는 다시 사용할 수 없다.
• 길이가 M이 되면 하나의 완성된 순열로 출력한다.

2. 재귀 함수의 목적 정의 (핵심)

sequence(n, depth)의 역할

• depth == M → 길이 M의 수열이 완성되었으므로 출력하고 종료한다.
• 그렇지 않으면 → 1부터 N까지 순회하면서 아직 사용하지 않은 숫자를 선택한다.

3. 핵심 로직 흐름

sequence(depth):
    if depth == M:
        수열 출력
        return
>
    for i = 1 to N:
        if i가 아직 사용되지 않았다면:
            i를 선택
            sequence(depth + 1)
            i 선택 취소 (상태 복원)

4. 백트래킹의 본질

• 선택: visited[i] = true, tempArr[depth] = i
• 재귀 호출: 다음 자리로 이동
• 복원: visited[i] = false

코드

import java.util.*;

class Main {
    public static int[] tempArr;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int r = sc.nextInt();

        tempArr = new int[r];
        visited = new boolean[n + 1];

        sequence(n, 0);
        System.out.println(sb);
    }

    public static void sequence(int n, int depth) {
        if (depth == tempArr.length) {
            for (int i = 0; i < tempArr.length; i++) {
                sb.append(tempArr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tempArr[depth] = i;
                sequence(n, depth + 1);
                visited[i] = false; // 상태 복원
            }
        }
    }
}

시간·공간 복잡도

• 시간 복잡도: O(N! / (N−M)!)
• 공간 복잡도: O(N + M)

어려웠던 점

• 재귀를 사용해야 한다는 것은 알았지만 재귀 함수 하나가 정확히 무엇을 책임지는지를 정의하지 못해 접근이 어려웠다.
• “이 함수가 한 번 호출될 때 정확히 무엇을 결정하는가”를 잡지 못해 로직을 외부 설명에 의존하게 되었다.

배운 점 및 팁

• 재귀 문제에서는 반드시 “이 함수는 어떤 단위의 문제를 해결하는가”를 먼저 문장으로 정의해야 한다.
• 백트래킹은 선택 → 재귀 → 복원 이 3단계가 항상 세트로 움직인다.
• 순열/조합 문제에서 depth는 현재까지 몇 개를 골랐는지를 의미하는 지표로 이해하면 훨씬 명확해진다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/15649
• 참고 자료: https://velog.io/@gayeong39/백트래킹-알고리즘-BackTracking

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 15650번 N과 M (2)
  • 백준 - 15651번 N과 M (3)

• 확장 문제 (GPT 추천)

  • 백준 - 9742번 순열
  • 백준 - 6603번 중복 없는 조합

난이도: ★★★☆☆ • solved on: 2026-01-19

문제 요약

• 문제 유형: 재귀, 분할 정복
• 요구사항: 크기 N의 정사각형에 대해 중앙이 비어 있는 별 패턴을 재귀적으로 출력해야 한다.

사용 개념

1. 자료구조

   • List<String> : 각 줄을 문자열 단위로 관리

2. 알고리즘/기법

   • 재귀 (Recursion)
   • 분할 정복 (Divide and Conquer)

3. 핵심 키워드

   • 패턴 생성 (pattern generation)
   • 재귀적 구조 (recursive structure)

풀이 아이디어

1. 문제 분해

• N이 1일 때는 "*" 하나로 종료되는 기저 조건을 둔다.
• N이 1보다 클 경우, 크기 n/3의 별 패턴을 먼저 만든다.
• 만들어진 작은 패턴을 이용해
  • 위: ***
  • 중간: * *
  • 아래: *** 형태로 결합한다.

2. 핵심 로직 흐름

   getStars(n):
       if n == 1:
           return ["*"]
   >
       small = getStars(n / 3)
   >
       for s in small:
           add s + s + s
   >
       for s in small:
           add s + blank + s
   >
       for s in small:
           add s + s + s

3. 예외 처리
   • n == 1 인 경우 바로 리스트를 반환하여 재귀를 종료한다.

코드

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> result = getStars(n);
        StringBuilder sb = new StringBuilder();
        for(String s : result) {
            sb.append(s).append("\n");
        }
        System.out.println(sb);
    }

    public static List<String> getStars(int n) {

        List<String> result = new ArrayList<>();

        if(n == 1) {
            result.add("*");
            return result;
        }

        List<String> smallStars = getStars(n / 3);
        for(String s : smallStars) {
            result.add(s + s + s);
        }

        String blank = "";
        for(int i = 0; i < n / 3; i++){
            blank += " ";
        }

        for(String s : smallStars) {
            result.add(s + blank + s);
        }

        for(String s : smallStars) {
            result.add(s + s + s);
        }
        return result;
    }
}

시간·공간 복잡도

• 시간 복잡도: O(N²)

  • 최종적으로 N×N 크기의 별 패턴을 생성해야 하므로 출력량 자체가 O(N²)이다.

• 공간 복잡도: O(N²)

  • 모든 줄을 문자열로 저장하는 리스트 때문이며, 재귀 호출 스택은 O(log₃N) 수준이다.

어려웠던 점

• 처음에 접근 자체가 되지 않았다.
• 재귀를 쓰는 것은 알겠지만, 반환 타입을 String, List<String>, String[][] 중에서 무엇으로 할지 결정하지 못해 설계 단계에서 막혔다.
• 결국 재귀 함수의 역할을 n 크기의 패턴 전체를 반환한다로 명확히 정의하면서 해결할 수 있었다. (int로 받고 List<String>으로 리턴하기)

배운 점 및 팁

• 재귀 문제에서는 함수의 역할을 한 문장으로 정의하는 것이 매우 중요하다.

  • 재귀 함수는 유닛 단위로 반복하는 것이기 때문

  • 예: getStars(n)은 n 크기의 별 패턴을 문자열 리스트로 반환한다

• 출력 형태가 줄 단위로 고정되어 있다면 List<String>이 매우 자연스럽다.

• 중앙을 비우는 문제는 대부분 3등분 구조를 가지므로, 먼저 작은 패턴을 만든 뒤 조합하는 방식이 핵심이다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2447
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 4779번 칸토어 집합
  • 백준 - 10993번 별 찍기 - 18

• 확장 문제 (GPT 추천)

  • 백준 - 10991번 별 찍기 - 16
  • 백준 - 10997번 별 찍기 - 22

난이도: ★★☆☆☆ • solved on: 2026-01-17

문제 요약

• 문제 유형: 문자열 처리, 정렬, 해시

• 요구사항:

  • 길이가 M 이상인 단어만 대상으로 한다

  • 단어를 다음 기준으로 정렬해야 한다

    1. 자주 나오는 단어일수록 앞에 온다
    2. 길이가 긴 단어일수록 앞에 온다
    3. 사전 순으로 앞서는 단어일수록 앞에 온다

사용 개념

1. 자료구조

   • HashMap<String, EnglishWord> : 단어별 등장 횟수 저장
   • List<EnglishWord> : 정렬을 위한 리스트

2. 알고리즘/기법

   • 해시를 이용한 빈도 카운팅
   • Comparable 구현을 통한 커스텀 정렬
   • 스트림 정렬 (stream().sorted())

3. 핵심 키워드

   • 빈도 기반 정렬 (frequency sort)
   • 다중 조건 정렬 (multi-level sort)

풀이 아이디어 및 코드

방법 1 : Custom Comparator

1. 문제 분해

• 단어를 입력받으며 길이가 M 미만이면 무시한다
• HashMap에 단어를 key로, 등장 정보를 value로 저장한다
• 이미 등장한 단어면 횟수만 증가시킨다

2. 정렬 전략
   • EnglishWord 클래스에서 Comparable을 구현한다
   • 정렬 기준
     1. 등장 횟수 오름차순
     2. 단어 길이 오름차순
     3. 사전 역순

   • Collections.reverseOrder()로 전체 정렬 결과를 뒤집는다
3. 출력
   • 정렬된 리스트를 순회하며 단어만 출력한다

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] cmds = br.readLine().split(" ");
        int n = Integer.parseInt(cmds[0]);
        int m = Integer.parseInt(cmds[1]);

        HashMap<String, EnglishWord> map = new HashMap<>();

        for(int i = 0; i < n; i++) {
            String word = br.readLine();
            if(word.length() < m) continue;

            if(!map.containsKey(word)) {
                map.put(word, new EnglishWord(word));
            } else {
                map.get(word).updateCnt();
            }
        }

        List<EnglishWord> list = map.values().stream()
                .sorted(Collections.reverseOrder())
                .toList();

        StringBuilder sb = new StringBuilder();
        for(EnglishWord word : list) {
            sb.append(word.word).append("\n");
        }

        System.out.println(sb);
    }

    static class EnglishWord implements Comparable<EnglishWord> {
        String word;
        int cnt;

        public EnglishWord(String word) {
            this.word = word;
            this.cnt = 1;
        }

        @Override
        public int compareTo(EnglishWord anotherWord){
            if(cnt - anotherWord.cnt != 0){
                return cnt - anotherWord.cnt;
            }
            if(word.length() - anotherWord.word.length() != 0){
                return word.length() - anotherWord.word.length();
            }
            return -1 * word.compareTo(anotherWord.word);
        }

        public void updateCnt(){
            cnt++;
        }
    }
}

방법 2 : Custom Class 없이 Comparator 활용

1. 개선 포인트

• 별도의 클래스를 만들지 않는다
• 정렬 기준을 Comparator 체이닝으로 한눈에 드러낸다
• reverseOrder()를 쓰지 않아도 된다

2. 정렬 기준 명시
   • 빈도 내림차순
   • 길이 내림차순
   • 사전 오름차순

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

class Main {
    public static void main(String[] args) throws Exception {
        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());

        Map<String, Integer> map = new HashMap<>();

        for(int i = 0; i < n; i++) {
            String word = br.readLine();
            if(word.length() < m) continue;
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        List<String> result = map.keySet().stream()
                .sorted((a, b) -> {
                    if(map.get(a) != map.get(b))
                        return map.get(b) - map.get(a);
                    if(a.length() != b.length())
                        return b.length() - a.length();
                    return a.compareTo(b);
                })
                .toList();

        StringBuilder sb = new StringBuilder();
        for(String w : result) sb.append(w).append("\n");
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

어려웠던 점

• HashMap의 value 객체들을 기준에 맞게 정렬하려다 보니 클래스를 만들고 Comparable을 구현하는 과정이 길어졌다

배운 점 및 팁

• 정렬 기준이 명확한 문제는 Comparator가 가독성이 더 좋다
• Comparable + reverseOrder() 방식은 기준이 많아질수록 직관성이 떨어질 수 있다
• 단순 빈도 문제는 Map<String, Integer> 구조만으로도 충분하다

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/20920
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 1302반 베스트셀러
  • 백준 - 11536번 줄 세우기

• 확장 문제 (GPT 추천):

  • 백준 - 1181번 단어 정렬

난이도: ★★☆☆☆ • solved on: 2026-01-17

문제 요약

• 문제 유형: 정렬, 구현, 해시/카운팅
• 요구사항: N개의 정수에 대해 산술평균(반올림), 중앙값, 최빈값, 범위를 출력해야 한다.

사용 개념

1. 자료구조

   • 방법 1: int[], HashMap<Integer,Integer>, ArrayList<Integer>
   • 방법 2: int[] count (8001) 카운팅 배열

2. 알고리즘/기법

   • 방법 1: 정렬 + 해시맵 빈도
   • 방법 2: 카운팅 (Counting) + 누적합 스캔

3. 핵심 키워드

   • 반올림 (rounding)
   • 최빈값 tie-breaking (동률 시 두 번째로 작은 값)
   • 값 범위 고정 (-4000~4000)

풀이 아이디어 및 코드

방법 1 : HashMap + 정렬

1. 문제 분해

• 입력을 받으면서 min, max, total을 갱신한다.
• HashMap으로 각 수의 빈도를 센다.
• 최빈값 후보를 ArrayList에 모은 뒤 정렬로 규칙(두 번째로 작은 값)을 맞춘다.
• arr를 정렬해 중앙값을 구한다.

2. 핵심 로직 흐름

   입력:
       min/max/total 갱신
       map[num]++
   >
   map 순회:
       최대 빈도 cnt 갱신
       cnt와 같으면 후보 추가
       cnt보다 크면 후보 초기화 후 추가
   >
   arr 정렬 -> 중앙값
   후보 정렬 -> 최빈값 결정(두 번째로 작은 값)

3. 예외 처리
   • 평균은 Math.round(1.0 * total / n) 형태로 반올림한다.

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

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

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int total = 0;
        int freq = 4001;
        int cnt = 0;
        ArrayList<Integer> arrayList = new ArrayList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] arr = new int[n];
        map.put(freq, -1);

        for(int i = 0; i < n; i++){
            int temp =  Integer.parseInt(br.readLine());
            if(temp < min) min = temp;
            if(temp > max) max = temp;

            total += temp;

            if(map.containsKey(temp)){
                map.put(temp,map.get(temp)+1);
            } else {
                map.put(temp,1);
            }
            arr[i] = temp;
        }
        for(Integer key : map.keySet()){
            if(map.get(key).equals(-1)){
                continue;
            }
            if(map.get(key).equals(cnt)){
                arrayList.add(key);
            }
            if(map.get(key).compareTo(cnt)>0){
                arrayList.clear();
                arrayList.add(key);
                cnt = map.get(key);
            }
        }
        Arrays.sort(arr);
        arrayList.sort(Collections.reverseOrder());
        System.out.println(Math.round(1.0 * total / n));
        System.out.println(arr[n/2]);
        if(arrayList.size() == 1){
            System.out.println(arrayList.get(0));
        } else {
            System.out.println(arrayList.get(arrayList.size()-2));
        }
        System.out.println(max-min);
    }
}

방법 2 : 카운팅 배열로 동시 처리

1. 문제 분해

• 값 범위가 -4000 ~ 4000으로 고정이므로 count[8001]로 빈도를 센다(인덱스는 x + 4000).
• 평균: sum / n을 Math.round로 반올림한다.
• 중앙값: 누적 빈도가 (n+1)/2 이상이 되는 지점을 찾는다(문제에서 N은 홀수).
• 최빈값: 최대 빈도를 찾은 뒤, 오름차순 스캔 중 최빈값을 만나는 두 번째 값을 답으로 한다(동률 규칙 충족).
• 범위: max - min을 출력한다.

2. 핵심 로직 흐름

   입력:
       sum, min, max 갱신
       count[x+4000]++
   >
   median:
       누적합 >= (n+1)/2 되는 최초 값
   >
   mode:
       maxFreq 구함
       i=0..8000 오름차순으로 스캔하며
           count[i]==maxFreq 인 값을 발견할 때마다 found++
           found==1이면 mode=값
           found==2이면 mode=값(두 번째로 작은 값)로 확정

3. 예외 처리
   • 평균 반올림은 음수도 포함하므로 Math.round((double)sum / n)으로 처리한다.

import java.io.*;

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

        int[] count = new int[8001]; // -4000~4000 => +4000 shift
        long sum = 0;

        int min = 4001;
        int max = -4001;

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine());
            sum += x;
            if (x < min) min = x;
            if (x > max) max = x;
            count[x + 4000]++;
        }

        // 1) 산술평균
        int mean = (int) Math.round((double) sum / n);

        // 2) 중앙값 (N은 홀수)
        int target = (n + 1) / 2;
        int cumulative = 0;
        int median = 0;
        for (int i = 0; i < 8001; i++) {
            cumulative += count[i];
            if (cumulative >= target) {
                median = i - 4000;
                break;
            }
        }

        // 3) 최빈값 (여러 개면 두 번째로 작은 값)
        int maxFreq = 0;
        for (int i = 0; i < 8001; i++) {
            if (count[i] > maxFreq) maxFreq = count[i];
        }

        int mode = 0;
        int found = 0;
        for (int i = 0; i < 8001; i++) {
            if (count[i] == maxFreq) {
                mode = i - 4000;
                found++;
                if (found == 2) break; // 두 번째로 작은 최빈값 확정
            }
        }

        // 4) 범위
        int range = max - min;

        StringBuilder sb = new StringBuilder();
        sb.append(mean).append('\n');
        sb.append(median).append('\n');
        sb.append(mode).append('\n');
        sb.append(range).append('\n');
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N log N) (정렬)
• 공간 복잡도: O(N) (배열 + 맵/리스트)

방법 2

• 시간 복잡도: O(N + K) (K=8001 고정) → 사실상 O(N)
• 공간 복잡도: O(K) → 사실상 O(1)

어려웠던 점

• 최빈값을 어떻게 저장하고 찾아낼지에 대해 골머리를 앓았다 처음 접근 (방법1)에서는 따로 HashMap을 저장하여 cnt를 확인했는데 나중 접근을 통해 카운팅 배열을 활용해볼 수 있다는 걸 확인했다.

배운 점 및 팁

• 값의 범위가 작고 고정이면 HashMap정렬보다 카운팅 배열이 구현도 단순하고 성능도 안정적이다.
• 최빈값 동률 규칙은 정렬 후 두 번째를 요구하므로, 오름차순 스캔 중 두 번째로 만나는 최빈값을 고르는 방식이 가장 안전하다. (시간 복잡도는 증가하나, 공간복잡도는 간결하다)
• 평균 반올림은 음수도 포함하므로 Math.round((double)sum / n)처럼 double로 변환해 처리하는 편이 명확하다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2108
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 10989번 수 정렬하기 3
  • 백준 - 2587번 대표값2
  • 백준 - 2592번 최빈수 구하기

• 확장 문제 (GPT 추천):

  • 백준 - 11650번 좌표 정렬하기
  • Hackerrank - Day 0: Mean, Median, and Mode

난이도: ★☆☆☆☆ • solved on: 2026-01-15

문제 요약

• 문제 유형: 수학, 약수 성질
• 요구사항: 어떤 수 (N)의 진짜 약수들(1과 (N) 제외)이 주어질 때, (N)을 구해야 한다.

사용 개념

1. 자료구조

   • 입력 순회(최솟값/최댓값 갱신)

2. 알고리즘/기법

   • 약수의 짝(pair) 성질 이용

3. 핵심 키워드

   • 약수 쌍(divisor pair), 최소/최대 약수

풀이 아이디어

왜 최소 약수 × 최대 약수 = N 이 되는가?

핵심은 약수는 항상 쌍으로 존재한다는 성질이다.

• 어떤 수 $N$에 대해 약수 $d$가 있으면, 항상 $N/d$도 약수이다.
• 따라서 약수들은 $(d, N/d)$ 형태의 짝으로 묶인다.
• 이때 각 짝의 곱은 항상 ($d \times (N/d) = N$) 이다.

코드

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

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

        long max = Long.MIN_VALUE;
        long min = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            long temp = Long.parseLong(st.nextToken());
            if (temp > max) max = temp;
            if (temp < min) min = temp;
        }

        System.out.println(min * max);
    }
}

시간·공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

어려웠던 점

• 왜 최소 약수와 최대 약수를 곱하면 원래 수 N이 되는지 직관적으로 이해가 안됐다. 하지만 테스트 케이스를 기준으로 규칙성을 찾아 이해는 안되지만 구현하니 됐다.
• “약수는 쌍으로 묶이고, 가장 작은 약수의 짝이 가장 큰 약수”라는 연결이 바로 떠오르지 않았다.

배운 점 및 팁

• 약수 문제는 대부분 짝(pair) 성질을 떠올리면 식이 단순해진다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1037
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 - 2501번 약수 구하기
  • 백준 - 9506번 약수들의 합

• 확장 문제 (GPT 추천) :

  • 백준 - 2609번 최대공약수와 최소공배수
  • 백준 - 3036번 링

난이도: ★★☆☆☆ • solved on: 2026-01-13

문제 요약

• 문제 유형: 자료구조(Queue/Stack), 시뮬레이션 최적화
• 요구사항: 주어진 type(0=queue, 1=stack)과 초기 값들로 구성된 구조에 대해, 입력 m개를 순서대로 넣고 최종적으로 빠져나오는 값을 출력해야 한다.

사용 개념

1. 자료구조

   • Deque : 앞/뒤 삽입·삭제가 O(1)

2. 알고리즘/기법

   • 불필요한 시뮬레이션 제거

3. 핵심 키워드

   • queue만 결과에 영향
   • 초기 queue 값의 “흐름”을 한 덩어리로 처리

풀이 아이디어 및 코드

방법 1 : 시뮬레이션 기반 풀이 (시간 초과로 실패)

전체를 매 입력마다 끝까지 시뮬레이션해서 m × n이 발생하는 구조라 시간 복잡도가 커진다.

Deque를 활용해 구현

//  queuestack

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

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

        int n = Integer.parseInt(br.readLine());

        ArrayList<Deque<Integer>> arr = new ArrayList<>();
        String[] types = br.readLine().split(" ");
        String[] values = br.readLine().split(" ");

        int m = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        String num = "";
        String temp = "";
        for(int i = 0; i < m; i++){
            num = st.nextToken();
            for(int j = 0; j < n; j++){
                if(types[j].equals("0")){
                    temp =  values[j];
                    values[j] = num;
                    num = temp;
                } else {
                    continue;
                }
            }

            sb.append(num+" ");
        }
        System.out.println(sb);
    }
}

배열을 활용해 구현

//  queuestack

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

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

        int n = Integer.parseInt(br.readLine());

        ArrayList<Deque<Integer>> arr = new ArrayList<>();
        int[] types = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

        int m = Integer.parseInt(br.readLine());

        StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<n;i++){
            arr.add(new ArrayDeque<>());
            types[i] = Integer.parseInt(st.nextToken());
            arr.get(i).add(Integer.parseInt(st2.nextToken()));
        }
        int num;
        for(int i = 0; i < m; i++){
            arr.get(0).add(Integer.parseInt(st3.nextToken()));
            for(int j = 0; j < n-1; j++){
                if(types[j] == 0){
                    num = arr.get(j).pollFirst();
                } else {
                    num = arr.get(j).pollLast();
                }
                arr.get(j+1).add(num);
            }

            if(types[n-1] == 0){
                num = arr.get(n-1).pollFirst();
            } else {
                num = arr.get(n-1).pollLast();
            }
            sb.append(num+" ");
        }
        System.out.println(sb);
    }
}

방법 2 : 관찰로 O(n+m) 만들기

1. stack(type=1)은 “넣고 바로 빼는 효과”만 내서 최종 출력 흐름에 남는 값이 없다.
2. queue(type=0)의 초기 값들만 결과 스트림에 영향을 준다.
3. 따라서 초기 queue 값들을 한 번에 모아두고, 매 쿼리마다 입력값 push → 맨 앞 pop만 하면 된다.

핵심 로직 흐름

q = deque()
>
// 초기 상태에서 type=0(queue)인 값만 모음
for i in 0..n-1:
    if type[i] == 0:
        q.addLast(value[i])
>
// 실제 출력은 가장 "앞에서" 빠져나오므로,
// 위에서 모은 queue 값들의 순서를 "역방향"으로 맞춰야 한다.
// (구현에서는 q에 넣는 순서를 뒤에서부터 넣거나, 앞에 addFirst로 넣는다)
>
for each x in queries:
    q.addLast(x)
    print q.pollFirst()

Java 코드

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

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

        int n = Integer.parseInt(br.readLine());
        int[] type = new int[n];
        int[] val = new int[n];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) type[i] = Integer.parseInt(st1.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) val[i] = Integer.parseInt(st2.nextToken());

        int m = Integer.parseInt(br.readLine());
        StringTokenizer st3 = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

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

        for (int i = n - 1; i >= 0; i--) {
            if (type[i] == 0) q.addFirst(val[i]);
        }

        for (int i = 0; i < m; i++) {
            int x = Integer.parseInt(st3.nextToken());
            q.addLast(x);
            sb.append(q.pollFirst()).append(' ');
        }

        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(n × m)
• 공간 복잡도: O(n)

방법 2

• 시간 복잡도: O(n + m)
• 공간 복잡도: O(n) (type=0인 값 개수만큼)

어려웠던 점

• 처음 실제 시뮬레이션 기반의 풀이에서 시간복잡도를 어떻게 더 줄여야 하는지 감이 잡히지 않았다.
• 매 쿼리마다 n개 구조를 끝까지 시뮬레이션하는 방식에서 병목이 생겼다.

배운 점 및 팁

• 전체를 그대로 시뮬레이션하지 말고, 출력에 실제로 영향을 주는 요소만 남기는 관찰이 핵심이다.
• 이 문제는 type=1(stack)이 결과 흐름에서 사라지는 요소라서, type=0(queue)만 모아 한 번에 처리하면 된다.
• Deque로 addLast / pollFirst만 하면 쿼리당 O(1)로 끝난다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/24511
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 - 12789번 도키도키 간식드리미
  • 백준 - 18258번 큐 2
  • 백준 - 10866번 덱

• 확장 문제 (GPT 추천) :

  • 백준 - 1021번 회전하는 큐
  • 백준 - 1966번 프린터 큐
  • HackerRank - Queue using Two Stacks

이 글은 딥러닝 역사에서 전환점으로 평가받는 AlexNet 논문을 읽으며, 이 모델이 왜 “작동했는가”를 정리하기 위해 작성되었습니다.

성능 비교가 아니라, 당시 기술적 제약 속에서 어떤 선택들이 문제를 해결했는지를 중심으로 살펴보고자 합니다. 또한 이 글은 Standford University의 CS231n의 일부를 참고로 하였습니다. 따라서 Computer Vision에 대해 더 궁금하신 독자께서는 링크를 참고해주세요. link

Paper Information

Title: ImageNet Classification with Deep Convolutional Neural Networks

Authors: Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton

Journal: Advances in Neural Information Processing Systems (NeurIPS 2012) link

arXiv ID: NFI

Ⅰ. Introduction

“To recognize the real world, how much capacity does a model really need?”

Ⅰ.1. 데이터 규모와 문제 복잡성

이 논문에 대한 이야기를 하기 전, 먼저 이러한 모델이 나올 수 있었고 효과가 있었던 배경에 대해 설명하려 합니다.

디지털 사진이 막 도입된 시점 (1960s), 객체 탐지 (Object Recognition)은 상당히 어려운 분야였습니다. 대상이 어디있는가? 어디까지 대상으로 할 것인가?에 대한 Vision Representation에 대한 고전적인 질문과 함께 (Stages of Visual Representation, David Marr, 1970s) 아직은 디지털 데이터에 대해 정리하고 확립하는 과정이었습니다.

그 과정에서 나온 데이터 셋은 NORB와 Caltech-101/256, CIFAR-10/100 등이 있습니다. 이들은 당시 기준으로는 표준적이고 잘 만들어진 데이터셋이지만 데이터의 규모는 객체 인식 연구를 하기에는 충분하지 않은 규모 (수만 장)였습니다.

물론 간단한 인식은 labrl-preserving transformation릏 통한 데이터 증강을 활용하여 이 규모에서도 꽤나 잘 이루어졌지만 문제는 가려짐, 배경 변화, 시점 변화 같은 상황의 경우 단순한 증강으로는 한계점이 있어 더 많은 데이터가 필요해졌습니다.

이때 등장한 것이 바로 ImageNet이었습니다. ImageNet은 2009년 대규모 객체 인식을 위해 등장한 이미지 데이터셋으로. 한 객체 범주 (synset) 당 평균 1000개의 이미지라는 대규모의 데이터셋입니다. 이로써 객체 인식을 위한 데이터의 규모는 갖추어졌지만, 많은 데이터가 필요해짐에 따라 또한 모델의 용량도 이에 맞춰 더 커져야 했습니다.

Ⅰ.2. 모델 용량(Capacity)의 필요성

데이터의 규모가 커진 만큼 데이터의 복잡도 (e.g. 시점 변화, 조명 변화, 배경 변화...)도 느러 연구진은 CNN을 선택하게 됩니다. CNN의 특성은 바로 다음 섹션에서 설명합니다.

이러한 배경에서 연구진들은 다음과 같은 선택을 통해 모델의 용량을 키워 AlexNet의 성능을 끌어올립니다.

• 약 6천만개의 파라미터

• 5개의 Convolution Layer와 3개의 Fully Connected Layer
• 상대적으로 큰 Neural Network

Ⅱ. Key Design Choices

Architecture is not just structure; it is prior knowledge.

Ⅱ.1. Convolution Neural Network (CNN)

CNN은 기존의 Neural Network에 기반하였기에 학습 가능한 weights와 bias를 가진 neuron을 가지고 있습니다. 하지만 가장 큰 변화점은 입력값이 이미지라는 가정하에 다양한 이미지의 특성을 구조에 녹일 수 있다는 점입니다.

다시 말해 "이미지의 내부에는 인접한 픽셀 간의 강한 상관관계가 있다 (Locality)"라는 가정과 "이미지의 통계적 특성은 픽셀의 위치에 따라 크게 변하지 않는다 (Stationarity)"라는 가정을 전제하에 두고 있습니다.

그렇기에 기존의 Nerual Network와는 다르게 더 적은 connection와 parameter를 가지고 더 쉽게 학습 가능하게 됩니다. 물론 이때 약간의 성능하락은 존재하지만 여전히 매력적인 선택지입니다.

하지만 그럼 왜 진작 사용하지 않았는가? 라고 묻는다면 이 모델을 실행할 하드웨어 자원이 부족했기 때문입니다. 하지만 연구진은 당시에 개발된 GPU (GTX 580 3GB GPU)를 CNN에 맞게 적용하여 사용해서 큰 CNN 모델에 대한 학습을 가능하게 합니다. 이를 연구진은 아래와 같이 말합니다.

Luckily, current GPUs, paired with a highly-optimized implementation of 2D convolution, are powerful enough to facilitate the training of interestingly-large CNNs, and recent datasets such as ImageNet contain enough labeled examples to train such models without severe overfitting.

하지만 연구진은 Convolution layer만 사용하지 않고 기존의 Fully connected network 역시 사용합니다. (It contains eight learned layers — five convolutional and three fully-connected.)

Fully-connected layer란? 한 레이어의 모든 뉴런이 바로 이전 레이어의 모든 뉴런과 연결되어 있는 레이어를 말합니다.

1. convolutional layer

• 국소 영역 (local receptive field)만 봄
• 가중치 공유 (weight sharing)
• 공간 구조 (spatial structure)를 유지

2. fully-connected layer

• 공간 구조를 더 이상 고려하지 않음
• 입력 전체를 하나의 벡터로 보고
• 모든 입력을 종합해서 판단

Ⅱ.2. Rectified Linear Units (ReLUs) Nonlinearity

기존의 $tanh$, sigmoid 계열의 활성화 함수는 깊은 네트워크 (입력값의 절댓값이 커질 수록) gradient saturation 문제를 유발하게 됩니다. (e.g. $sigmoid(x) = (1 + e^{-x})^{-1}$) 이런 문제를 해결하고자 연구진은 $f(x) = max(0,x)$ ReLU를 활성화 함수로 지정하여 이러한 saturation 문제를 해결합니다.

Saturation은 왜 문제가 되는가? Fig. 1에서 나타나듯이 Epoch에 따라 Training Error Rate를 보면 ReLU가 tanh에 비해 훨씬 빠른 학습 속도를 보여줍니다. 이 이유는 입력값의 절댓값이 커질 수록 출력이 거의 일정해지고 그렇기에 gradient가 매우 작아지며 학습이 느려지게 되기 때문입니다.

이 ReLU를 통해 학습 속도는 대폭 향상되고, 큰 모델에서도 non-saturating한 활성 함수를 사용하기에 실험을 반복적으로 수행 가능하며, 이러한 깊은 CNN 학습이 현실적인 시간 내에 완료되도록 합니다.

Ⅱ.3. GPU parallelization

연구진이 사용한 GTX 580 GPU는 3GB의 메모리 크기를 가지고 있기에 1,200,000개의 훈련 데이터를 학습하기에 적합한 Network를 돌리기에는 한 GPU 가지고는 모자랐습니다. 그렇기에 연구진의 선택은 두개의 GPU를 통해 병렬 연산을 진행하는 방식을 선택했습니다.

단순히 Kernel이나 Neuron을 절반으로 나누어 각각 넣는게 아니라 GPU간의 communication을 특정 레이어에서만 전체 연결을 허용합니다. 예를 들어 3번 레이어의 Kernel은 2번 레이어의 모든 Kernel로부터 정보를 받습니다. (이는 두 GPU에서의 값을 모두 받는다는 것을 의미합니다. Communication 발생)

하지만 4번 레이어의 Kernel의 경우 동일 GPU에 있는 3번 레이어의 데이터만 입력값으로 받게 됩니다. 이렇게 함으로써 개별 GPU가 소화할 수 있는 적정한 연산량 안에서의 communication 양을 세밀하게 조절할 수 있게 해줍니다.

이러한 구조는 Columnar CNN과 상당히 유사하지만 AlexNet은 column이 독립적이지 않다라는 차이점이 있습니다.

정리하자면 이러한 GPU 병렬화는 개별 GPU로는 수행하지 못하는 양의 연산을 수행하고, 단일 Convolution layer에서 개별 GPU로만 구현했을 때보다 약간 빠르게 수행합니다.

Ⅱ.4. Reducing Overfitting

물론 모델이 커짐에 따라 너무나도 학습 데이터를 잘 학습한 나머지 발생하는 과적합은 필연적이게 됩니다. 이러한 과적합을 연구진은 계속해서 언급했고, 아래의 두가지 전략을 통해 과적합을 줄입니다.

Ⅱ.4.1. Data Augmentation

AlexNet에서는 두가지 방법으로 데이터 증강을 진행합니다. 첫번째는 이미지를 임의로 224 by 224 patch로 잘라내고 좌우 반전을 하는 방식으로 증강을 이루는 것입니다. 이러한 데이터 증강은 훈련 데이터셋의 사이즈를 키우는 방식으로 과적합을 줄여줍니다.

두번째 방법으로는 학습 이미지의 RGB 채널의 강도를 PCA (Primary Component Analysis)를 통해 도출된 principal component를 곱하는 방식으로 조정을 해줍니다. 또한 RGB pixel 값들의 eigenvector와 eigenvalue를 활용해서 단순히 색을 무작위로 변화하는 방식으로 증강한 것이 아니라 현실적인 조명 변화를 흉내내며 증강하게 됩니다.

그래서 Generating image translations and horizontal reflec tions와 Altering the intensities of the RGB channels in training images 두가지 데이터 증강 전략을 통해 과적합을 방지할 수 있었다고 합니다.

Ⅱ.4.2. Dropout

당시 비교적 최근에 소개된 dropout 전략이 AlexNet에 적용된 두번째 과적합 방지 전략입니다. Dropout 전략은 각각의 히든 뉴런의 출력값에 대해서 일정한 확률 (AlexNet에서는 0.5)로 0이 되게끔 설정하는 전략입니다. 이러한 방식으로 누락된 ("Dropped out") 뉴런들은 다음 레이어에 영향을 미치지 않아 back propagation에도 참여하지 못하게 됩니다.

이렇게 함으로써 학습을 진행할 때마다 구조가 조금씩 다른 네트워크를 학습하는 동시에 weight 값은 공유를 하기에 샘플마다 다른 개별 특징에 초점이 맞춰지는게 아니라 더 일반적인 공통된 특징에 더 집중되어 학습을 진행하게 됩니다. 이렇게 진행함으로써 과적합을 방지할 수 있게 됩니다.

Ⅲ. Limitations & Conclusion

결론적으로 AlexNet은 당시의 GPU 발전과 함께 대규모의 깊은 CNN을 구현했고 그 해 2012년 Large Scale Visual Recognition Challenge (LSVRC)에서 top-5 test error rate로 15.3%로 두번째로 낮았던 26.2%보다 훨씬 뛰어난 성능을 보였습니다.

물론 실험을 단순하게 하기 위해 Unsupervised pre-traing을 사용하지 않았으므로 성능을 더 끌어올릴 수 있는 여지가 있다는 점, 인간의 시각 시스템에 비해서는 아직 너무나도 작은 모델이라는 연구진의 자기 평가가 있었지만 그럼에도 불구하고 깊은 CNN 하나만으로 순수 지도학습에서 당시 최고 성능을 달성했다는 점에서 의미있는 시도였습니다.

오늘은 Computer Vision에서 굵직한 마일 스톤 중 하나인 AlexNet에 대한 논문을 읽어보았습니다. 이번에도 긴 글 읽어주셔서 감사합니다.

의견이나 질문이 있다면 댓글로 남겨주시기 바랍니다.

난이도: ★★☆☆☆ • solved on: 2026-01-03

문제 요약

• 문제 유형: 수학, 에라토스테네스의 체, 구현
• 요구사항: 입력된 구간 [n, m] 안에 존재하는 모든 소수를 한 줄씩 출력해야 한다.

사용 개념

1. 자료구조

   • boolean[] : 합성수 여부 (표시 배열)
   • StringBuilder : 출력 누적

2. 알고리즘/기법

   • 에라토스테네스의 체 (Sieve of Eratosthenes)
   • 배수 마킹 (Marking multiples)

3. 핵심 키워드

   • 소수 (prime number)
   • 합성수 (composite number)
   • 배수 (multiple)

풀이 아이디어

1. 문제 분해

• 0과 1은 소수가 아니므로 먼저 합성수 취급(true)로 표시한다.
• 2부터 시작해, 아직 체크되지 않은 수(소수 후보)를 만나면 그 수의 배수들을 합성수(true)로 표시한다.
• 최종적으로 arr[i] == false인 수만 출력한다(소수만 남김).

2. 핵심 로직 흐름

   arr[0] = arr[1] = true  // 소수 아님(합성수 취급)
   for i = 2 .. m:
       if arr[i] == true: continue
       for j = 2 while i*j <= m:
           arr[i*j] = true  // 합성수 표시
   >
   for i = n .. m:
       if arr[i] == false: print i

3. 예외 처리
   • 0, 1은 소수가 아니므로 반드시 제외한다.
   • boolean 배열의 기본값이 false이므로, “표시되면 합성수(true)” 방식으로 관리한다.

코드

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

class Main {
    public static boolean[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new boolean[m+1];
        StringBuilder sb = new StringBuilder();
        makeSlieve();

        for(int i = n; i <= m; i++){
            if(!arr[i]) sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
    public static void makeSlieve(){
        arr[0] = true;
        arr[1] = true;
        for(int i = 2; i < arr.length; i++){
            if(arr[i]) continue;
            for(int j = 2; i*j < arr.length; j++){
                arr[i*j] = true;
            }
        }
    }
}

시간·공간 복잡도

• 시간 복잡도: 대략 O(M log log M) 수준 (에라토스테네스의 체)

  • 구현상 i*j 형태로 마킹하므로 상수는 커질 수 있으나, 기본 아이디어는 체 방식이다.

• 공간 복잡도: O(M) (boolean[m+1])

어려웠던 점

• boolean 배열의 기본값이 무엇인지 몰라서 혼란이 있었다.
• 처음에는 소수만 true를 기대했지만 실제로는 기본값이 전부 false라서 의도와 반대로 동작하는 문제가 생겼다.
• 그래서 합성수만 true로 표시하고, 끝까지 false로 남은 값이 소수가 되도록 방향을 바꿔 해결했다.
• 참고 블로그를 통해 boolean 기본값이 false임을 확인했다.

배운 점 및 팁

• Java에서 boolean[]의 기본값은 false라서, 보통은 합성수만 true로 마킹하는 형태가 구현이 편하다.
• 배수 마킹은 j = i*i부터 시작하거나 $i <= \sqrt{m}$까지만 돌리면 더 빠르게 만들 수 있다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1929
• 참고 블로그/깃허브: https://nanarin.tistory.com/53

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 1978번 소수 찾기
  • 백준 - 4948번 베르트랑 공준

• 확장 문제 (GPT 추천):

  • 백준 - 17103번 골드바흐 파티션
  • HackerRank - Day 25: Running Time and Complexity

난이도: ★★☆☆☆ • solved on: 2026-01-03

문제 요약

• 문제 유형: 수학, 소수 판정, 브루트포스
• 요구사항: 각 테스트케이스마다 입력된 수 n 이상에서 가장 작은 소수를 찾아 출력해야 한다.

사용 개념

1. 자료구조

   • StringBuilder : 여러 줄 출력 누적
   • BufferedReader : 빠른 입력

2. 알고리즘/기법

   • 소수 판정(Prime Check)
   • n부터 1씩 증가시키며 첫 소수 탐색

3. 핵심 키워드

   • 소수(prime number)
   • √n 까지 나눗셈 검사

풀이 아이디어

1. 문제 분해

• 각 입력 target에 대해 current = target으로 시작한다.
• current가 소수인지 확인하고, 아니면 current++ 하며 반복한다.
• 처음으로 소수 판정을 통과한 current를 출력한다.

2. 핵심 로직 흐름

   for i in 1..T:
       current = target
       while true:
           if isPrime(current):
               print current
               break
           current++

3. 예외 처리
   • 0, 1은 소수가 아니므로 false로 처리한다.
   • 2는 소수이므로 true로 처리한다.

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long target;
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < n; i++){
            String s = br.readLine();
            target = Long.parseLong(s);
            long current = target;
            while(true){
                if(isPrime(current)){
                    sb.append(current).append("\n");
                    break;
                }
                current++;
            }
        }
        System.out.print(sb);
    }
    public static boolean isPrime(long n){
        if(n == 1 || n == 0) return false;
        if(n == 2) return true;
        for(long i = 2; i*i <= n; i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

시간·공간 복잡도

• 시간 복잡도: 최악의 경우 O(K × √M)

  • K = 소수를 찾을 때까지 증가한 횟수
  • M = 검사 중인 수 크기

• 공간 복잡도: O(1) (입력/출력 버퍼 제외)

어려웠던 점

• 0, 1이 소수가 아니라는 예외를 놓치면 오답이 나기 쉽다.
• target부터 시작해서 다음 소수를 찾는 반복 구조에서, 소수 판정 함수가 정확해야 한다.

배운 점 및 팁

• 소수 판정은 2부터 √n까지만 나눠보면 된다.
• 밀러-라빈 테스트를 구현하면 더 효율적인 검증이 가능하지만 아직 어려워 이해하지 못했다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/4134
• 참고 블로그/깃허브:
  • Miller–Rabin primality test
  • [Algo] 밀러-라빈 소수 판별법(Miller-Rabin Primality Test)

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 1929번 소수 구하기
  • 백준 - 4948번 베르트랑 공준

• 확장 문제 (GPT 추천):

  • 백준 - 17103번 골드바흐 파티션
  • HackerRank - Day 25: Running Time and Complexity

난이도: ★★★☆☆ • solved on: 2026-01-03

문제 요약

• 문제 유형: 수학, 최대공약수(GCD)
• 요구사항: 기존 가로수 위치를 기준으로 모든 가로수 사이의 간격이 동일해지도록 만들 때, 추가로 심어야 하는 가로수의 개수를 구해야 한다.

사용 개념

1. 자료구조

   • long[] : 가로수 좌표 및 간격 저장

2. 알고리즘/기법

   • 정렬
   • 유클리드 호제법 (Euclidean Algorithm)

3. 핵심 키워드

   • 인접 간격
   • 간격들의 최대공약수 (GCD)
   • (gap / gcd) - 1

풀이 아이디어 및 코드

방법 1 : 현재 가로수의 위치 정보를 저장

1. 문제 분해

• 가로수 위치를 배열에 저장한다.
• 인접한 가로수 사이의 간격 배열 gaps를 만든다.
• 모든 간격의 GCD를 구해 currentGcd로 저장한다.
• 첫 위치부터 마지막 위치까지 currentGcd 간격으로 하나씩 훑으면서, 기존 가로수가 없는 위치를 카운트한다.
  2. 핵심 로직 흐름

     gaps 생성
     gaps 전체 GCD 계산 → currentGcd
     start부터 end까지 currentGcd 간격으로 순회
     기존 위치에 없으면 count++

  3. 한계

• 좌표 범위가 커질 경우, while 문 순회 횟수가 불필요하게 많아질 수 있다.
• 실제로는 계산으로 바로 구할 수 있는 값을 시뮬레이션으로 처리하고 있다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] positions = new long[n];
        long[] gaps = new long[n-1];
        long currentGcd = 1;

        for(int i=0;i<n;i++){
            positions[i] = Long.parseLong(br.readLine());
            if(i > 0){
                gaps[i-1] = positions[i] - positions[i-1];
            }
            if(i == n-1){
                break;
            }
        }

        Arrays.sort(positions);

        for(int i=0;i<n-1;i++){
            if(i == 1){
                currentGcd = gcd(gaps[i-1], gaps[i]);
            } else if (i > 1){
                currentGcd = gcd(currentGcd, gaps[i]);
            }
        }

        int i = 0;
        int j = 0;
        long start = positions[0];
        int count = 0;

        while((start + currentGcd * j) <= positions[positions.length-1]){
            if(positions[i] == start + currentGcd * j){
                i ++;
                j ++;
                continue;
            } else {
                count++;
                j ++;
            }
        }
        System.out.println(count);
    }

    public static long gcd(long a,long b){
        while(b != 0){
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

방법 2 : 위치 정보 대신 간격 합산에 집중

1. 핵심 관찰

• 최종적으로 모든 가로수 사이의 간격은 “인접 간격들의 최대공약수(GCD)”가 된다.

2. 계산 방식
   • 어떤 간격 gap이 있고 최종 간격이 gcd라면,
   • 해당 구간은 gap / gcd개의 구간으로 나뉜다.
   • 이미 양 끝에 나무가 있으므로, 추가로 필요한 나무 수는 (gap / gcd) - 1이다.
3. 전체 답
   • 모든 인접 간격에 대해 위 값을 더한 합이다.
4. 핵심 로직 흐름

   positions 정렬
   모든 인접 gap의 GCD 계산 → g
   answer = Σ (gap / g - 1)

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

class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

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

        long[] pos = new long[N];
        for (int i = 0; i < N; i++) {
            pos[i] = Long.parseLong(br.readLine());
        }

        Arrays.sort(pos);

        long g = pos[1] - pos[0];
        for (int i = 2; i < N; i++) {
            g = gcd(g, pos[i] - pos[i - 1]);
        }

        long answer = 0;
        for (int i = 1; i < N; i++) {
            long gap = pos[i] - pos[i - 1];
            answer += (gap / g) - 1;
        }

        System.out.println(answer);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: $O(N log N + R / G)$ (R: 좌표 범위, G: 최종 간격)
• 공간 복잡도: $O(N)$

방법 2

• 시간 복잡도: $O(N log N)$
• 공간 복잡도: $O(N)$

어려웠던 점

• 구현 자체는 단순했지만, 시뮬레이션을 수식으로 치환할 수 있다는 발상에 도달하기 어려웠다.
• “모든 위치를 직접 세어보지 않아도 된다”는 점을 떠올리지 못해 시간복잡도 개선 방향을 잡는 데 시간이 걸렸다.

배운 점 및 팁

• 동일 간격을 만드는 문제는 대부분 간격들의 GCD로 귀결된다.
• 좌표 문제에서 “하나씩 훑는 방식”이 보이면, 간격 단위로 계산할 수 있는지 먼저 의심해보는 것이 좋다. (위치 정보의 필요성에 대한 의심)
• 추가 개수는 시뮬레이션보다 $Σ (gap / gcd - 1)$ 형태의 수식이 훨씬 안전하고 빠르다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2485
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 2609번 최대공약수와 최소공배수
  • 백준 - 2981번 검문

• 확장 문제 (GPT 추천):

  • 백준 - 14476번 최대공약수 하나 빼기
  • 백준 - 1735번 분수 합 `

난이도: ★★☆☆☆ • solved on: 2026-01-02

문제 요약

• 문제 유형: 유클리드 호제법, 수학
• 요구사항: 테스트 케이스마다 두 자연수의 최소공배수(LCM) 를 출력해야 한다.

사용 개념

1. 자료구조

   • StringTokenizer, StringBuilder

2. 알고리즘/기법

   • 최대공약수 (GCD)
   • 최소공배수 (LCM) 관계식: $LCM(a,b) = (a / GCD(a,b)) * b$

3. 핵심 키워드

   • 유클리드 호제법 (Euclidean Algorithm)
   • 공약수/공배수

풀이 아이디어 및 코드

방법 1 : 공통 인수 탐색

1. 문제 분해

• 두 수의 공약수를 작은 값부터 나눠가며 공통 인수를 result에 누적한다.
• 나눠 떨어지면 a, b를 그 인수로 나누고, 나눠 떨어지지 않을 때만 divisor++ 한다.

2. 핵심 로직 흐름

   result = 1
   divisor = 2
   while divisor < a or divisor < b:
       if a%divisor==0 and b%divisor==0:
           result *= divisor
           a /= divisor
           b /= divisor
       else:
           divisor++
   result *= a*b

3. 예외 처리
   • 한 수가 다른 수의 배수인 경우, 더 큰 수가 LCM이므로 바로 출력한다.

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int a = 0;
        int b = 0;
        int result = 1;

        for(int i = 0; i < n; i++){
            String[] lines = br.readLine().split(" ");

            a = Integer.parseInt(lines[0]);
            b = Integer.parseInt(lines[1]);
            result = 1;

            if(a%b == 0 || b%a == 0){
                sb.append(Math.max(a,b)).append("\n");
                continue;
            }
            int min = Math.min(a, b);
            int divisor = 2;
            while(divisor < a || divisor < b){
                if(a%divisor==0 && b%divisor==0){
                    result *= divisor;
                    a /= divisor;
                    b /= divisor;
                } else {
                    divisor++;
                }
            }

            result *= a * b;
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

방법 2 : 유클리드 호제법으로 GCD → LCM

1. 문제 분해

• 최소공배수는 공약수를 “직접” 모두 찾기보다, 최대공약수(GCD) 만 구하면 바로 계산할 수 있다.

2. 핵심 로직 흐름

   gcd(a,b):
       while b != 0:
           t = a % b
           a = b
           b = t
       return a
   >
   lcm = a / gcd(a,b) * b

3. 예외 처리
   • 곱이 커질 수 있으므로 long을 사용한다.

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

class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());

            long g = gcd(a, b);
            long l = (a / g) * b;   // overflow 방지를 위해 a/g 먼저 수행
            sb.append(l).append('\n');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1 :

• 시간 복잡도: 최악 O(max(a,b))에 가깝게 커질 수 있다. (작은 약수부터 전부 시도하는 구조)
• 공간 복잡도: O(1)

방법 2 :

• 시간 복잡도: O(log(min(a,b))) (유클리드 호제법)
• 공간 복잡도: O(1)

어려웠던 점

• 처음에는 for (divisor++)로 약수를 검사했는데, 이 방식은 같은 소수가 여러 번(예: p²) 나눠지는 경우를 연속으로 반영하기 어렵다는 문제가 있었다.
• 그래서 “약수를 찾지 못할 때만 ++ 한다”는 방식으로 while로 바꿔 중복 약수를 처리하도록 수정했다.

배운 점 및 팁

• 최소공배수는 공약수를 직접 누적하기보다 GCD만 구해도 LCM = a / GCD * b로 바로 계산한다.
• 유클리드 호제법은 구현이 짧고 입력 범위가 커져도 안정적으로 빠르다.
• 곱셈이 들어가는 문제는 int 대신 long을 먼저 떠올리는 습관이 중요하다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1934
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 2609번 최대공약수와 최소공배수
  • 백준 - 2981번 검문

• 확장 문제 (GPT 추천):

  • 백준 - 3036번 링
  • HackerRank - Euclid's Algorithm

난이도: ★☆☆☆☆ • solved on: 2026-01-01

문제 요약

• 문제 유형: 집합(Set), 해시(Hash)
• 요구사항: 두 집합 A, B에 대해 대칭 차집합 $((A-B) ∪ (B-A))$의 원소 개수를 출력해야 한다.

사용 개념

1. 자료구조

   • HashSet : 원소 존재 여부를 평균 O(1)로 검사한다.

2. 알고리즘/기법

   • 집합 연산의 크기 계산
   • 교집합 개수 세기

3. 핵심 키워드

   • 대칭 차집합 (symmetric difference)
   • 교집합 (intersection)

풀이 아이디어 및 코드

방법 1 : 합집합을 만들고 교집합 개수만큼 빼기

1. 문제 분해

• A, B를 각각 HashSet에 넣는다.
• A∪B 역할을 하는 setAorB를 만든다.
• setAorB를 순회하며 A와 B에 모두 있으면(교집합) count++ 한다.
• 최종 답을 |A∪B| - |A∩B| 로 계산한다.

2. 핵심 로직 흐름

   setAorB = A ∪ B
   count = |A ∩ B|
   answer = |setAorB| - count

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int m = Integer.parseInt(nums[1]);
        int count = 0;

        HashSet<String> setA = new HashSet<>(n);
        HashSet<String> setB = new HashSet<>(m);
        HashSet<String> setAorB = new HashSet<>();
        StringTokenizer stA = new StringTokenizer(br.readLine());
        StringTokenizer stB = new StringTokenizer(br.readLine());

        while(stA.hasMoreTokens()){
            String temp = stA.nextToken();
            setA.add(temp);
            setAorB.add(temp);
        }

        while(stB.hasMoreTokens()){
            String temp = stB.nextToken();
            setB.add(temp);
            setAorB.add(temp);
        }

        for(String a : setAorB){
            if(setA.contains(a)&&setB.contains(a)){
                count++;
            }
        }

        System.out.println(setAorB.size()-count);
    }
}

방법 2 : 교집합만 세서 n + m - 2*common로 바로 계산

1. 개선 포인트

• 대칭 차집합 크기 = (|A-B| + |B-A|) 이고, 이는 (|A| + |B| - 2|A∩B|) 로 정리된다.
• 따라서 합집합 set을 따로 만들 필요가 없다.

2. 핵심 로직 흐름

   common = 0
   A를 set에 저장
   B를 읽으면서 A에 있으면 common++
   answer = n + m - 2*common

3. 추가 개선
   • 입력이 자연수이므로 HashSet<Integer>로 처리하는 편이 의미상 맞고, 변환 비용도 줄인다.

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

class Main {
    public static void main(String[] args) throws Exception {
        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());

        HashSet<Integer> setA = new HashSet<>(n);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            setA.add(Integer.parseInt(st.nextToken()));
        }

        int common = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int x = Integer.parseInt(st.nextToken());
            if (setA.contains(x)) common++;
        }

        int answer = n + m - 2 * common;
        System.out.println(answer);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M) 평균 (해시 연산 가정)
• 공간 복잡도: O(N + M) (setA, setB, setAorB 저장)

방법 2

• 시간 복잡도: O(N + M) 평균
• 공간 복잡도: O(N) (setA만 유지)

어려웠던 점

• 없음

배운 점 및 팁

• 대칭 차집합 크기는 $n + m - 2 * |A∩B|$ 로 바로 계산하는 편이 구현과 메모리 측면에서 더 단순하다.
• 이 문제는 최대 200,000개 원소까지 가능하므로, 이중 루프 대신 해시 기반 포함 검사로 풀어야 한다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1269
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 1764번 듣보잡
  • 백준 - 7785번 회사에 있는 사람
  • 백준 - 10816번 숫자 카드 2

• 확장 문제 (GPT 추천):

  • HackerRank - No Idea!
  • HackerRank - Two Strings

난이도: ★★☆☆☆ • solved on: 2026-01-01

문제 요약

• 문제 유형: 해시 (Hash), 문자열, 정렬
• 요구사항: 듣도 못한 사람과 보도 못한 사람의 교집합을 찾아 사전식(오름차순)으로 출력해야 한다.

사용 개념

1. 자료구조

   • HashMap<String, Integer> / HashSet<String>
   • ArrayList<String> : 교집합 결과 저장
   • Collections.sort() : 사전식 정렬

2. 알고리즘/기법

   • 해시를 이용한 중복/존재 여부 체크
   • 교집합 추출 후 정렬

3. 핵심 키워드

   • 교집합 (intersection)
   • 사전식 정렬 (lexicographical order)

풀이 아이디어 및 코드

방법 1 : HashMap 카운팅으로 교집합 판별

1. 문제 분해

• 듣도 못한 사람 N명을 map에 넣고 값 1로 기록한다.
• 보도 못한 사람 M명을 입력받아 map.getOrDefault(name, 0) + 1로 누적한다.
• 최종적으로 값이 2인 키가 교집합(듣보잡)이므로 리스트에 담는다.
• 리스트를 사전식으로 정렬한 뒤 개수와 이름들을 출력한다.

2. 핵심 로직 흐름

   map에 N명은 1로 저장
   M명을 읽으며 map[name] += 1
   map 전체 순회하며 value==2인 key만 list에 저장
   list 정렬 후 출력

3. 예외 처리
   • 교집합이 0명일 수도 있으므로, 출력 형식을 그대로 유지한다.

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n =  Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        HashMap<String, Integer> map = new HashMap<>();
        int total = 0;
        StringBuilder sb = new StringBuilder();
        ArrayList<String> list = new ArrayList<>();

        for(int i = 0; i < n; i++){
            map.put(br.readLine(), 1);
        }

        for(int i = 0; i < m; i++){
            String name = br.readLine();
            map.put(name, map.getOrDefault(name, 0) + 1);
        }

        for(String key : map.keySet()){
            if(map.get(key)==2){
                total++;
                list.add(key);
            }
        }
        System.out.println(total);

        Collections.sort(list);

        for(int i = 0; i < list.size(); i++){
            sb.append(list.get(i)).append("\n");
        }

        System.out.println(sb);

    }
}

방법 2 : HashSet으로 존재 확인 후 교집합만 수집

1. 개선 포인트

• HashMap으로 전체를 카운팅하지 않고, 듣도 목록을 Set에 저장한 뒤 보도 입력을 읽으면서 set.contains(name)인 경우만 결과 리스트에 추가한다.
• 교집합 후보만 모으므로, 불필요한 map.keySet() 전체 순회가 사라지고 코드가 더 단순해진다.

2. 핵심 로직 흐름

   set에 N명 저장
   M명을 읽으며 set에 있으면 result에 추가
   result 정렬 후 출력

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

class Main {
    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());

        HashSet<String> heard = new HashSet<>(n * 2);
        ArrayList<String> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            heard.add(br.readLine());
        }

        for (int i = 0; i < m; i++) {
            String name = br.readLine();
            if (heard.contains(name)) {
                result.add(name);
            }
        }

        Collections.sort(result);

        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append('\n');
        for (String name : result) sb.append(name).append('\n');
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M + K log K) (K = 교집합 크기, 정렬 비용)
• 공간 복잡도: O(N + M) 수준 (map에 둘 다 들어갈 수 있음)

방법 2

• 시간 복잡도: O(N + M + K log K)
• 공간 복잡도: O(N + K) (듣도 set + 결과만 보관)

어려웠던 점

• 처음에는 HashMap으로 false/true 판별 방식도 고려했지만, 사전식 정렬을 해야 해서 결국 카운팅 방식으로 저장한뒤 정렬 로직을 따로 구성했다.
• Set.contains(value)는 평균적으로 O(1)인 것을 까먹었다

배운 점 및 팁

• 교집합 문제는 “한 쪽을 Set에 넣고, 다른 쪽을 보면서 contains로 걸러내기”가 가장 단순한 정석 패턴이다.
• 사전식 정렬은 결과 리스트만 정렬하면 되므로, 전체 자료구조를 정렬형(TreeSet)으로 유지할 필요는 보통 없다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1764
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 10816번 숫자 카드 2

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡 (정렬 대신 출력 포맷/자료구조 변형 연습)
  • HackerRank - Hash Tables: Ransom Note

난이도: ★★☆☆☆ • solved on: 2025-12-31

문제 요약

• 문제 유형: 해시맵(HashMap), 카운팅(counting)
• 요구사항: N개의 정수 카드에서 각 질의 수가 몇 개 있는지 개수를 출력해야 한다.

사용 개념

1. 자료구조

   • HashMap<Integer, Integer>: (숫자 → 등장 횟수) 저장

2. 알고리즘/기법

   • 빈도수 카운팅 (frequency counting)
   • getOrDefault를 이용한 안전 조회

3. 핵심 키워드

   • 평균 O(1) 조회
   • 중복 원소 개수(count)

풀이 아이디어 및 코드

방법 1 : HashMap을 활용한 누적 카운팅

1. 문제 분해

• N개의 카드를 읽으면서 map에 숫자별 등장 횟수를 누적한다.
• M개의 질의를 읽으면서 map.getOrDefault(q, 0)으로 개수를 출력한다.

2. 핵심 로직 흐름

   입력 N
   카드 N개를 map에 카운팅
   >
   입력 M
   질의 M개에 대해 map[q] 출력 (없으면 0)

3. 예외 처리
   • 질의 숫자가 없는 경우 0 출력 (getOrDefault)

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

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

        HashMap<Integer, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        String m = br.readLine();
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        while(st.hasMoreTokens()){
            int temp = Integer.parseInt(st.nextToken());
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }

        while(st2.hasMoreTokens()){
            int q = Integer.parseInt(st2.nextToken());
            sb.append(map.getOrDefault(q, 0)).append(" ");
        }

        System.out.println(sb);
    }
}

방법 2 : 정렬 + 이분 탐색

1. 개선 포인트

• 해시맵 풀이도 정답이고 빠르지만, 이 문제는 전형적으로 정렬 후 lower/upper bound로 개수를 세는 풀이도 자주 사용한다.
• 해시맵은 평균 O(1)이지만, 정렬 기반 풀이는 성능이 안정적이고(결정적), 구현 연습 가치가 있다.

2. 핵심 로직 흐름

   카드 배열 정렬
   count(x) = upperBound(x) - lowerBound(x)

3. 예외 처리
   • 카드에 없는 값이면 두 bound가 같아 0

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

public class Main {
    static int lowerBound(int[] arr, int target) {
        int l = 0, r = arr.length; // [l, r)
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    static int upperBound(int[] arr, int target) {
        int l = 0, r = arr.length; // [l, r)
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] > target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) cards[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(cards);

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int q = Integer.parseInt(st.nextToken());
            int cnt = upperBound(cards, q) - lowerBound(cards, q);
            sb.append(cnt).append(' ');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1 (HashMap)

• 시간 복잡도: O(N + M) (평균)
• 공간 복잡도: O(N) (서로 다른 값 개수만큼)

방법 2 (정렬 + 이분 탐색)

• 시간 복잡도: O(N log N + M log N)
• 공간 복잡도: O(N)

어려웠던 점

• 없음

배운 점 및 팁

• 이 문제는 카운팅이므로 해시맵이 가장 직관적이다.

• 코딩 테스트 관점에서는

  • 빠르게 맞추기: 해시맵
  • 기본기/안정성 연습: 정렬 + lower/upper bound 둘 다 정석 범위에 들어간다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/10816
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 10815번 숫자 카드
  • 백준 - 14425번 문자열 집합

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡
  • HackerRank - Frequency Queries

난이도: ★★☆☆☆ • solved on: 2025-12-31

문제 요약

• 문제 유형: 해시맵(HashMap), 문자열 처리, 구현
• 요구사항: 포켓몬 이름 ↔ 번호를 빠르게 상호 변환하여 질의 M개에 답해야 한다.

사용 개념

1. 자료구조

   • HashMap<String, Integer>: 이름 → 번호 조회
   • String[] names: 번호 → 이름 조회 (인덱스 기반)

2. 알고리즘/기법

   • 양방향 매핑 (bidirectional mapping)
   • 질의가 숫자인지/문자인지 판별하여 분기 처리

3. 핵심 키워드

   • 해시 조회
   • 문자열 판별

풀이 아이디어 및 코드

방법 1 : 내 풀이

1. 문제 분해

• names[i]에 i번 포켓몬 이름을 저장한다.
• map에 (이름 → 번호)를 저장한다.
• 질의가 숫자면 names[index], 문자면 map.get(name)을 출력한다.

2. 핵심 로직 흐름

   입력 N, M
   for i=1..N:
       names[i] = pokemon
       map[pokemon] = i
   >
   for each question:
       if (question is number) -> names[number]
       else -> map[question]

3. 예외 처리
   • 없음

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        String[] names = new String[n+1];
        HashMap<String, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= n; i++){
            String pokemon = br.readLine();
            names[i] = pokemon;
            map.put(pokemon, i);
        }

        for(int i = 0; i < m; i++){
            String question = br.readLine();
            if(question.toUpperCase().equals(question)){
                int index = Integer.parseInt(question);
                sb.append(names[index]).append("\n");
            } else {
                sb.append(map.get(question)).append("\n");
            }
        }

        System.out.println(sb);
    }
}

방법 2 : 개선된 최적의 풀이 (숫자 판별 로직 교정)

1. 개선 포인트

• question.toUpperCase().equals(question)는 “질의가 숫자인지” 판별하는 조건으로 부적절하다.
  • 숫자 문자열은 대소문자 변화가 없어서 true가 되지만, 이름이 전부 대문자인 경우도 true가 되어 Integer.parseInt()에서 예외가 난다.
  • 하지만 이 문제에서는 예외가 발생하지 않았다. 와우.

• 따라서 첫 글자가 숫자인지로 판별하는 방식이 안전하고 빠르다. (Character.isDigit(question.charAt(0)))

2. 핵심 로직 흐름

   if Character.isDigit(question.charAt(0)):
       idx = Integer.parseInt(question)
       print names[idx]
   else:
       print map.get(question)

3. 예외 처리
   • 없음 (문제 조건상 숫자 질의는 항상 올바른 번호로 주어진다)

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

public class Main {
    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());

        String[] names = new String[n + 1];
        HashMap<String, Integer> map = new HashMap<>(n * 2);

        for (int i = 1; i <= n; i++) {
            String pokemon = br.readLine();
            names[i] = pokemon;
            map.put(pokemon, i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            String q = br.readLine();
            if (Character.isDigit(q.charAt(0))) {
                sb.append(names[Integer.parseInt(q)]).append('\n');
            } else {
                sb.append(map.get(q)).append('\n');
            }
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M)
• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N + M)
• 공간 복잡도: O(N)

어려웠던 점

• 없음

배운 점 및 팁

• “문자열이 숫자인지” 판별할 때 대소문자 변환 비교는 목적에 맞지 않다.
• 이 문제처럼 입력이 “번호 또는 이름”으로만 주어질 때는 Character.isDigit(첫 글자)가 가장 간단하고 안전하다.
• 입출력은 BufferedReader + StringTokenizer + StringBuilder 조합이 안정적으로 빠르다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1620
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 7785번 회사에 있는 사람

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡
  • 백준 - 10816번 숫자 카드 2
  • HackerRank - Hash Tables: Ransom Note

난이도: ★★★☆☆ • solved on: 2025-12-29

문제 요약

• 문제 유형: 정렬, 해시(좌표 압축)
• 요구사항: 주어진 수열의 각 값에 대해, 중복 제거 후 정렬했을 때의 인덱스를 원래 순서대로 출력해야 한다.

사용 개념

1. 자료구조

   • HashSet : 중복 제거
   • ArrayList : 유니크 값 정렬
   • HashMap : 값 → 압축 인덱스 매핑
   • int[] : 숫자 배열 처리
   • StringTokenizer : 빠른 입력 파싱

2. 알고리즘/기법

   • 좌표 압축 (coordinate compression):
     • 중복 제거 → 정렬 → rank(0..k-1) 부여 → 원본 순서대로 출력
     • 원래 가지고 있던 값들의 의미는 모두 사라지고 오직 순서에 따른 정보만 남게 되는 테크닉

3. 핵심 키워드

   • value-to-rank mapping (값→순위 매핑)
   • unique + sort + map

풀이 아이디어 및 코드

방법 1 : HashSet 중복 제거 + 정렬 + HashMap 매핑

1. 문제 분해

• 입력 수열을 문자열 배열로 받고 HashSet으로 중복 제거한다.
• 유니크 값 리스트(arrList)를 정렬한다.
• 정렬된 유니크 리스트의 인덱스를 HashMap에 저장해 값→순위 매핑을 만든다.
• 원본 배열을 순회하면서 map.get(num)으로 순위를 출력한다.

2. 핵심 로직 흐름

   arr = 입력(문자열)
   set = 중복 제거
   arrList = set -> 리스트 변환
   arrList 정렬
   >
   map[value] = 정렬 인덱스
   for num in arr:
       출력 map[num]

3. 예외 처리
   • 중복이 많아도 HashSet으로 유니크만 정렬하므로 정렬 대상이 줄어든다.

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());
        String line = sc.nextLine();
        String[] arr = line.split(" ");
        HashSet<String> set = new HashSet<>(Arrays.asList(arr));
        ArrayList<String> arrList = new ArrayList<>(set);

        arrList.sort((a,b)-> {
            return Integer.valueOf(a).compareTo(Integer.valueOf(b));
        });
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < arrList.size(); i++) {
            map.put(arrList.get(i), i);
        }
        StringBuilder sb = new StringBuilder();
        for(String num : arr){
            sb.append(map.get(num)).append(" ");
        }
        System.out.println(sb);
    }
}

방법 2 : int 배열 복사본 정렬 + 중복 스캔으로 rank 매핑 + 빠른 입력

1. 핵심 개선 포인트

• Scanner/split 대신 BufferedReader + StringTokenizer로 입력 비용을 줄인다.
• String 대신 int로 처리해 변환/비교 비용을 줄인다.
• HashSet 없이도, 정렬된 배열을 한 번 스캔하며 중복을 제거하면서 map을 만들 수 있다.

2. 핵심 로직 흐름

   origin = 원본 int[]
   sorted = origin 복사본
   sorted 정렬
   >
   rank = 0
   for i in 0..n-1:
       if i==0 or sorted[i] != sorted[i-1]:
           map[sorted[i]] = rank++
   for x in origin:
       출력 map[x]

3. 예외 처리
   • 음수/큰 수여도 정렬 후 인덱스 기반이므로 문제 없음
   • 출력 마지막 공백은 조건으로 처리

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

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

        int[] origin = new int[n];
        int[] sorted = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(st.nextToken());
            origin[i] = v;
            sorted[i] = v;
        }

        Arrays.sort(sorted);

        HashMap<Integer, Integer> map = new HashMap<>(n * 2);
        int rank = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1]) {
                map.put(sorted[i], rank++);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(origin[i]));
            if (i + 1 < n) sb.append(' ');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: 대략 O(NlongN)

  • 중복 제거 O(N)
  • 유니크 정렬 O(U log U)
  • 매핑/출력 O(N)
  • 단, Scanner와 split, Integer.valueOf 반복 호출로 체감 시간이 늘 수 있다.

• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

어려웠던 점

• 처음 시행착오에서는 정렬된 유니크 리스트에서 순위를 얻기 위해 arrList.indexOf(num) 같은 방식으로 접근했는데, 이 경우 TimeOut이 발생한다.

  • 이유는 원소마다 리스트를 선형 탐색하게 되어 전체가 최악 O(N²) 로 커질 수 있었기 때문이다.

• 결국 “값의 순위를 찾는 과정”은 반복 탐색이 아니라, HashMap으로 값→순위를 미리 만들어서 즉시 조회해야 한다는 점이 핵심이었다.

• 추가로, 입력이 커질 때 Scanner + split 조합이 병목이 될 수 있다는 점도 체감할 수 있는 포인트였다.

배운 점 및 팁

• 좌표 압축은 정렬 + 매핑이 핵심이며, 출력 단계는 반드시 O(1) 조회로 끝나야 한다.
• 대량 입력 문제는 알고리즘이 같아도 입력 방식(Scanner vs BufferedReader) 에서 제출 성능 차이가 크게 난다.
• 숫자는 가능하면 String으로 들고 가지 말고 int로 즉시 파싱하는 편이 깔끔하고 빠르다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/18870
• 참고 블로그/깃허브: 좌표 압축 개념 참고 https://wikidocs.net/214469

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 - 11650번 좌표 정렬하기
  • 백준 - 11651번 좌표 정렬하기 2
  • 백준 - 10814번 나이순 정렬

• 확장 문제 (GPT 추천) :

  • Hackerrank - No Idea!
  • Hackerrank - Sorting: Comparator

난이도: ★★☆☆☆ • solved on: 2025-12-29

문제 요약

• 문제 유형: 정렬 (Sorting), 안정 정렬 (Stable Sort)
• 요구사항: 회원을 나이 오름차순으로 정렬하되, 나이가 같으면 가입한 순 (입력 순) 을 유지해서 출력한다.

사용 개념

1. 자료구조

   • String[][] : 입력순 인덱스, "나이 이름" 원문을 한번에 저장
   • Member[] : 나이/이름을 분리 저장 (커스텀 클래스)

2. 알고리즘/기법

   • 정렬 (Comparator)
   • 안정 정렬 (stable sort) 활용

3. 핵심 키워드

   • 안정 정렬 (stable sort), 입력 순서 유지 (input order)

풀이 아이디어 및 코드

방법 1 : 배열을 활용한 인덱스 저장

1. 문제 분해

• 각 입력에 대해 원래 순서를 arr[i][0]에 문자열로 저장한다.
• Comparator에서 나이를 비교하고, 같으면 저장한 순서를 비교한다.

2. 핵심 로직 흐름

   arr[i] = (i, "age name")
   정렬: age 오름차순, age 같으면 i 오름차순
   arr[i][1] 출력

3. 예외 처리
   • 나이가 같은 경우 입력 순서 유지

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[][] arr = new String[n][2];
        for(int i = 0; i < n; i++){
            arr[i][0] = i + "";
            arr[i][1] = br.readLine();
        }
        Arrays.sort(arr, (a, b) -> {
            String[] person1 = a[1].split(" ");
            int person1Age = Integer.parseInt(person1[0]);

            String[] person2 = b[1].split(" ");
            int person2Age = Integer.parseInt(person2[0]);

            if(person1Age != person2Age){
                return person1Age - person2Age;
            }
            return Integer.parseInt(a[0]) - Integer.parseInt(b[0]);
        });

        StringBuilder sb = new StringBuilder();
        for(String[] data : arr){
            sb.append(data[1]).append("\n");
        }
        System.out.println(sb);
    }
}

방법 2 : 입력 파싱 1회 + 안정 정렬 활용

1. 개선 포인트 (시간/공간)

• 방법 1은 정렬 비교할 때마다 split()과 parseInt()가 반복되어 비용이 크다.

• 입력 받을 때 나이/이름을 미리 분리 저장하면 비교가 매우 가벼워진다.

• 또한 이 문제는 “나이가 같으면 입력 순서 유지”인데, Java에서 객체 배열 정렬은 안정 정렬이므로 나이만 비교해도 입력 순서가 유지된다. → “순서 인덱스”를 따로 저장할 필요가 없어진다.

2. 핵심 로직 흐름

   members[i] = (age, name)
   안정 정렬: age 오름차순만 비교
   출력: age + " " + name

3. 예외 처리
   • 나이가 같을 때는 Comparator가 0을 반환 → 안정 정렬이라 입력 순서 유지

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

public class Main {

    static class Member {
        int age;
        String name;
        Member(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Member[] members = new Member[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            members[i] = new Member(age, name);
        }

        Arrays.sort(members, (a, b) -> a.age - b.age); // 나이만 비교 (안정 정렬 활용)

        StringBuilder sb = new StringBuilder();
        for (Member m : members) {
            sb.append(m.age).append(' ').append(m.name).append('\n');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N log N * L)

  • 비교 함수가 호출될 때마다 split() 등 문자열 처리 비용이 반복됨 (L = 문자열 길이)

• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N log N)

• 공간 복잡도: O(N)

어려웠던 점

• 입력 순서 정보를 어떻게 유지할지 설계하는 부분에서 난감했고, 처음에는 배열에 인덱스를 같이 저장하는 방식으로 해결했다.

배운 점 및 팁

• 이 문제의 핵심은 나이 같으면 입력 순서 유지인데, 안정 정렬(stable sort) 을 활용하면 인덱스 저장 자체가 필요 없어질 수 있다.
• Comparator 안에서 split() 같은 문자열 파싱을 하면, 정렬 과정에서 같은 문자열을 계속 쪼개게 되어 비효율이 커진다. 따라서 파싱은 최초 저징시 진행하는 것이 좋다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/10814
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 1181번 단어 정렬
  • 백준 - 11650번 좌표 정렬하기
  • 백준 - 10825번 국영수

• 확장 문제 (GPT 추천)

  • 백준 - 18870번 좌표 압축
  • Hackerrank - Sort
  • Hackerrank - Comparator

난이도: ★★☆☆☆ • solved on: 2025-12-29

문제 요약

• 문제 유형: 정렬 (Sorting), 문자열 (String), 중복 제거 (Deduplication)
• 요구사항: 단어를 길이 오름차순, 길이가 같으면 사전순 오름차순으로 정렬하되 중복 단어는 한 번만 출력해야 한다.

사용 개념

1. 자료구조

   • ArrayList<String>: 단어 저장 및 정렬
   • HashSet<String>: 중복 제거(개선 풀이)

2. 알고리즘/기법

   • 커스텀 정렬 기준 (Comparator)
   • 중복 제거 후 정렬

3. 핵심 키워드

   • 사전순 정렬 (lexicographical order)
   • 다중 키 정렬 (multi-key sort)
   • 해시 기반 중복 제거 (hash-based dedup)

풀이 아이디어 및 코드

방법 1 : 처음 풀이

1. 문제 분해

• 입력을 받으면서 ArrayList에 저장하되, contains로 중복이면 건너뛴다.
• Comparator로 (길이 → 사전순) 기준으로 정렬한다.

2. 핵심 로직 흐름

   for each word:
       if words.contains(word) continue
       words.add(word)
   >
   words.sort(길이 오름차순, 같으면 사전순)
   출력

3. 예외 처리
   • 중복 단어는 contains로 제거

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<String> words = new ArrayList<>();

        for(int i = 0; i < n; i++){
            String word = br.readLine();
            if(words.contains(word)){
                continue;
            }
            words.add(word);
        }

        words.sort(new StringComparator());

        StringBuilder sb = new StringBuilder();
        for(String word : words){
            sb.append(word).append("\n");
        }
        System.out.println(sb);
    }

    public static class StringComparator implements Comparator<String>{
        @Override
        public int compare(String o1, String o2) {
            if(o1.length() != o2.length()){
                return o1.length() - o2.length();
            }
            if(!o1.equals(o2)){
                return o1.compareTo(o2);
            }
            return 0;
        }
    }
}

방법 2 : HashSet으로 중복 제거 후 정렬

1. 개선 포인트 (시간/공간)

• 방법 1의 병목은 words.contains(word)가 O(N) 이라서, 전체가 최악 O(N²) 로 커질 수 있다는 점이다.
• 중복 제거는 HashSet이 평균 O(1) 이므로 입력 단계가 훨씬 빨라진다.

2. 핵심 로직 흐름

   set에 단어 N개 추가(중복 자동 제거)
   set -> list로 변환
   list.sort(길이 오름차순, 같으면 사전순)
   출력

3. 예외 처리
   • HashSet이 중복을 자동으로 제거하므로 별도 처리 불필요

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

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

        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(br.readLine()); // 중복 자동 제거
        }

        ArrayList<String> words = new ArrayList<>(set);

        words.sort((a, b) -> {
            if (a.length() != b.length()) return a.length() - b.length();
            return a.compareTo(b);
        });

        StringBuilder sb = new StringBuilder();
        for (String w : words) sb.append(w).append('\n');
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

• 시간 복잡도: 최악 O(N² + M log M)

  • 중복 체크 contains가 누적되어 최악 O(N²) 가능
  • M = 중복 제거 후 단어 수

• 공간 복잡도: O(M)

방법 2

• 시간 복잡도: 평균 O(N + M log M)

  • HashSet 삽입 평균 O(1) × N
  • 정렬 O(M log M)

• 공간 복잡도: O(M)

어려웠던 점

• 없음

배운 점 및 팁

• 중복 제거 + 정렬 문제는 보통

  • 입력 단계: HashSet (또는 TreeSet/정렬 필요 시)로 중복 처리
  • 출력 단계: List로 옮겨 sort 이 조합이 가장 자주 쓰인다고 한다.

• 비교 함수에서 if(!o1.equals(o2)) return o1.compareTo(o2); 부분은, 길이가 같다면 그냥 return o1.compareTo(o2); 로 충분하다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1181
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 10825번 국영수
  • 백준 - 11650번 좌표 정렬하기
  • 백준 - 10814번 나이순 정렬

• 확장 문제 (GPT 추천)

  • 백준 - 18870번 좌표 압축
  • Hackerrank - Java Comparator
  • Hackerrank - Java Sort

난이도: ★★☆☆☆ • solved on: 2025-12-29

문제 요약

• 문제 유형: 정렬(Sorting), 구현
• 요구사항: N개의 점을 x 오름차순, x가 같으면 y 오름차순으로 정렬해 출력한다.

사용 개념

1. 자료구조

   • int[][] : 좌표 저장

2. 알고리즘/기법

   • 커스텀 정렬 기준 (Comparator) 기반 정렬

3. 핵심 키워드

   • 다중 키 정렬 (multi-key sort), 비교 함수 (comparator)

풀이 아이디어

1. 문제 분해

• 커스텀한 Comparator를 활용한다.
• (x, y) 좌표쌍을 배열에 저장한다.
• 정렬 기준을 x -> y 순으로 정의한다.

2. 핵심 로직 흐름

   입력 N
   좌표 N개를 arr[i][0]=x, arr[i][1]=y에 저장
   Arrays.sort(arr, (a,b) -> a[0] 다르면 a[0]-b[0], 같으면 a[1]-b[1])
   정렬된 순서대로 출력

3. 예외 처리
   • 특별한 예외 처리 없음 (입력 범위 내에서 정렬만 수행)

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i++){
            String[] temp = br.readLine().split(" ");
            int x = Integer.parseInt(temp[0]);
            int y = Integer.parseInt(temp[1]);
            arr[i][0] = x;
            arr[i][1] = y;
        }
        Arrays.sort(arr, new AxisComparator());

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append(arr[i][0] + " ");
            sb.append(arr[i][1] + "\n");
        }
        System.out.println(sb);
    }

    public static class AxisComparator implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            if(o1[0] != o2[0]){
                return o1[0] - o2[0];
            }
            if(o1[1] != o2[1]){
                return o1[1] - o2[1];
            }
            return 0;
        }

    }
}

시간·공간 복잡도

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

어려웠던 점

• 없음

배운 점 및 팁

• 입력 파싱을 split() 대신 StringTokenizer로 바꾸면 메모리/시간이 더 안정적일 수 있다. (특히 N=100,000)
• 비교에서 o1[0] - o2[0] 대신 Integer.compare(o1[0], o2[0])를 쓰면 오버플로우 위험을 일반적으로 피할 수 있다. (이 문제 범위에서는 큰 문제는 잘 안 생김)

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/11650
• 참고 블로그/깃허브: 없음

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • 백준 - 11651번 좌표 정렬하기 2
  • 백준 - 10814번 나이순 정렬
  • 백준 - 18870번 좌표 압축

• 확장 문제 (GPT 추천)

  • 백준 - 10825번 국영수
  • 백준 - 1181번 단어 정렬
  • Hackerrank - Java Comparator

난이도: ★☆☆☆☆ • solved on: 2025-12-28

문제 요약

• 문제 유형: 문자열 처리, 정렬
• 요구사항: 입력된 수의 각 자리 숫자를 내림차순으로 정렬하여 출력해야 한다.

사용 개념

1. 자료구조

   • String
   • int[10] (카운팅 배열)

2. 알고리즘/기법

   • 버블 정렬 형태의 반복 교환
   • 카운팅 정렬

3. 핵심 키워드

   • 자리수 분해
   • 내림차순 정렬 (descending sort)
   • 문자열 불변 (immutable)

풀이 아이디어 및 코드

풀이 1 : 버블 정렬

1. 문제 분해

• 입력 문자열을 순회하며 이웃하는 수 간의 대소관계를 비교한다.

2. 핵심 로직 흐름

   if(String[i] < String[i+1]) 
   swap String[i] and String[i+1]

3. 예외 처리
   • 각 순회에서 마지막 인덱스에 도달한 경우, 스왑을 점검하지 않고 마친다.

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int count = 0;
        while(true){
            count = 0;
            for(int i = 0; i < s.length(); i++){
                if(i == s.length()-1){
                    break;
                }
                if(s.charAt(i) < s.charAt(i+1)){
                    s = swap(i, i+1, s);
                    count++;
                }
            }
            if(count == 0){
                break;
            }
        }
        System.out.println(s);
    }
    public static String swap(int idx1, int idx2, String s){
        char temp = s.charAt(idx1);
        s = s.substring(0, idx1) + s.charAt(idx2) + s.substring(idx1 + 1);
        s = s.substring(0, idx2) + temp + s.substring(idx2 + 1);
        return s;
    }
}

풀이 2 : 카운팅 정렬

1. 문제 분해

• 입력 문자열을 한 글자씩 보며 0~9 등장 횟수를 cnt[10]에 누적한다.
• 9부터 0까지 역순으로, 등장 횟수만큼 출력에 붙이면 내림차순이 된다.

2. 핵심 로직 흐름

   cnt[digit]++
   for d = 9..0:
       append d, cnt[d]번

3. 예외 처리
   • 한 자리 입력도 동일하게 처리

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();

        int[] cnt = new int[10];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - '0']++;
        }

        StringBuilder sb = new StringBuilder();
        for (int d = 9; d >= 0; d--) {
            for (int k = 0; k < cnt[d]; k++) sb.append(d);
        }

        System.out.print(sb);
    }
}

시간·공간 복잡도

풀이 1

• 시간 복잡도: 최악 기준 대략 O(N³)

• 공간 복잡도: O(N) (문자열이 반복 생성됨)

풀이 2

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

어려웠던 점

• 특정 인덱스에 있는 char를 교체하는 메소드를 몰라 참고 블로그를 확인하여 swap함수를 구현했었다 (풀이 1)

배운 점 및 팁

• String은 불변(immutable)이라 substring 기반 교체는 매번 새 문자열이 만들어져 비용이 커질 수 있다.
• 숫자 범위가 0~9로 고정인 경우, 일반 정렬보다 카운팅 정렬이 더 간단하고 빠르다.

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1427
• 참고 블로그/깃허브: https://m.blog.naver.com/jjekjjek7/222923433163

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 백준 2750번 - 수 정렬하기
  • 백준 1181번 - 단어 정렬

• 확장 문제 (GPT 추천) :

  • 백준 10989번 - 수 정렬하기 3
  • 백준 2108번 - 통계학