greentea31's Note

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18_yw6I9MCFAZN 

풀이 과정

N의 배수 번호인 양을 세면서 모든 숫자를 다 볼려면 양을 몇번 봐야 하는지 구하는 문제이다.

문제 그대로 모든 숫자를 다 볼 때 까지 계속 양을 센 횟수에 N을 더해주면 된다. 숫자를 모두 봤는지 판별할 때 어떤 숫자가 나왔는지를 저장하는 사이즈 10의 배열을 선언할 수도 있겠지만 비트마스킹을 사용해서 좀 더 빠르게 판단할 수 있다.

소스 코드

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

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

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine()); // 문제의 입력 N
            int visited = 0; // 현재까지 본 숫자를 bit로 표현한 수, 2-4-5를 봤다면 0000110100 (2)
            int target = (1 << 10) - 1; // 1111111111 (2) -> visited == target이면 모든 숫자 관찰
            int answer = 0; // 양을 몇 번 세었는지 저장한다

            while (visited != target) { // 모든 숫자를 볼 때 까지 반복한다
                answer += N; // 양을 N번 더 센다
                char[] ch = String.valueOf(answer).toCharArray(); // 숫자를 문자열로 변환 후 문자 배열로 저장한다
                for (char c : ch) {
                    int num = c - '0'; // 문자 배열의 각 문자를 숫자 값으로 받는다
                    visited = visited | (1 << num); // 현재까지 본 숫자를 비트마스킹으로 표시해준다
                }
            }
            System.out.printf("#%d %d\n", tc, answer);
        } // end of testcase
    } // end of main
} // end of class

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=2 

풀이 과정

NxN 차원 배열에 시계방향으로 바깥쪽부터 안쪽까지 숫자를 1씩 늘려가면서 채우는 문제이다.

배열에 채워야 할 수가 NxN으로 정해져 있으므로 이미 채워진 블록, 배열의 끝을 만나면 방향을 진행 방향의 오른쪽으로 바꿔가며 배열에 수를 N^2번 채우면 된다.

처음 풀 때 while문을 이용해서 좀 지저분하게 짰는데 그 코드도 맨 아래에 남겨놓았다.

소스 코드

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        // 동 남 서 북
        int[] dy = {0, 1, 0, -1};
        int[] dx = {1, 0, -1, 0};

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            int[][] board = new int[N][N];
            int y = 0; int x = 0;
            int num = 1;
            int direction = 0;

            for (int i = 0; i < N*N; i++) {
                board[y][x] = num++;
                int ny = y + dy[direction];
                int nx = x + dx[direction];

                if (ny < 0 || ny > N-1 || nx < 0 || nx > N-1 || board[ny][nx] != 0) {
                    direction++;
                    if (direction == 4) {
                        direction = 0;
                    }
                }

                y += dy[direction];
                x += dx[direction];
            }

            System.out.printf("#%d\n", tc);

            for (int i = 0; i < N; i++) {
                for (int j : board[i]) {
                    System.out.print(j+" ");
                }
                System.out.println();
            }
        }
    }
}

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

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

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            int[][] board = new int[N][N];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    board[i][j] = 0;
                }
            }

            int direction = 0;
            int r = 0; int c = 0;
            int num = 1;
            while (board[r][c] == 0) {
                board[r][c] = num++;
                if (direction == 0 ) {
                    if (c+1 < N && board[r][c+1] == 0) {
                        c++;
                    } else {
                        if (r+1 < N && board[r+1][c] == 0) {
                            direction++;
                        } else {
                            break;
                        }
                    }
                }

                if (direction == 1) {
                    if (r+1 < N && board[r+1][c] == 0) {
                        r++;
                    } else {
                        if (c-1 >= 0 && board[r][c-1] == 0) {
                            direction++;
                        } else {
                            break;
                        }
                    }
                }

                if (direction == 2) {
                    if (c-1 >= 0 && board[r][c-1] == 0) {
                        c--;
                    } else {
                        if (r-1 >= 0 && board[r-1][c] == 0) {
                            direction++;
                        } else {
                            break;
                        }
                    }
                }

                if (direction == 3) {
                    if (r-1 >= 0 && board[r-1][c] == 0) {
                        r--;
                    } else {
                        if (c+1 < N && board[r][c+1] == 0) {
                            direction = 0;
                            c++;
                        } else {
                            break;
                        }
                    }
                }
            }

            System.out.printf("#%d\n", tc);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
}

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

풀이 과정

회의의 시작 시간과 끝나는 시간이 주어질 때, 회의가 겹치지 않으면서 가장 많은 회의를 진행하는 경우를 구하는 문제이다.

가능한 많은 회의를 진행하려면 회의의 종료시간이 빠른 순서대로 회의를 진행하면 된다. 회의의 종료시간이 같은 두 개의 회의가 존재할 때는 어떻게 처리해야 할까?

(9, 10), (10, 10) 두 입력이 들어왔다 가정하자. 여기서 (10, 10)을 먼저 처리하면 (9, 10)이 그리디로 처리되지 않는다. 따라서 종료시간이 빠른 순서대로 처리하되, 종료시간이 같은 회의는 시작시간이 더 빠른 회의가 우선으로 배정되도록 처리해야 한다.

