해야할 작업은 파일에 자바 클래스 저장하기, 파일에서 읽어온 데이터는 자바 클래스 형식으로 변환하는 것이 목표였습니다. 간단한 프로젝트였는데, 스프링과 비슷하게 구현하는데 어려움이있었습니다.

팀원들과 mvc 패턴으로 해당 프로젝트를 구현하기 위해 많은 회의를 했던 것 같고, 파일에 데이터를 저장하고 읽어오는 것을 jpaRepository처럼 구현하는데 많은 고민을 했던 것 같습니다.

1. 카카오 API를 호출해서 책 정보 검색
2. 검색한 책 정보 출력
3. 데이터베이스의 값 저장 유무 입력 받고
4. 데이터베이스에 값을 저장해야되면, 저장하고 값 출력

사용한 코드 구조 입니다.

• Main 서비스 실행
• Service 서비스 로직들을 담고 있음
• ApiClient Api 호출 관련
• Database 데이터베이스 호출 관련
• Book 책 엔티티
• Constant 사용하는 상수들을 위한 클래스
• ExceptionHandler 서비스에서 발생하는 예외 핸들러

import한 라이브러리들입니다.

API 통신을 위한 라이브러리 그리고 mysql 데이터베이스 연결을 위한 import들이 있습니다.

순수 자바만을 이용해서 데이터베이스 통신을 하는 코드를 작성해보니, spring에서 정말 많은 기능을 대신해준다는 것을 느낄 수 있었습니다.

1. 사용자로부터 위치에 대한 키워드와 반경 입력 받기 ex) 정자동, 수내동 등등
2. 입력 받은 주소의 위도, 경도 값을 카카오 API를 통해서 받아오기
3. 받아온 위도, 경도 값을 기준으로 사용자가 입력한 반경 내 약국 카카오 API를 통해 조회하기
4. 받아온 약국 정보를 화면에 출력하고, 지도 url 주소를 입력 받으면, 브라우저를 열어 지도 페이지 보여주기

사용한 외부 라이브러리들은 다음과 같습니다. http 통신을 위해서 httpclient을 사용하였고, json 오브젝트를 다루기 위해 json을 사용하였습니다.

프로젝트 코드는 다음과 같습니다. 구현해야할 기능이 간단해서 Main 하나의 클래스 내부에서 메소드 단위로 작업들을 처리하게 설계하였습니다.

약국 정보를 받아오는 초대입니다. 약국 정보를 출력할때, 출력해야할 정보가 많아서 따로 Pharmacy라는 약국 정보를 담는 클래스를 만들었습니다. 또 파라미터로 넘겨줘야할 값이 많기에 빌더 패턴을 사용하여 Pharmacy 객체를 생성하였습니다. Http request를 보낼 때, 파라미터로 넘길 값들을 상수화하여서 관리하였습니다.

실제 API 통신을 해서 받아온 json을 string으로 변환해서 return하는 메소드입니다.

스프링의 도움 없이 직접 httpclient, json을 이용해서 과제를 진행해보니, spring이 내부적으로 어떤 동작을 하는지 자세히 알 수 있었던 것 같습니다.

포스트를 작성하게 된 계기 그래프 관련 알고리즘에는 다양한 알고리즘이 있다.

• bfs
• dfs
• prim
• kruskal
• dijkstra
• bellman-ford 위 알고리즘들이 그래도 코테 문제에서 흔히 등장하는 알고리즘들인 것 같은데, 지금까지는 dfs, bfs 문제들만 주로 풀어왔었기에, mst를 구하는 prim, kruskal과 최단 거리를 구하는 dijkstra, bellman-ford 알고리즘 문제들을 검색 없이는 해결하기 힘들었었고, 코테를 준비하는데 다양한 그래프 알고리즘들을 다룰 줄 알아야겠다는 필요성을 느꼈다.

BFS

너비 우선 탐색 알고리즘이다. 한 정점에서 퍼져나가는 방식으로 탐색을 진행한다. queue 자료구조를 사용해서 구현할 수도 있지만, 개인적으로는 두개의 리스트 구조를 이용하는 방식을 선호한다

