Problem

• 문제 링크

Z 모양으로 순회하는 순서를 알아내는 문제입니다.

Solution

처음 보는 순간 재귀가 떠오릅니다.

사각형을 4개의 사분면으로 나누어서 순서대로 들어가고 또 그 사각형 내에서 4등분 하여 접근합니다.

그렇게 사각형을 더이상 나누지 못하는 1이 될 때까지 재귀를 들어간 후에 카운트 해주면 됩니다.

(x, y, size);

(0, 0, 8);
      (0, 0, 4);
          (0, 0, 2);
              (0, 0, 1);
              (1, 0, 1);
              (0, 1, 1);
              (1, 1, 1);
          (2, 0, 2);
          (0, 2, 2);
          (2, 2, 2);
      (4, 0, 4);
          (4, 0, 2);
          (6, 0, 2);
          (4, 2, 2);
          (6, 2, 2);
      (0, 4, 4);
      (4, 4, 4);

간단하게 표현한건데 재귀에 들어가는 모습을 시각적으로 표현한 겁니다.

전부 다 나타낸 것은 아니고 일부만 나타낸 거지만 size가 1이 될 때까지 계속해서 사각형을 나누어 접근합니다.

규칙이 머리속에 바로 떠오르지 않는다면 이렇게 간단하게 적어보시면 금방 찾을 수 있습니다.

하지만 N 이 최대 15라서 재귀를 사용하며 시간 초과가 발생합니다.

시간을 줄이기 위해서 일일히 좌표에 접근하지 않고 한번에 가는 방법을 생각해보았습니다.

규칙이 보이시나요?

8 * 8 배열 일 때 각 사분면의 첫번째 값은 0, 16, 32, 48 입니다.

4 * 4 배열 일 때 각 사분면의 첫번째 값은 0, 4, 8, 12 입니다.

2 * 2 배열 일 때 각 사분면의 첫번째 값은 0, 1, 2, 3 입니다.

n * n 배열 일 때 각 사분면의 첫번째 값은

(n/2) * (n/2) * 0
(n/2) * (n/2) * 1
(n/2) * (n/2) * 2
(n/2) * (n/2) * 3

이렇게 됩니다.

count 에 대한 식을 이렇게 얻었습니다.

Exmaple

n 이 8 인 경우 (2, 3) 좌표를 찾아가보겠습니다.

Step 1. n = 8

먼저 (2, 3) 좌표는 (n / 2, n / 2) 인 (4, 4) 좌표보다 x, y 좌표가 둘다 작습니다.

그래서 왼쪽 위 사각형으로 이동하고 n 은 n /= 2 로 절반으로 줄어듭니다.

Step 2. n =4

그리고 다시 (2, 3) 좌표는 (n / 2, n / 2) 인 (2, 2) 좌표보다 x, y 좌표가 둘다 크거나 같습니다.

그래서 오른쪽 아래 사각형으로 이동하고 n 은 n /= 2 로 절반으로 줄어듭니다.

Step 3. n = 2

오른쪽 아래 사각형은 (2, 2) 좌표가 첫번째 값입니다.

그러므로 (2 + n / 2, 2 + n / 2) 인 (3, 3) 좌표와 값을 비교합니다.

(2, 3) 좌표는 (3, 3) 좌표보다 x 좌표는 작지만 y 좌표는 크거나 같기 때문에 오른쪽 위 사각형으로 이동합니다.

그리고 n 을 절반으로 하면 1 이 되기 때문에 더 이상 나눌 수 없고 해당 좌표의 카운트를 출력합니다.

말로 설명하기 어려운 부분이 있는데 그림을 보며 코드를 따라가시면 금방 이해할 수 있습니다.

Java Code

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

class Main {
    static int stoi(String s) { return Integer.parseInt(s);}

    static int N;
    static int r;
    static int c;
    static int count = 0;

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

        int N = stoi(st.nextToken());
        int r = stoi(st.nextToken());
        int c = stoi(st.nextToken());