소스 코드

import sys

N = int(sys.stdin.readline())
meeting = []

for i in range(N):
    start, end = map(int, sys.stdin.readline().split())
    meeting.append([start, end])

meeting.sort(key=lambda x: (x[1], x[0]))

answer = 1
end = meeting[0][1]

for i in range(1, N):
    if meeting[i][0] >= end:
        answer += 1
        end = meeting[i][1]

print(answer)

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

풀이 과정

A를 B번 곱한 수를 C로 나눈 나머지를 구하는 문제이다.

A, B, C 모두 약 21억까지 수가 들어올 수 있는데 시간제한이 0.5초다. 반복문으로 A를 21억번 곱하는 방법으로 풀면 O(N)으로 시간 초과가 발생하게 된다.

2의 32승은 2의 16승 * 2의 16승과 같다. 이러한 지수 법칙을 이용하면 계산의 시간복잡도를 O(logN)으로 바꾸어 문제를 해결할 수 있다.

A*B % C = ((A%C) * (B%C)) % C 임을 이용해 오버플로우가 나지 않도록 계산을 진행하여야 한다.

소스 코드

import sys


def div_and_con(a, b, c):
    if b == 1:
        return a % c

    temp = div_and_con(a, b//2, c)

    if b % 2 == 0:
        return ((temp%c) * (temp%c)) % c
    else:
        return ((temp%c) * (temp%c) * (a%c)) % c


A, B, C = map(int, sys.stdin.readline().split())
print(div_and_con(A, B, C))

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

풀이 과정

진실을 아는 사람, 진실을 들었던 사람들이 참가한 파티에서는 거짓말을 할 수 없고, 진실을 아는 사람과 파티에 참석하는 사람들의 번호가 주어질 때 거짓말을 할 수 있는 최대 횟수를 구하는 문제이다.

문제를 읽고 생각할 수 있는 것은

1. 파티에 진실을 아는 사람이 참석했으면 무조건 진실을 말해야 한다.

2. 진실을 아는 사람이 참석한 파티의 모든 참가자들은 진실을 듣게 되었으므로, 원래 진실을 몰랐던 사람도 아는 사람으로 바뀌게 된다.

라고 판단하고 코드를 짠 다음에 예시 입력을 넣어보면 예시 출력과 다른 답이 나오게 된다. 무엇이 문제일까?

1번이라는 사람이 진실을 알고, 첫 번째 파티에 3번이 참가, 두 번째 파티에 1번과 3번이 참가했다고 가정해보자. 첫 번째 파티는 진실을 모르는 3번이 참가했으니 거짓말 횟수 1 증가... 두 번째 파티는 진실을 아는 1번이 참가했으니 3번을 진실을 아는 사람으로 설정하고 거짓말 횟수 보류... 이러면 오답을 출력하게 된다. 최종적으로는 3번이 진실을 알게 되므로 첫 번째 파티에서 거짓말을 하면 3번에게 거짓이라는 것을 2번째 파티에서 들키게 된다.

파티 참가자들을 살펴보며 union-find를 사용해서 진실을 아는 사람, 진실을 들은 사람을 전부 다 연결시키고, 다시 한번 파티 참가자들을 살펴보면서 진실을 모르는 사람들만 있는 파티에서 거짓말 횟수를 증가시키면 문제를 해결할 수 있다.

소스 코드

import sys

parent = [i for i in range(51)]
truth_check = [False for _ in range(51)]


def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]


def uni(a, b):
    aRoot = find(a)
    bRoot = find(b)
    if aRoot == bRoot:
        return
    if truth_check[aRoot]:
        parent[bRoot] = aRoot
        return

    parent[aRoot] = bRoot


N, M = map(int, sys.stdin.readline().split())
truth_people = list(map(int, sys.stdin.readline().split()))
people_list = []

if truth_people[0] != 0:
    for i in range(1, truth_people[0] + 1):
        truth_check[truth_people[i]] = True

for _ in range(M):
    people = list(map(int, sys.stdin.readline().split()))
    people_list.append(people[1:])
    prev = people[1]

    for i in range(1, people[0] + 1):
        uni(prev, people[i])
        prev = people[i]

answer = 0

for peo in people_list:
    truth_flag = False
    for pe in peo:
        if truth_check[find(pe)]:
            truth_flag = True
    if not truth_flag:
        answer += 1

print(answer)

https://leetcode.com/problems/single-number/

풀이 과정

배열에서 딱 한번만 나오는 원소를 출력하는 문제이다.

비트 연산중에 XOR 연산은 비트가 같으면 0, 다르면 1을 출력한다. 0을 저장하고 있는 변수에 배열의 모든 원소들을 XOR 연산을 하면 2번씩 나온 원소들은 bit 연산중 0으로 바뀌고 1번 나온 원소의 bit만 남게될 것이다.

소스 코드

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0
        for num in nums:
            answer ^= num
        return answer

https://leetcode.com/problems/search-a-2d-matrix-ii/

풀이 과정