void bfs() {
    List<Integer> currentNodes = new ArrayList<>();
    ~~~~ 
    while (!currentNodes.isEmpty()) {
        List<Integer> temp = new ArrayList<>();
        for (int currentNode : currentNodes) {
            for (int nextNode : canGo(currentNode) {
                if (visited[nextNode] == 0) {
                    visited[nextNode] = 1;
                    temp.add(nextNode);
                }
            }

        }

        currentNodes = temp;

    }

}

위와 같은 방식으로 bfs 탐색을 진행하는게 queue 자료구조를 사용하는 것보다 기억하기 쉬웠던 것 같다. 그리고 특정 노드가 시작 노드로부터 얼마나 떨어져있는지 같은 정보를 index 같은 변수 하나만 추가하면 바로 알 수 있다는 점도 문제 풀이에 도움됐었던 경험이 많아서 주로 bfs는 위와 같은 방식으로 코드를 작성하고 있다.

DFS

깊이 우선 탐색 방식이다. 미로 찾기 처럼 갈 수 있는 한 방향으로 계속 탐색하다가 더이상 탐색할 수 없는 지점을 맞이하면 되돌아오는 방식으로 탐색을 진행한다. dfs는 주로 재귀함수를 이용해서 구현하였다.

void dfs(int index) {
    if (visited[index] == 1) {
        return;
    }
    visited[index] = 1;
    for (int nextNode : canGo(index)) {
        dfs(nextNode);
    }

}

문제에 따라 조금씩 변형되긴하지만, 위와 같은 코드가 dfs 문제에 적용하는 가장 근본적인 코드인 것 같다.

kruskal

크루스칼 알고리즘은 MST를 만드는 알고리즘 중 하나이다.

MST란? minimum spanning tree로 n개의 정점을 가진 그래프가 있으면 n-1 개의 간선으로 이루어지면서 n개의 정점이 모두 연결된 tree 중에서 간선의 가중치 합이 가장 작은 tree를 의미한다.

MST를 만드는 알고리즘에는 kruskal, prim알고리즘이 존재하는데, kruskal은 greedy하게 간선을 선택하는 방식으로 진행된다.

크루스칼 알고리즘의 진행 방식은 다음과 같다.

1. 간선을 가중치를 기준으로 정렬한다.
2. 간선을 탐색하면서, 간선을 이루는 두 정점이 같은 그룹에 있는지를 판단한다.
   • 같은 그룹에 있으면 사이클이 형성되면서 mst를 이룰 수 없다.
   • 같은 그룹에 속하는지에 대한 판단은 union-find 알고리즘을 이용하면 쉽게 할 수 있다.
3. 같은 그룹에 속하면 넘어가고, 같은 그룹에 속하지 않으면 간선을 mst에 추가하고, 두 정점을 union한다.

prim

크루스칼 알고리즘과 동일하게 mst를 만드는 알고리즘 중 하나인데, prim 알고리즘은 정점 선택 방식으로 진행된다.

프림 알고리즘의 진행 방식은 다음과 같다.

1. 임의의 한 정점을 시작 정점으로 설정한다.
2. 해당 정점의 간선 중 가장 값이 가장 간선을 mst로 추가한다.
3. 이 과정을 n개의 노드가 추가될 때 까지 반복한다.

크루스칼과 프림 모두 mst를 이루는 알고리즘인데, 간선의 숫자가 많은 경우에는 prim 알고리즘이 적합하다. 그리고 prim 알고리즘에서 정점별 간선을 heap을 이용해서 구현하면, 좀 더 빠르게 mst를 구할 수 있다.

dijkstra

다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단 거리들을 알고 싶을 때 사용하는 알고리즘이다. 다만 간선의 가중치에 음의 값이 포함된 경우에는 적용될 수 없다.

다익스트라 알고리즘의 진행방식은 다음과 같다.

1. 출발 노드를 설정하고, 출발노드에서 다른 모든 노드로 가는 값을 아주 큰 값으로 설정한다.
2. 출발노드와 인접한 노드들을 보고, 최소값이 갱신되어야하면, 큐에 추가하면서 최소값을 갱신해준다.
3. 이 과정을 큐에 담긴 값이 없을때까지 반복한다.

문제 링크

분류

자료 구조, 깊이 우선 탐색, 분리 집합, 그래프 이론, 그래프 탐색

문제 설명

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다.

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

풀이

입력으로 주어지는 지도에서 밖으로 나가는 방향의 입력은 주어지지 않는 다고 했으니, 순환 구조가 존재할 것이라고 판단하였다. 순환 구조에서는 아무 한 점이나 SAFE ZONE으로 지정하면 되겠다고 생각하여서 순환 구조를 발견할때마다 출력할 변수를 +1 해주고, 기존에 존재하는 순환구조를 방문하는 경우에는 변수의 크기를 키우지 않는 방식으로 해결할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    int N;
    int M;
    String[] map;
    int[][] visited;
    int[][] group;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};
    public static HashMap<Character, Integer> convertTable = new HashMap<>() {
        {
            put('U', 0);
            put('L', 1);
            put('D', 2);
            put('R', 3);
        }
    };
    int answer;
    int index;
    public static void main(String[] args) {
        Main main = new Main();
        try {
            main.init();
            main.solution();
        } catch (IOException e) {
            System.out.println("exception during I/O");
        }
    }


    void init() throws IOException {
        int[] inputArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = inputArray[0];
        M = inputArray[1];

        map = new String[N];
        for (int i = 0; i < N; i++) {
            map[i] = BR.readLine();
        }

        visited = new int[N][M];
        group = new int[N][M];
        answer = 0;
        index = 0;
    }

    void solution() throws IOException {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visited[i][j] == 0) {
                    group[i][j] = index;
                    dfs(i, j);
                    index += 1;
                }
            }
        }
        System.out.println(answer);
    }

    void dfs(int i, int j) {
        if (visited[i][j] == 1) {
            if (group[i][j] == index) {
                answer += 1;
            }
            return;
        }
        visited[i][j] = 1;
        group[i][j] = index;
        int[] nextNode = getNextNode(i, j);
        dfs(nextNode[0], nextNode[1]);

    }

    int[] getNextNode(int i, int j) {
        Integer direction = convertTable.get(map[i].charAt(j));
        return new int[]{i + dx[direction], j + dy[direction]};

    }

}

도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?

알고리즘 문제를 풀다가 위와 비슷한 상황을 직면한 적이 종종있었는데, 그럴때마다 풀릴 듯이 문제가 풀리지 않았어서 배낭 문제를 푸는 법에 대해서 한번 정리해보려고 한다.