        int n = getSize(N);
        int count = 0;
        int x = 0;
        int y = 0;

        /**
         * 사각형 절반으로 나눠서 각 사분면으로 계산
         * n 이 1 이 된다는 것은 x, y 좌표가 r, c랑 같아진다는 것
         */
        while (n > 0) {
            n /= 2;

            // 2사분면 (왼 위)
            if (r < x+n && c < y+n) {
                count += n * n * 0;
            }
            // 1사분면 (오른 위)
            else if (r < x+n) {
                count += n * n * 1;
                y += n;
            }
            // 3사분면 (왼 아래)
            else if (c < y+n) {
                count += n * n * 2;
                x += n;
            }
            // 4사분면 (오른 아래)
            else {
                count += n * n * 3;
                x += n;
                y += n;
            }

            if(n == 1) {
                System.out.println(count);
                break;
            }
        }
    }

    static int getSize(int n) {
        int result = 1;
        for(int i=0; i<n; i++) {
            result *= 2;
        }
        return result;
    }
}

문제 링크 : https://www.acmicpc.net/problem/2667

단지의 개수와 각 단지별 집의 개수를 출력하는 문제입니다.

DFS로 각 단지의 개수를 세주면 됩니다.

한번 방문한 집은 또 방문할 일이 없기 때문에 일반적으로 사용하는 visited 배열을 쓰지 않고

대신 arr 값을 1에서 0으로 바꿔주면서 DFS를 반복했습니다.

DFS를 한번 돌 때마다 단지 하나가 전부 0 이 됩니다.

그러므로 main에서 DFS를 한번 접근 할 때마다 카운트하여 단지 수를 저장하면 됩니다.

단지별 집의 개수는 오름차순으로 출력하기 때문에 바로바로 출력하지 말고 따로 저장해야합니다.

ArrayList에 담은 후에 Collections.sort 를 사용하여 정렬을 해도 되지만

저는 우선순위큐를 사용하여 오름차순으로 출력하였습니다.

문제 링크 : https://www.acmicpc.net/problem/1302

가장 많이 나온 책을 출력하는 문제입니다.

책을 Key로, 횟수를 Value로 저장하는 HashMap<String, Integer> 를 사용하여 해결할 수 있습니다.

한가지 주의사항은 value가 같을 때는 패스하는게 아니라 책을 비교하여 사전순으로 앞서는 것으로 갱신해야 한다는 점입니다.

HashMap 반복문은 개인적으로 제가 가장 편하게 생각하는 것으로 구현하였습니다.

Iterator나 Element를 사용해도 상관 없습니다.

문제 링크 : https://www.acmicpc.net/problem/1057

김지민, 임한수가 라운드 몇에서 대결하게 될 지 맞추는 문제입니다.

처음에 단순하게 Queue로 구현을 하였습니다.

1. 모든 토너먼트 멤버를 Queue에 넣은 뒤 두 개씩 poll 한다.

2. 두 값을 비교하여 김지민, 임한수라면 라운드를 출력하고 종료

2-1. 두 값 중 하나만 김지민 혹은 임한수라면 무조건 승리자

2-2. 둘 다 해당되지 않는다면 무조건 앞 번호가 승리자

이렇게 단순하게 구현하여 Queue에 계속 넣었다 빼며 구현하였습니다.

하지만 정답을 맞춘 후에 다른 정답자들 코드를 보니 굉장히 간단하게 구현하였습니다.

각 멤버가 같은 라운드에서 만난다는 것은 부모 노드가 같다고 볼 수 있습니다.

그래서 두 멤버의 부모 노드만을 계속 따라가며 같은 값이 될 때의 라운드를 출력하면 됩니다.

자식 노드가 최대 두 개로 고정되어 있기 때문에 부모 노드의 인덱스는

(now + 1) / 2

now/2 + now%2

이렇게 두 가지 방법으로 구할 수 있습니다.

코드는 처음에 구현했던 Queue를 이용한 방법과 두번째로 구현한 방법 모두 올리겠습니다.