행, 열 단위로 정렬되어 있는 2차원 배열에서 target 값이 존재하는지 여부를 판단하는 문제이다.

2차원 배열의 값들과 target의 값을 일일이 비교해보는 방법으로도 찾을수 있지만, 행 열 단위로 정렬되어 있다는 조건이 주어졌으므로 더 빠르게 문제를 해결할 수 있다.

시작 위치를 2차원 배열의 오른쪽 위 끝 혹은 왼쪽 아래 끝으로 잡은 뒤 배열 요소의 값과 target 값과의 대소 비교후 index를 바꾸면서 찾아가는 것이다. 이러면 모든 배열의 요소를 점검 할 필요가 없다.

소스 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        
        m = len(matrix)
        n = len(matrix[0])
        
        a = 0
        b = n - 1
        
        while 0 <= a < m and 0 <= b < n:
            if matrix[a][b] == target:
                return True
            elif matrix[a][b] < target:
                a += 1
            else:
                b -= 1
        
        return False

https://leetcode.com/problems/intersection-of-two-arrays/

풀이 과정

두 배열의 교집합을 구하는 문제이다.

리스트를 set 자료형으로 바꾼다음에 s1.intersection(s2) 혹은 s1 & s2로 파이썬 내장 함수를 이용하는 방법이 가장 편리한 풀이방법이다.

O(N^2) 방법으로 브루트 포스로도 풀 수는 있다.

자료형 내장 함수도, 브루트 포스도 싫다! 하면 두 리스트를 모두 정렬후 투 포인터로 문제를 해결하면 된다.

포인터 2개 설정하고 맨 앞에 포인터를 설정한 뒤 포인터가 가리키고 있는 값끼리 비교하고, 같으면 정답에 추가, 한 쪽이 작으면 작은쪽의 포인터를 한 칸 전진하는 방법으로 문제를 해결할 수 있다.

소스 코드

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer = set()
        nums1.sort()
        nums2.sort()
        len1 = len(nums1)
        len2 = len(nums2)
        index1 = 0
        index2 = 0
        
        while index1 < len1 and index2 < len2:
            if nums1[index1] < nums2[index2]:
                index1 += 1
            elif nums1[index1] > nums2[index2]:
                index2 += 1
            else:
                answer.add(nums1[index1])
                index1 += 1
                index2 += 1
        
        return answer

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = set(nums1)
        nums2 = set(nums2)
        return nums1 & nums2

https://leetcode.com/problems/search-in-rotated-sorted-array/

풀이 과정

오름차순으로 정렬된 배열이 회전되어져서 주어질 때, target값의 인덱스를 O(logN)으로 구하는 문제이다. 없으면 -1을 리턴하면 된다.

O(logN)으로 구해야 하므로 배열을 전부 살펴보며 target값이 있는지 확인하는 O(N) 방법은 사용할 수 없다. 몇번 회전되어 있는지를 구하고 다시 회전시키고 이진 탐색을 수행하면 좋을 것 같은데 몇번 회전되어 있는지를 구하는 연산도 O(N)이다... 이런....

0 1 2 3 4 5 6 이라는 배열을 생각해보자. 이 배열을 회전시키면

        mid

0 1 2 3 4 5 6

1 2 3 4 5 6 0

2 3 4 5 6 0 1

3 4 5 6 0 1 2

4 5 6 0 1 2 3

5 6 0 1 2 3 4

6 0 1 2 3 4 5

이다. 처음 값을 left로 두고 마지막 값을 right로 두고 while left <= right으로 이진 탐색을 수행한다고 할 때 다음과 같은 생각을 할 수 있다.

nums[left] < nums[mid]가 성립한다면? 일단 left ~ mid까지는 정렬이 되어있다는 소리고 (중간에 대소관계의 역전이 발생하지 않음) 그 안에서는 이진 탐색을 수행할 수 있을 것이다.

nums[left] < nums[mid]가 성립하지 않는다면? nums[mid] < nums[right]는 무조건 성립하고 그 안에서는 이진 탐색을 수행할 수 있다. 0 1 2 3 4 5 6 을 회전시킨 배열들을 보면서 대입해보면 이해가 편리하다.

nums[left] < nums[mid]가 성립했다면? nums[left] <= target <= nums[mid]인지 체크해서 왼쪽 배열에 target값이 존재하는지 판단할 수 있다. 없으면 오른쪽 배열에 있을 가능성이 있으므로 오른쪽을 찾아봐야 한다.

이와 유사한 논리로 왼쪽 정렬되어 있는데 왼쪽에 있는 경우, 없는 경우 그리고 오른쪽이 정렬되어 있는데 오른쪽에 있는 경우, 없는 경우... 이렇게 모두 따져보면 이진 탐색이 가능함을 알 수 있다.

소스 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        mid = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

https://leetcode.com/problems/binary-search/

풀이 과정

이진 탐색으로 target이 배열에 존재하면 target의 index를, 아니면 -1을 출력하는 문제이다.

배열이 정렬된 상태로 들어오므로 이진 탐색으로 탐색 범위를 반씩 줄여나가면서 target을 빠르게 찾을 수 있다.

소스 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        mid = (left + right) // 2
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1 
        
        return -1