위와 같은 문제를 직면할 때마다 들었던 생각은 가장 비싼 보석을 먼저 담으면서, 가방이 찢어지게되는 상황이 발생하면 가방에 있는 보석을 빼는 방식을 생각했었던 것 같은데, 반례가 존재하는 풀이인 것 같다.

위 문제는 dp를 이용해서 가장 효율적으로 풀이할 수 있다.

배낭 문제에서 사용되는 점화식은 아래와 같다.

P[i,w]는 i개의 보석이 있고, 배낭의 무게 한도가 w 일때의 최대 이익을 의미한다. 위 점화식의 의미는 다음과 같다.

• i번째 보석이 배낭의 무게한도보다 무거우면 넣을 수 없으므로, P[i-1,w]의 값을 가져온다
• i번째 보석을 추가하는게 나은지 아닌지를 판단하고, 그에 맞는 최대값을 리턴한다.

점화식을 보면 알 수 있듯이, (i,w) 크기의 이중 배열이 선언되어야한다.

문제 링크

분류

브루트포스 알고리즘, 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제 설명

《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.

《수 나누기 게임》의 규칙은 다음과 같습니다.

• 게임을 시작하기 전 각 플레이어는 1부터 1000000 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.
• 매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.
• 결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 0이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.
• 승리한 플레이어는 1점을 획득하고, 패배한 플레이어는 1점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.
• 본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다.

《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

입력

첫 번째 줄에 플레이어의 수 N이 주어집니다.

두 번째 줄에 첫 번째 플레이어부터 N 번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 x1, ⋯, xN이 공백으로 구분되어 주어집니다.

출력

첫 번째 플레이어부터 N번째 플레이어까지 게임이 종료됐을 때의 각 플레이어의 점수를 공백으로 구분하여 출력해주세요.

풀이

소수 판정에서 이용되는 에라토스테네스의 채 개념을 이용해서 문제를 풀 수 있었다. 결국 주어진 카드들 중에서 소수처럼 다른 수들로 나눠지지 않는 숫자만 점수를 얻는다는 아이디어를 통해서 해결할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    int N;
    int[] cards;
    int[] toPrint;
    int[] scores;
    int maxCard;
    HashSet<Integer> cardHashSet;
    public static void main(String[] args) {
        Main main = new Main();
        try {
            main.init();
            main.solution();
        } catch (Exception e) {
            System.out.println("exception during I/O");
        }

    }

    /*
    카드의 숫자들을 전체 숫자라고 정의하고, 소수 여부를 판단하면되는 게임이 아닌가?

     */

    void init() throws Exception {
        N = Integer.parseInt(BR.readLine());
        String inputArray = BR.readLine();
        cards = Arrays.stream(inputArray.split(" ")).mapToInt(Integer::parseInt).toArray();
        toPrint = Arrays.stream(inputArray.split(" ")).mapToInt(Integer::parseInt).toArray();
        maxCard = Arrays.stream(cards).max().getAsInt();
        scores = new int[maxCard+1];
        cardHashSet = new HashSet<>();
        Arrays.sort(cards);
        for (int card : cards) {
            cardHashSet.add(card);
        }
    }

    void solution() throws Exception {
        for (int card : cards) {
            for (int i = card * 2; i <= maxCard; i += card) {
                if (cardHashSet.contains(i)) {
                    scores[card] += 1;
                    scores[i] -= 1;
                }
            }
        }


        for (int card : toPrint) {
            BW.write(scores[card]+" ");
        }
        BW.flush();
        BW.close();
    }
}

포스트를 작성하게된 계기 평소에 알고리즘 문제 풀이를 진행할 때, 소수 관련 문제는 많이 풀어보지 않았다. 제곱근을 이용해 소수를 구하는 방식을 주로 사용하였기에, 소수 관련 문제 난이도가 올라갈 수록 풀이에 어려움을 겪었다. 에라토스테네스의 채를 정리하여 다음에 소수 관련 문제를 맞이하였을 때 보다 효율적인 풀이를 작성하기 위해서 포스트를 작성하게 되었다.

에라토스테네스의 채

에라토스테네스의 채는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 숫자 N 까지의 소수를 찾는데 아주 효율적인 방법이다.

에타토스테네스의 채는 다음과 같은 순서로 진행된다.

1. 2부터 N 까지의 수를 나열한다.
2. 2부터 시작하며 N까지, 자신의 배수를 지워나간다.
3. 지워지지 않은 수는 모두 소수이다.

이 방법을 코드로 옮기면 다음과 같다.

// 구하고자 하는 숫자 범위
int N = 120;
boolean prime[] = new boolean[N];
prime[0] = prime[1] = true;

for(int i=2; i*i<=N; i++){
    if(!prime[i]){
        for(int j=i*i; j<=N; j+=i) prime[j] = true;                
    }        
}    

문제 링크

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

문제 설명

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

풀이