문제 링크 : https://www.acmicpc.net/problem/2026

서로 좋아하는 친구들의 목록이 나열될 때 소풍에 보낼 수 있는 K 명의 학생을 출력하는 문제입니다.

예전에 굉장히 많이 틀려서 포기했던 문제인데 다시 푸는데도 굉장히 많은 시도를 하고 맞췄습니다..

제 기준에서 크게 두 가지의 함정이 있었는데 아래에서 설명드리겠습니다.

1. 첫번째로 주의할 점은 싸이클을 찾는 문제가 아니라는 사실입니다.

따라서 일반적인 DFS의 싸이클 검사나 유니온 파인드로는 해결할 수가 없습니다.

결국 백트래킹으로 완전 탐색을 하는데 단순하게 인접 행렬로 그래프를 구현해서 돌리면 O(n^3)으로 시간초과가 됩니다.

2. 그래서 탐색할 필요가 없는 노드를 생략하는게 두번째 핵심입니다.

탐색할 필요가 없는지는 어떻게 아는가?

소풍은 무조건 K 명이 가게 됩니다.

만약 K=4 일 때 1번 노드의 친구가 2번, 3번 밖에 없다면 그들이 모두 친구 관계여도 3이 됩니다.

결국 1번 노드는 탐색할 필요가 없어서 생략할 수 있게 됩니다.

예를 들어 K=62 일 때, 모든 노드가 60명의 친구만 가지고 있는 테스트 케이스가 주어집니다.

모든 노드들은 본인과 친구 60명을 포함해서 최대로 나올 수 있는 친구 관계가 61명이라 소풍에 가는 인원이 나올 수 없습니다.

하지만 불필요하게 모든 노드들을 탐색하고 있어야 하죠.

그래서 저는 indegree 배열을 만들어서 자신과 연결된 노드의 갯수가 몇 개인지 저장했습니다.

1번 노드의 친구가 2, 3 이면 indegree[1] = 2가 됩니다.

만약 indegree가 K-1보다 작은 노드들은 탐색할 필요 없이 생략하게 됩니다.

이렇게 두가지 예외처리를 해주면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/10809

간단한 문제지만 자바에서는 알파벳 순회를 이렇게도 할 수 있단걸 보여주기 위해 썼습니다.

문제 링크 : https://www.acmicpc.net/problem/8958

O가 연속될수록 점수가 커지는 문제입니다.

받은 String의 길이만큼 돌며 O 면 값을 더해주고 score을 1 증가시키고

X 면 계속 score을 1로 유지시킵니다.

테스트케이스가 얼마나 들어올 지 모르기 때문에 출력 형식으로 System.out.println 대신에 StringBuilder를 사용하였습니다.

문제 링크 : https://www.acmicpc.net/problem/2839

배달 가능한 봉투 개수가 최소가 되는 값을 구하는 문제입니다.

간단하게 이전까지의 값을 저장하는 것으로 문제를 해결 할 수 있습니다.

봉투는 항상 3kg 또는 5kg 밖에 없다는 점을 이용합니다.

예를 들어 18 이라는 값이 들어오면 15kg + 3kg 또는 13kg + 5kg 라는 두 개의 경우가 있습니다.

15kg와 13kg에는 이전에 계산 해놓았기 때문에 이미 최소값이 들어가 있습니다.

그러므로 봉투 하나만 추가하면 됩니다.

이 중에서 더 작은 값을 저장하며 N까지 진행하면 됩니다.

** 딱 나누어 떨이지지 않는 값이 들어오면 -1을 출력해야 하기 때문에 아무런 값도 저장하지 않습니다.

7kg는 딱 나누어 떨어지지 않기 때문에 0이 들어있습니다.

10kg는 7kg + 3kg와 5kg + 5kg 중 더 작은 값이 들어가게 되는데 7kg가 0이라서 무조건 1이 들어가게 됩니다.

그러므로 i-3 또는 i-5 의 값이 0보다 클 때만 계산해줍니다.