트리 구조로 정점들이 이루어져있을때, 정점간의 최대거리를 구하는 문제였다. 임의의 한 점을 트리의 root로 설정하고, 정점의 서브트리를 탐색하는 재귀 함수를 설정하였다. 재귀 함수는 정점의 자녀 중 가장 길이가 먼 길이를 리턴하게했으며, root를 방문하지 않고 최대 거리가 나오는 경우가 있을 수 있기에, 재귀 함수 내부에서 서브 트리 거리의 합도 계산함으로서 답을 구할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    int V;
    long answer;
    HashMap<Integer, Node> nodeHashMap;
    HashSet<Integer> visited;

    public static void main(String[] args) {
        Main main = new Main();
        try {
            main.init();
            main.solution();
        } catch (Exception e) {
            System.out.println("exception during I/O");
        }

    }

    void init() throws Exception {
        V = Integer.parseInt(BR.readLine());
        answer = 0L;
        nodeHashMap = new HashMap<>();
        visited = new HashSet<>();

        for (int i = 0; i < V; i++) {
            int[] inputArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int from = inputArray[0];

            if (!nodeHashMap.containsKey(from)) {
                Node newNode = new Node(from);
                nodeHashMap.put(from, newNode);
            }

            Node node = nodeHashMap.get(from);

            for (int j = 1; j + 1 < inputArray.length; j += 2) {
                node.neighbor.put(inputArray[j], inputArray[j + 1]);
            }

        }

    }

    void solution() throws Exception {
        Node root = nodeHashMap.get(1);
        visited.add(1);
        long fromRoot = travel(root);
        if (fromRoot > answer) {
            answer = fromRoot;
        }
        System.out.println(answer);
    }

    long travel(Node parent) {
        HashMap<Integer, Integer> neighbors = parent.getNeighbor();
        PriorityQueue<Long> maxSubTreeDistance = new PriorityQueue<>(Collections.reverseOrder());

        for (Integer child : neighbors.keySet()) {
            if (!visited.contains(child)) {
                visited.add(child);
                Node nextNode = nodeHashMap.get(child);
                long travelDistance = travel(nextNode);
                travelDistance += neighbors.get(child);
                maxSubTreeDistance.add(travelDistance);
            }
        }

        if (maxSubTreeDistance.isEmpty()) {
            return 0L;
        } else {
            long toReturn = maxSubTreeDistance.peek();
            if (maxSubTreeDistance.size() >= 2) {
                long subTreeDistance1 = maxSubTreeDistance.remove();
                long subTreeDistance2 = maxSubTreeDistance.remove();
                if (subTreeDistance1 + subTreeDistance2 > answer) {
                    answer = subTreeDistance1 + subTreeDistance2;
                }
            }
            return toReturn;
        }
    }

    static class Node {
        int number;
        HashMap<Integer, Integer> neighbor;

        public Node(int number) {
            this.number = number;
            this.neighbor = new HashMap<>();
        }

        public int getNumber() {
            return number;
        }

        public HashMap<Integer, Integer> getNeighbor() {
            return neighbor;
        }
    }


}

문제 링크

성능 요약

메모리: 28232 KB, 시간: 384 ms

분류

그리디 알고리즘, 정렬

문제 설명

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

• 다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

(2) 2번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

(3) 3번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

(4) 4번 마을에 도착하면

• 받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.

출력

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

풀이

O(N^2) 시간 복잡도로 해결할 수 있는 문제였다. truck 배열에 마을을 지나갈 때 트럭에 담겨있는 박스의 개수를 저장하였고, 배송요청을 배송지를 기준으로 정렬하였다. 출발지에서 최대 담을 수 있는 박스의 개수를 초과하였다면, 넘어가고, 그게 아니면 출발지부터 배송지까지 박스의 최대 개수를 구하고, 담을 수 있는 최대 박스의 개수에서 구한 값을 뺀 값을 truck 출발지부터 배송지까지 더해주면서 답을 구할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    int N;
    int C;
    int M;
    int[][] delivery;
    int[] truck;
    int[] delivered;

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        int[] inputArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = inputArray[0];
        C = inputArray[1];
        M = Integer.parseInt(BR.readLine());
        delivery = new int[M][3];
        truck = new int[N];
        delivered = new int[N];
        Arrays.fill(truck, 0);
        Arrays.fill(delivered, 0);

        for (int i = 0; i < M; i++) {
            int[] villageAndBoxes = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            delivery[i][0] = villageAndBoxes[0] - 1;
            delivery[i][1] = villageAndBoxes[1] - 1;
            delivery[i][2] = villageAndBoxes[2];

        }
    }

    void solution() throws Exception {
        long answer = 0;
        Arrays.sort(delivery, Comparator.comparing((int[] orders) -> orders[1]));
        for (int[] deliver : delivery) {
            int start = deliver[0];
            int destination = deliver[1];
            int amount = deliver[2];
            int currentWeight = truck[start];
            if (currentWeight != C) {
                int currentMaximum = currentWeight;
                for (int i = start + 1; i < destination; i++) {
                    if (truck[i] > currentMaximum) {
                        currentMaximum = truck[i];
                    }
                    if (currentMaximum == C) {
                        break;
                    }
                }
                if (currentMaximum != C) {
                    int toAdd = Math.min(C - currentMaximum, amount);
                    answer += toAdd;
                    for (int i = start; i < destination; i++) {
                        truck[i] += toAdd;
                    }

                }

            }


        }

        System.out.println(answer);
    }

}

문제 링크

분류

이분 탐색, 정렬

문제 설명

KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x₁, x₂, ..., x_M은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a₁, b₁), (a₂, b₂), ..., (a_N, b_N)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다.

사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 x_i와 동물의 위치 (a_j, b_j) 간의 거리는 |x_i-a_j| + b_j로 계산한다.

예를 들어, 아래의 그림과 같은 사냥터를 생각해 보자. (사대는 작은 사각형으로, 동물의 위치는 작은 원으로 표시되어 있다.) 사정거리 L이 4라고 하면, 점선으로 표시된 영역은 왼쪽에서 세 번째 사대에서 사냥이 가능한 영역이다.

사대의 위치와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수를 출력하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌표 값이 빈칸을 사이에 두고 양의 정수로 주어진다. 이후 N개의 각 줄에는 각 동물의 사는 위치를 나타내는 좌표 값이 x-좌표 값, y-좌표 값의 순서로 빈칸을 사이에 두고 양의 정수로 주어진다. 사대의 위치가 겹치는 경우는 없으며, 동물들의 위치가 겹치는 경우도 없다. 모든 좌표 값은 1,000,000,000보다 작거나 같은 양의 정수이다.

출력

출력은 단 한 줄이며, 잡을 수 있는 동물의 수를 음수가 아닌 정수로 출력한다.

풀이

사냥할 수 있는 동물의 개수를 구하는 문제이다. 이분 탐색을 이용해서 x 좌표를 기준으로 가장 가까운 사대를 찾고, 해당 사대에서 사냥할 수 있으면 answer += 1을 해주는 방식으로 해결할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    int M;
    int N;
    int L;
    int[] shootingRanges;
    int[][] animals;


    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        int[] inputArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        M = inputArray[0];
        N = inputArray[1];
        L = inputArray[2];

        shootingRanges = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        animals = new int[N][2];
        for (int i = 0; i < N; i++) {
            int[] animal = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            animals[i][0] = animal[0];
            animals[i][1] = animal[1];
        }

    }

    void solution() throws Exception{
        Arrays.sort(shootingRanges);
        Arrays.sort(animals, Comparator.comparing((int[] animal) -> animal[0]));
        int answer = 0;
        int index = 0;
        for (int[] animal : animals) {
            int calculatedDistance = calculateDistance(shootingRanges[index], animal);
            if (calculatedDistance <= L) {
                answer += 1;
            } else {
                if (index + 1 < M) {
                    if (calculateDistance(shootingRanges[index + 1], animal) <= L) {
                        answer += 1;
                        index += 1;
                    }
                }
            }
        }
        System.out.println(answer);
    }

    int calculateDistance(int shoot, int[] animal) {
        return Math.abs(shoot - animal[0]) + animal[1];
    }
}

문제 링크

분류

구현, 누적 합, 정렬

문제 설명

지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.

이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다.

공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력하는 프로그램을 작성하시오.

입력

첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 C_i와 그 크기를 나타내는 자연수 S_i가 주어진다(1 ≤ C_i ≤ N, 1 ≤ S_i ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다.

출력

N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.

풀이

자신보다 크기가 작은 공들의 크기의 합을 알아야하고, 이때 자신과 같은 색깔이면서 자신보다 크기가 작은 공들의 크기의 합은 빼주어야하는 문제였다. HashMap 자료구조를 이용해서 크기별로 자신보다 크기가 작은 공들 크기의 합을 저장해주는 방식으로 해결할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    int N;
    // 입력 받은 2중 배열을 저장하는 배열
    int[][] colorAndSizes;
    // 입력 받은 전체 공에 대하여 공 크기별 사로 잡을 수 있는 공들의 크기의 합
    HashMap<Integer, Long> totalSubSums;
    // 색깔 별 공 크기의 누적 합, N * 2이중 배열, 0번 인덱스에 공 크기, 1번 인덱스에 크기 누적합 저장
    long[][] colorSubSums;
    // 사로잡을 수 있는 전체 공 크기의 합에서 뺄 같은 색깔이면서 자신보다 작은 크기의 공들 크기의 합
    HashMap<Integer, HashMap<Integer, Long>> sumToMinus;
    // 출력할 값 저장
    long[] toPrint;


    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        N = Integer.parseInt(BR.readLine());
        colorAndSizes = new int[N][3];
        colorSubSums = new long[N][2];
        sumToMinus = new HashMap<>();
        toPrint = new long[N];
        totalSubSums = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int[] array = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            colorAndSizes[i][0] = array[0];
            colorAndSizes[i][1] = array[1];
            colorAndSizes[i][2] = i;
            Arrays.fill(colorSubSums[i], 0L);
            sumToMinus.put(i, new HashMap<>());
        }

    }

    void solution() throws Exception{
        int currentBallSize = 0;
        long subSums = 0;
        Arrays.sort(colorAndSizes, Comparator.comparingInt(ball -> ball[1]));
        for (int[] colorAndSize : colorAndSizes) {
            int color = colorAndSize[0];
            int size = colorAndSize[1];
            if (currentBallSize < size) {
                currentBallSize = size;
                totalSubSums.put(currentBallSize, subSums);
            }
            if (colorSubSums[color - 1][0] < size) {
                colorSubSums[color - 1][0] = size;
                HashMap<Integer, Long> subSumsPerColor = sumToMinus.get(color - 1);
                subSumsPerColor.put(size, colorSubSums[color - 1][1]);
            }
            subSums += size;
            colorSubSums[color - 1][1] += size;
        }

        for (int[] colorAndSize : colorAndSizes) {
            int color = colorAndSize[0];
            int size = colorAndSize[1];
            int index = colorAndSize[2];

            Long totalSubSum = totalSubSums.get(size);
            Long sumToIgnore = sumToMinus.get(color - 1).get(size);

            toPrint[index] = totalSubSum - sumToIgnore;

        }

        for (long l : toPrint) {
            BW.write(Long.toString(l));
            BW.newLine();
        }
        BW.flush();
        BW.close();
    }


}

문제 링크

분류

자료 구조, 해싱, 트리, 트라이

문제 설명

집합 A,B와 문자열 S에 대하여, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• add A S: A에 S를 추가한다.
• delete A S: A에서 S를 제거한다.
• add B S: B에 S를 추가한다.
• delete B S: B에서 S를 제거한다.
• find S: A의 원소의 접두사와 B의 원소의 접미사를 이어 붙여 S가 되는 경우의 수를 출력한다. 원소가 다르거나 접두사(접미사)가 다르면 다른 경우로 센다. 빈 접두사(접미사)는 고려하지 않는다.

초기에 A,B 는 비어있으며, 이미 존재하는 원소를 추가하거나 존재하지 않는 원소를 제거하는 쿼리는 주어지지 않는다.

입력

첫째 줄에 쿼리의 개수 Q가 주어진다. (1≤Q≤1000)   둘째 줄부터 Q개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 쿼리에 등장하는 문자열은 영어 소문자로 이루어지며, 길이는 1 이상 1000 이하이다.

find 쿼리는 적어도 한 번 주어진다.

출력

find 쿼리의 답을 한 줄에 하나씩 출력한다.

풀이

시간 제한이 2초이고, 문자열의 최대 길이가 1000이기에, Hashtable을 이용해서 풀 수 있었다. 다른분의 풀이를 보니까 Trie 자료구조를 써서 풀이하셨던데, Trie를 쓴 풀이도 생각해봐야겠다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    int Q;
    Hashtable<String, Long> A;
    Hashtable<String, Long> B;
    String[] commands;

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        Q = Integer.parseInt(BR.readLine());
        A = new Hashtable<>();
        B = new Hashtable<>();
        commands = new String[Q];
        int i = 0;
        while (i < Q) {
            commands[i] = BR.readLine();
            i += 1;
        }
    }

    void find(String toFind) {
        long answer = 0;
        StringBuilder findA = new StringBuilder();
        StringBuilder findB = new StringBuilder(toFind);
        for (int i = 0; i < toFind.length(); i++) {
            findA.append(toFind.charAt(i));
            findB.deleteCharAt(0);
            String strA = findA.toString();
            String strB = findB.toString();
            if (A.containsKey(strA) && B.containsKey(strB)) {
                answer += A.get(strA) * B.get(strB);
            }
        }
        System.out.println(answer);
    }
    void add(String AB, String toAdd) {
        if (AB.equals("A")) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < toAdd.length(); i++) {
                sb.append(toAdd.charAt(i));
                String str = sb.toString();
                A.put(str, (A.containsKey(str) ? A.get(str) + 1 : 1));
            }
        } else {
            StringBuilder sb = new StringBuilder(toAdd);
            for (int i = 0; i < toAdd.length(); i++) {
                String str = sb.toString();
                B.put(str, (B.containsKey(str) ? B.get(str) + 1 : 1));
                sb.deleteCharAt(0);
            }
        }
    }

    void delete(String AB, String toDelete) {
        if (AB.equals("A")) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < toDelete.length(); i++) {
                sb.append(toDelete.charAt(i));
                String str = sb.toString();
                A.put(str, (A.containsKey(str) ? A.get(str) - 1 : 0));
            }
        } else {
            StringBuilder sb = new StringBuilder(toDelete);
            for (int i = 0; i < toDelete.length(); i++) {
                String str = sb.toString();
                B.put(str, (B.containsKey(str) ? B.get(str) - 1 : 0));
                sb.deleteCharAt(0);
            }
        }
    }

    void solution() {
        for (String command : commands) {
            String[] query = command.split(" ");
            if (query[0].equals("find")) {
                find(query[1]);
            } else if (query[0].equals("add")) {
                add(query[1], query[2]);
            } else {
                delete(query[1], query[2]);
            }
        }

    }


}

문제 링크

구분

코딩테스트 연습 > 연습문제

문제 설명

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1
n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간동안 일을 한 결과는 [2, 2, 2]입니다. 이 때 야근 지수는 2² + 2² + 2² = 12 입니다.

입출력 예 #2
n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간동안 일을 한 결과는 [1,1,2]입니다. 야근지수는 1² + 1² + 2² = 6입니다.

입출력 예 #3

남은 작업량이 없으므로 피로도는 0입니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이

heap를 이용해서 문제 풀이를 할 수 있다. heap를 이용해서 최대 값의 크기를 줄여나가는 방식으로 문제를 해결할 수 있었다. 다만 테스트 케이스의 전체 경우의 수가 작은 것으로 판단되어서 n의 숫자가 클 때 동작하는지는 추가 검증이 필요할 것 같다.

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> pq= new PriorityQueue<Integer>(Collections.reverseOrder());
        for (int work : works) {
            pq.add(work);
        }
        boolean done = false;
        for (int i = 0; i < n; i++) {
            Integer removed = pq.remove();
            if (removed == 0) {
                done = true;
                break;
            }
            removed -= 1;
            pq.add(removed);
        }
        if (done) {
            return 0;
        }
        for (Integer integer : pq) {
            answer += Math.pow(integer, 2);
        }
        return answer;
    }
}

문제 링크

성능 요약

메모리: 27716 KB, 시간: 328 ms

분류

자료 구조, 그리디 알고리즘, 큐

문제 설명

A, B, C로만 이루어졌고 길이가 |S|인 문자열 S가 있다. 당신은 이 문자열에 다음과 같은 시행을 할 수 있다.

• A와 그 뒤에 있는 B를 지운다.
• B와 그 뒤에 있는 C를 지운다.

각 문자는 최대 한 번만 지울 수 있다.

예를 들어 ABCBA를 보자. 각 문자에 왼쪽부터 1번, 2번, 3번. . . 과 같이 번호를 붙이면 다음과 같이 시행할 수 있다.

• 1번 A와 2번 B를 지운다. 이 경우 시행의 횟수는 1번이고, 남은 문자열은 CBA이다. 어떤 두 문자를 골라도 시행의 조건을 만족시킬 수 없으므로, 더 이상 시행을 할 수 없다.
• 1번 A와 4번 B를 지우고, 이어 2번 B와 3번 C를 지운다. 이 경우 시행의 횟수는 2번이고 남은 문자열은 A이다. 문자열에 남은 문자가 하나이므로, 더 이상 시행을 할 수 없다.

이외에도 시행을 할 수 있는 여러 경우의 수가 있다.

시행을 할 수 있는 최대 횟수를 구해라.

입력

첫 번째 줄에 문자열 S가 주어진다.

출력

첫 번째 줄에 답을 출력한다.

풀이

A 보다 큰 인덱스로 나오는 B를 지울 수 있고, B 보다 큰 인덱스로 나오는 C를 지울 수 있다. B는 A를 지우는데도 필요하고 C를 지우는데도 필요하다.즉 단어를 아무리 많이 지워봤자 B의 개수보다 많이 지울 수는 없다. C의 인덱스는 B의 인덱스보다 커야하니, 입력 받은 문자열을 순회하며, A,B,C 각각 큐에다가 인덱스를 삽입한 후에, 먼저 C를 지우고, 가능한 C를 다 지우고 난 뒤, B가 남았으면, 가능한 A를 지워가는 방식으로 문제를 해결할 수 있다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));

    String S;
    Queue<Integer> As;
    Queue<Integer> Bs;
    Queue<Integer> Cs;
    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        S = BR.readLine();
        As = new ArrayDeque<>();
        Bs = new ArrayDeque<>();
        Cs = new ArrayDeque<>();

        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == 'A') {
                As.add(i);
            } else if (S.charAt(i) == 'B') {
                Bs.add(i);
            } else {
                Cs.add(i);
            }
        }
    }

    void solution() {
        long answer = 0;
        while (!Bs.isEmpty()) {
            if (!Cs.isEmpty()) {
                if (Cs.peek() > Bs.peek()) {
                    Cs.remove();
                    Bs.remove();
                    answer += 1;
                } else if (!As.isEmpty()) {
                    if (Bs.peek() > As.peek()) {
                        Bs.remove();
                        As.remove();
                        answer += 1;
                    } else {
                        Bs.remove();
                    }
                }
            } else if (!As.isEmpty()) {
                if (Bs.peek() > As.peek()) {
                    Bs.remove();
                    As.remove();
                    answer += 1;
                } else {
                    Bs.remove();
                }
            } else {
                break;
            }

        }
        System.out.println(answer);
    }


}

문제 링크

분류

자료 구조, 그리디 알고리즘, 큐

문제 설명

불면의 밤을 지새워 본 사람이라면 잠 못 드는 그 시간이 얼마나 괴로운지 알고 있다. 잠을 자지 못하는 것은 다음날 피로를 야기하고 삶에 전반적으로 악영향을 미친다. 이러한 이유 때문에 숙면을 신의 축복이라고 부르기도 한다.

하지만 바쁜 현대인들에게 숙면을 취한다는 것은 마냥 쉬운 일이 아니다. 이런 상황을 안타깝게 여긴 인하대학교의 잠마니 박사는 숙면을 취할 수 있는 몇 가지 조건을 제시했다. 아래는 잠마니 박사가 제시한 숙면의 조건 중 일부를 보여준다.

1. 침대 주변을 어둡게 한다.
2. 자려고 하는 시간보다 일어나는 시간을 조정하려 한다.
..... 이하 생략 .....

극심한 불면증에 시달려 심신이 피폐해진 준형이는 잠마니 박사가 제시한 숙면의 조건을 지켜 잃어버린 정상적인 삶과 건강을 되찾을 수 있게 되었다. 여행을 갈 수 있을 만큼 건강해진 준형이는 기념으로 특별한 여행을 하고 싶었고 인터넷을 통해 특별한 숙소를 예약했다. 하지만 숙소에 도착하고 경악을 금치 못했는데, 그곳에는 정말로 특별한 전구들이 있었기 때문이다.

특별한 전구들은 N개가 일렬로 놓아져 있었고 각각의 전구들은 꺼져있거나 켜져 있었다. 모든 전구를 다 끄고 싶었지만 정말로 특별한 전구들이기 때문에 각각의 전구를 개별적으로 끄거나 켤 수 있는 스위치는 없고 정확하게 연속된 K개의 전구의 상태를 반전시킬 수 있는 버튼만이 있었다. (상태를 반전시킨다는 것은 꺼져있는 전구는 켜지고 켜져있는 전구는 꺼지는 것을 의미한다.)

최대한 빨리 잠이 들고 싶었던 준형이는 최소한의 버튼 조작으로 모든 전구를 다 끄고 싶었지만 최소한은 고사하고 모든 전구를 끄는 것조차 번번이 실패를 하였다. 이대로라면 숙면의 첫 번째 조건을 만족하지 못해 다시 불면증에 빠질 것은 자명한일!! 준형이를 도와 최소한의 버튼 조작으로 모든 전구를 끌 수 있는 프로그램을 작성하자.

아래는 N = 6이고 K = 3일 때 세 번의 버튼 조작으로 모든 전구를 끄는 과정을 보여준다. 세 번의 버튼 조작은 최소한의 조작 횟수이며 이보다 더 적게 조작을 해서 전구를 모두 끄는 방법은 존재하지 않는다.

[그림 1] 세 번의 버튼조작으로 전구를 끄는 과정

입력

입력의 첫 줄에는 특별한 전구의 개수 N(1 ≤ N ≤ 100,000)과 한 번의 버튼 조작으로 상태를 반전시킬 수 있는 전구의 개수 K(1 ≤ K ≤ N)가 주어진다.

다음 줄에는 N개의 S_i가 공백을 기준으로 주어진다. S_i는 i(1 ≤ i ≤ N)번째 전구의 상태를 나타내며 1은 전구가 켜져 있는 것을, 0은 전구가 꺼져있는 것을 의미한다.

출력

모든 전구를 끌 수 있는 최소한의 버튼의 조작 횟수를 출력한다. 한 번의 조작은 정확히 연속된 K개 전구의 상태를 반전시킬 수 있음에 유의한다. 만약 어떠한 조작으로도 모든 전구를 끄는 것이 불가능하다면 “Insomnia”(따옴표는 제외)를 출력한다.

풀이

처음 풀이를 하였을 때는 시간초과가 발생하였다. 그 원인은 i ~ i+k-1번째 전구들을 직접 반전 시켜줬었는데, 그러면 시간 복잡도가 O(NK - K^2)로 제한 시간에 문제를 해결할 수 없게된다. 전구들을 직접 하나하 켜주지 않는 방법에 대해서 떠올리는데 시간이 좀 걸렸었다.

모든 전구를 궁극적으로 0의 상태로 만들어야한다. 입력 받은 전구를 0번 인덱스부터 순회하며, queue에서 자신의 인덱스보다 작은 수들은 pop을 해준다. 그리고 큐에 남아있는 수들의 개수가 짝수이면, 해당 전구는 초기에 입력받은 상태 그대로임을 의미하고, 홀수이면, 반전된 상태 임을 의미한다.

현재 전구의 상태가 1이면, queue에 i + k - 1를 추가한다. 만약 i + k - 1이 인덱스 범위를 초과하면, 해당 숫자는 뒤집을 수 없는 상태임으로 Insomnia를 출력하는 것으로 문제를 해결할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    int N;
    int K;
    int[] lightBulbs;

    Queue<Integer> queue;

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        int[] inputArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = inputArray[0];
        K = inputArray[1];
        queue = new ArrayDeque<>();
        lightBulbs = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    void solution() {
        long answer = 0;
        boolean done = true;
        for (int i = 0; i < N; i++) {
            while (queue.size() > 0 && queue.peek() < i) {
                queue.remove();
            }

            if (queue.size() % 2 == 0) {
                if (lightBulbs[i] == 1) {
                    if (i + K - 1 < N) {
                        answer += 1;
                        queue.add(i + K - 1);
                    } else {
                        done = false;
                        break;
                    }
                }
            } else {
                if (lightBulbs[i] == 0) {
                    if (i + K - 1 < N) {
                        answer += 1;
                        queue.add(i + K - 1);
                    } else {
                        done = false;
                        break;
                    }
                }
            }

        }
        if (done) {
            System.out.println(answer);
        } else {
            System.out.println("Insomnia");
        }
    }


}

문제 링크

분류

자료 구조, 큐, 슬라이딩 윈도우

문제 설명

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

• 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
• ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
• 상근: 근데?
• ??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
• 상근: 아? 근데 K는 어떻게 구해?
• ??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
• 상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

출력

첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.

풀이

이름의 길이가 2 ~ 20 이기에, 이름의 길이별로 queue를 생성해서, 해당 큐에 이름의 인덱스를 저장한 뒤에, 큐에서 integer들을 빼내면서 빼낸 인덱스들을 다른 queue에 삽입하고, 큐의 길이를 더해주면 정답을 구할 수 있다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));

    int N;
    int K;

    HashMap<Integer, Queue<Integer>> wordLengthTable;


    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        int[] inputArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = inputArray[0];
        K = inputArray[1];
        wordLengthTable = new HashMap<>();
        for (int i = 0; i < 21; i++) {
            wordLengthTable.put(i, new ArrayDeque<>());
        }
        for (int i = 0; i < N; i++) {
            String inputName = BR.readLine();
            Queue<Integer> indexes= wordLengthTable.get(inputName.length());
            indexes.add(i);

        }
    }

    void solution() throws Exception {

        long answer = 0;
        for (int i = 2; i < 21; i++) {
            Queue<Integer> indexes = wordLengthTable.get(i);
            Queue<Integer> temp = new ArrayDeque<>();
            while (indexes.size() > 0) {
                Integer removed = indexes.remove();
                while (temp.size() > 0 && removed - temp.peek() > K) {

                    temp.remove();

                }
                answer += temp.size();
                temp.add(removed);
            }
        }
        System.out.println(answer);
    }


}