그냥 코딩하는 사람의 블로그

https://programmers.co.kr/learn/courses/30/lessons/49190

풀이 과정

1. 방으로 셀수있는 경우의 수는 두가지이다.

   • 대각선끼리 교차하는 경우
   • 지나가지 않은 간선으로 이미 방문한 노드를 다시 방문하게 될 때

2. 각각의 경우에 맞추어서 대각선끼리 교차할 때와 재방문할때 방의 개수를 하나씩 늘려주면 된다.

3. 여기서 해맸던 점이.. 한방향 방문 처리만 해주어서 다른 방향으로 다시 방문할때 방의 개수가 계속 늘어나게 되는 문제가 있었다.

   • 따라서, (a,b) -> (c,d)로 진행한다면, (c,d) -> (a,b)도 방문처리 해주어야 함.

소스 코드

def movement(x, y, arrow):
    if arrow == 7:
        x += 1
        y -= 1
    if arrow == 6:
        y -= 1
    if arrow == 5:
        x -= 1
        y -= 1
    if arrow == 4:
        x -= 1
    if arrow == 3:
        x -= 1
        y += 1
    if arrow == 2:
        y += 1
    if arrow == 1:
        x += 1
        y += 1
    if arrow == 0:
        x += 1
    return x, y

def cross_check(edge, x, y, arrow):
    if arrow == 1:
        if (x, y+1, x+1, y) in edge or (x+1, y, x, y+1) in edge:
            return True
    elif arrow == 5:
        if (x, y-1, x-1, y) in edge or (x-1, y, x, y-1) in edge:
            return True
    elif arrow == 7:
        if (x, y-1, x+1, y) in edge or (x+1, y, x, y-1) in edge:
            return True
    elif arrow == 3:
        if (x-1, y, x, y+1) in edge or (x, y+1, x-1, y) in edge:
            return True

    return False


def solution(arrows):
    answer = 0
    visited = set()
    edge = set()
    x, y = 0, 0
    visited.add((x, y))
    for arrow in arrows:
        currentX, currentY = x, y
        x, y = movement(x, y, arrow)

        # 교차하는 대각선 여부 확인
        if arrow in [1, 3, 5, 7] and cross_check(edge, currentX, currentY, arrow):
            if (x, y, currentX, currentY) not in edge: 
                answer += 1

        if (x, y) in visited:
            # 반대로 돌아오는 간선 있는지 체크
            if (x, y, currentX, currentY) not in edge: 
                answer += 1
        else:
            visited.add((x, y))

        # 현재 간선정보 저장
        edge.add((currentX, currentY, x, y))
        edge.add((x, y, currentX, currentY))
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12902

풀이 과정

1. DP 테이블을 구성한다.

2. 현재 위치 i 기준으로 가능한 경우의 수

   • i-2칸을 채우는 경우의 수에서 2칸 채우는 경우의 수인 3을 곱한다.
   • i-4칸을 채우는 경우의 수에서 4칸 채우는 경우의 수인 2를 곱한다.
     • 4칸 채우는 경우의 수에서.. 가운데에 블록 하나씩 넣으면 2칸씩 늘어난다.
     • 6칸 채우는 경우의 수도 2개, 8칸 채우는 경우의 수도 2개, ..
     • 각각을 처리해 주어야 한다.

3. 테이블을 채우기 전, 계산한 결과를 1,000,000,007으로 나눈 나머지를 저장해 둔다.

4. dp[n]을 리턴해주면 된다.

소스 코드

def solution(n):
    answer = 0
    dp = [1] + [0] * (n)

    for i in range(2, n+1):
        dp[i] += (dp[i-2] * 3)
        for j in range(4, i+1, 2):
            dp[i] += (dp[i - j] * 2)

        dp[i] = dp[i] % 1000000007
    answer = dp[n]
    return answer

https://programmers.co.kr/learn/courses/30/lessons/42897

풀이 과정

• 썩 좋은 문제인거같지는 않음.. DP 테이블을 구성하면 시간초과가 나와서 찾아보니 변수로 풀이하면 시간초과가 나지 않는다고 하여 변수로 DP 풀이 함.

1. 동그랗게 배치되어 있으므로 1번에 집이 배치되던가 배치되지 않던가 두가지 경우로 나누어서 풀이해야 함.

   • 1번에 집이 배치되었다면 2번에는 반드시 배치가 되지 않은 상태로 3번부터 진행
   • 1번에 집이 배치되어있지 않다면 2번에는 배치가 될수도, 안될수도 있으니 각각에 맞춰 채운 후 진행

2. 최대 금액을 출력한다.

   • 1번에 집이 배치가 된 상태이면서 마지막 번호에 배치가 되지 않은 경우
   • 1번에 집이 배치가 되지 않은 상태이면서 마지막 번호에 배치가 되었거나 / 되지 않은 경우
   • 총 세가지 경우중 최댓값을 출력해주면 된다.

3. 아래 소스 참고

   • a -> 1번 뽑음 & 현재 번호의 집은 털지 않음
   • b -> 1번 뽑음 & 현재 번호의 집 털음
   • e -> 1번 뽑지 않음 & 현재 번호의 집 털지 않음
   • f -> 1번 뽑지 않음 & 현재 번호의 집 털음

소스 코드

def solution(money):

    # 1번을 뽑았을 때
    a, b, c, d = 0, 0, 0, 0
    a, b = money[0], money[0]

    # 1번을 뽑지 않았을 때
    e, f, g, h = 0, 0, 0, 0
    e, f = 0, money[1]

    for i in range(2, len(money)):
        c = max(a, b)
        d = max(a + money[i], b)
        g = max(e, f)
        h = max(e + money[i], f)

        a, b = c, d
        e, f = g, h


    answer = max(a, e, f)
    return answer

https://programmers.co.kr/learn/courses/30/lessons/86052

풀이 과정

• 이게 난이도 2는 아닌거 같음. 전혀 감을 못잡고있다가 힌트를 보고 풀었음..

1. 전체 경우의 수를 탐색함.

   • 각각의 격자에서 왼쪽, 아래, 오른쪽, 위 네개의 방향으로 시작해서 이미 방문한 격자를 만날때까지 탐색
   • 미리 방향 배열을 만들어 두어서 좌회전일땐 +1, 우회전일땐 -1 하도록 함.
   • 탐색할 때 격자를 몇개 이동했는지 저장해 둠.

2. 격자의 끝을 넘어갈 때, 반대쪽 방향으로 들어오는건 그냥 나머지 연산자로 구현함.

   • (-1) % n = n-1, (n+1) % n = 1 인걸 이용

3. 저장해 둔 탐색 결과를 오름차순으로 정렬하여 리턴

소스 코드

def goto(grid, visited, start):
    x, y, way = start
    direction = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    length = 0
    while True:
        if visited[x][y][way]:
            break

        visited[x][y][way] = True
        length += 1

        if grid[x][y] == 'S':
            pass
        elif grid[x][y] == 'L':
            way = (way + 1) % 4
        elif grid[x][y] == 'R':
            way = (way - 1) % 4

        x = (x + direction[way][0]) % len(grid)
        y = (y + direction[way][1]) % len(grid[0])

    return length

def solution(grid):
    answer = []
    visited = [[[False] * 4 for _ in range(len(grid[0]))] for __ in range(len(grid))]

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in range(4):
                if visited[i][j][k] == False:
                    answer.append(goto(grid, visited, [i, j, k]))

    answer.sort()
    return answer

https://programmers.co.kr/learn/courses/30/lessons/62050

풀이 과정

• 4단계 문제라 그런지 소스가 되게 길고 응용이 많다..

1. BFS로 이동 가능한 각각의 영역에 번호를 붙여준다.

   • 영역번호가 1번이라면 1번끼리는 이동 가능한 것이다.

2. 번호를 붙인 영역간에 이동 가능한 최소 거리를 저장해 둔다.

   • 노드가 영역의 수만큼 있다고 생각
   • dict[(1, 2)] = 3 이라면.. 1번 노드(영역)에서 2번 노드(영역)으로 이동하기 위해서(간선) 비용이 3이라고 보면 된다.

3. Kruskal 알고리즘으로 최소비용 신장트리를 구한 다음, 최소비용을 리턴해주면 된다.

   • 간선의 비용이 최소인것부터 순차적으로 사용한다.
   • union-find 알고리즘을 사용하여 사이클 검사

소스 코드

from collections import deque, defaultdict
import heapq

def area_bfs(area, land, start, value, height):
    queue = deque([start])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    area[start[0]][start[1]] = value
    while queue:
        cx, cy = queue.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx and nx < len(land) and 0 <= ny and ny < len(land[0]):
                if area[nx][ny] == int(10e9) and abs(land[cx][cy] - land[nx][ny]) <= height:
                    area[nx][ny] = value
                    queue.append([nx, ny])

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

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)

    if p1 != p2:
        parent[p1] = p2


def solution(land, height):
    answer = 0

    # 구간별로 번호 매김
    INT_MAX = int(10e9)
    area = [[INT_MAX] * len(land[0]) for _ in range(len(land))] 
    number = 1
    for i in range(len(area)):
        for j in range(len(area[0])):
            if area[i][j] == INT_MAX:
                area_bfs(area, land, [i, j], number, height)
                number += 1

    # 구간 그래프화
    dx = [1, 0]
    dy = [0, 1]

    distance = defaultdict(lambda: int(10e9))
    for i in range(len(area)):
        for j in range(len(area[0])):
            for k in range(2):
                nx, ny = i + dx[k], j + dy[k]
                if 0 <= nx < len(area) and 0 <= ny < len(area[0]) and area[i][j] != area[nx][ny]:
                    # 작은 지역번호가 앞으로 가도록 간선정보 구성
                    # key : (작은 지역 번호, 큰 지역 번호) = 최소 이동 거리
                    src = min(area[i][j], area[nx][ny])
                    dest = max(area[i][j], area[nx][ny])
                    distance[(src, dest)] = min(distance[(src, dest)], abs(land[nx][ny] - land[i][j]))


    parent = [i for i in range(number)]
    heap = []

    # 간선 오름차순으로 힙에 넣어줌.
    for areas, dist in distance.items():
        heapq.heappush(heap, [dist, areas])

    # 간선의 크기가 작은 순서대로 그래프에 추가
    # 사이클 형성시 패스
    while heap:
        dist, areas = heapq.heappop(heap)
        if find(parent, areas[0]) != find(parent, areas[1]):
            union(parent, areas[0], areas[1])
            answer += dist

    return answer

https://programmers.co.kr/learn/courses/30/lessons/43236?language=python3

풀이 과정

1. 이분 탐색으로 풀이를 한다. 이분 탐색의 대상은 각 지점 사이의 거리의 최솟값으로 진행한다.

   • 이 값을 mid라고 두자.

2. 만약 이전 돌과 현재 돌 사이의 거리가 mid보다 작다면 제거해야되는 돌이므로 제거 카운팅을 늘려준다.

   • 맨 마지막에 도착지점과 마지막 돌 사이의 거리도 체크해줘야 함.
   • 제거한 돌은 거리 계산에 들어가면 안되므로, 이전 돌은 prev라는 변수에 따로 저장해두고 현재 돌을 제거해야되는 경우 prev 변수를 갱신하지 않도록 함.

3. 제거한 돌의 개수가 n개 이하인 경우에는 정답을 저장해 두고 오른쪽 구간 진행(최댓값을 찾아야 하므로)

4. 제거한 돌의 개수가 n개보다 많은 경우는 왼쪽 구간 진행

• 원래 문제 읽어보면 딱 n개 제거해야되는거 같은데, n개 제거하도록 하면 틀림. n개 이하로 해야 맞음..

소스 코드

def solution(distance, rocks, n):
    answer = 0
    left = 0
    rocks.sort()
    right = int(10e8)+1

    # mid를 최솟값이라고 할 때
    while left <= right:
        mid = (left + right) // 2
        prev = 0
        eliminated_count = 0
        for i in range(len(rocks)):
            if rocks[i] - prev < mid:
                eliminated_count += 1
            else:
                prev = rocks[i]

        if distance - prev < mid: # 도착 거리
            eliminated_count += 1

        if eliminated_count <= n:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

풀이 과정

• 퇴실 순서는 리스트에서 큐 형태로 바꾸어 줌.
  => 구현의 편의성을 위해 큐로 바꾸어주는게 좋음!

• 구현의 편의를 위해 처음 인원수 저장할 때는 인원수 + 1만큼의 배열을 만들어 두고, 리턴할 때는 첫번째 인덱스부터 리턴

• 입실한 사람 순서대로 반복문을 진행한다.

  • 입실한 사람은 set에다가 넣어준다. (비교의 용이, 속도 면에서 좋을 것 같아서)
  • 입실 처리가 되었으면 퇴실 인원이 있는지도 확인한다.
  • 퇴실 인원의 확인은 큐의 맨 앞을 확인하면 되며, 퇴실 인원이라면 큐에서 빼준다.
    • 빼주면서 인원 처리를 해주어야 하는데, 빼낸 사람을 제외한 기존 입실 처리된 인원들은 빼낸 사람을 만났으므로, 기존 입실 처리된 인원들이 만난 사람 수에는 1을 더해준다
  • 또한, 빼낸 사람의 인원에는 빼낸 사람을 제외한 기존 입실 처리된 인원들의 수를 더해준다.

소스 코드

def solution(enter, leave):
    answer = [0] * (len(enter) + 1)
    leave = deque(leave)
    visited = set()

    for e_person in enter:
        visited.add(e_person)
        while leave:
            if leave[0] in visited:
                answer[leave[0]] += (len(visited) - 1)
                visited.remove(leave.popleft())
                for left_person in visited:
                    answer[left_person] += 1
            else:
                break

    return answer[1:]

출처

• https://programmers.co.kr/learn/courses/30/lessons/86048

풀이 과정

1. 파이썬으로는 풀이할 수가 없어서 Java로 풀이함.
2. 전체적인 흐름은 BFS로 구성
   • 전체 배열을 2중 for문으로 검사하면서, 0이 아닌 수가 발견되면 그 자리에서 bfs 진행
   • bfs의 경우, 현재 자리의 값을 0으로 만들고 현재 자리의 값과 같은 값이 인접 위치에 있다면, 해당 위치를 0으로 만들고 큐에 넣는 방식으로 진행.
   • 0으로 만든 배열 요소의 수를 따로 리턴해 준다.
3. 전체 BFS 진행 횟수가 영역의 개수, BFS 진행하면서 0으로 만든 배열 요소의 수의 최댓값이 가장 큰 영역의 넓이이다.

• 문제 오류인것 같긴 한데.. 입력받은 picture을 직접 수정하면 틀렸다고 나오고, picture를 따로 복사한 다음 수정해야 맞았다고 나온다..

소스 코드

import java.util.Queue;
import java.util.LinkedList;

class Position {
    int x;
    int y;

    public Position(int a, int b) {
        this.x = a;
        this.y = b;
    }
}

class Solution {
    public int bfs(int curX, int curY, int[][] picture) {
        Queue<Position> queue = new LinkedList<Position>();
        int areaValue = picture[curX][curY];
        queue.add(new Position(curX, curY));
        picture[curX][curY] = 0;
        int count = 1;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            Position pos = queue.poll();
            for (int i = 0; i<4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if (0 <= nx && nx < picture.length && 
                    0 <= ny && ny < picture[0].length && 
                    picture[nx][ny] == areaValue) {
                    queue.add(new Position(nx, ny));
                    count++;
                    picture[nx][ny] = 0;
                }
            }
        }

        return count;
    }

    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        int[][] copypicture = new int[picture.length][picture[0].length];

        for (int i = 0; i<m; i++)
            for (int j=0; j<n; j++)
                copypicture[i][j] = picture[i][j];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (copypicture[i][j] != 0) {
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, bfs(i, j, copypicture));
                    numberOfArea++;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}

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

풀이 과정

• 1, 2주차에 비해 난이도가 극악무도해져서 최대한 나중에 풀음ㅜㅜ
• 전체적으로 세개의 과정으로 나눌 수 있다.
  1. board에서 빈 블록 구하기
  2. table에서 넣을 블록 구하기
  3. (1)번에서 구한 빈 블록에 (2)번에서 구한 블록들을 1번, 2번, 3번, 4번 회전시키면서 넣어보고 맞는지 확인

1. board에서의 빈 블록과, table에서 넣을 블록들을 bfs로 구한다.
   • 이 때, 편의를 위해 블록들을 최대한 왼쪽 위로 붙여준다.
   • 예시로 4,4->4,5->4,6 블록을 (0,0 -> 0,1 -> 0,2)로 바꾸어 준다.
   • 방식은 블록들의 행의 최솟값과 열의 최솟값을 전체 블록에 빼주면 된다.
2. 블록 회전을 구현한다.
   • 블록 회전은 각 블록이 [행, 열]에 있을 때,
   • 회전된 블록은 [(블록들의 최대 열 - 현재 열), 행] 위치를 갖게 된다.
3. 이제 빈 블록에 대해서 블록들이 들어가는지 확인한다.
   • 블록을 4번 회전시키면 다시 자기자신으로 돌아오므로, 4번 회전시키면서 각각의 경우의 수에 대해 들어가는지 확인
   • 확인할 때 방식은 블록들과 빈 블록의 교집합을 하여, 교집합의 원소의 개수가 블록의 개수와 일치하면 블록이 들어가는것이다.

• 풀고나서 돌아보니 엄청 어려웠던것 같진 않은데.. 풀때는 되게 고민을 많이 한 문제였던 것 같다.

소스 코드

from collections import deque

def get_movement(arr, position, org_value, change_value):
    # board의 경우 org_value, change_value가 0, 1
    # table의 경우 org_value, change_value가 1, 0

    x, y = position[0], position[1]
    movement = [[x, y]]
    queue = deque([[x, y]])
    arr[x][y] = change_value
    min_x, min_y = x, y
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    length = len(arr)

    while queue:
        nx, ny = queue.popleft()
        for i in range(4):
            mx, my = nx + dx[i], ny + dy[i]
            if 0 <= mx < length and 0 <= my < length and arr[mx][my] == org_value:
                arr[mx][my] = change_value
                min_x, min_y = min(mx, min_x), min(my, min_y)
                movement.append([mx, my])
                queue.append([mx, my])

    movement = list(map(lambda f:(f[0]-min_x, f[1]-min_y), movement))
    return movement

def get_total_list(arr, f, value):
    length = len(arr)
    total_list = []
    org_value = value
    change_value = 1 if value == 0 else 0
    for i in range(length):
        for j in range(length):
            if arr[i][j] == value:
                total_list.append(f(arr, [i, j], org_value, change_value))

    return total_list

def rotate(block):
    max_col = max(map(lambda x:(x[1]), block))
    return list(map(lambda x:(max_col-x[1], x[0]), block))


def solution(game_board, table):
    answer = 0
    total_blank = get_total_list(game_board, get_movement, 0)
    total_block = get_total_list(table, get_movement, 1)
    used = [False] * len(total_block)
    for idx1, blank in enumerate(total_blank):
        for idx2, block in enumerate(total_block):
            if used[idx2] or len(blank) != len(block):
                continue

            temp = block
            find = False
            for i in range(4):
                temp = rotate(temp)
                if len(set(temp) & set(blank)) == len(temp):
                    find = True
                    break

            if find:
                used[idx2] = True
                answer += len(block)
                break

    return answer

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

풀이 과정

• 이전 챌린지에서 다른 사람들의 풀이를 보니, 컴프리헨션과 리스트의 함수들을 사용하는 모습을 보고, 소스가 훨씬 깔끔해 보이고 좋아보여서 최대한 사용해 보려고 해봄.

1. 최종적으로 목표는 리스트에 [승률, 몸무게가 무거운 복서를 이긴 횟수, 몸무게, 번호] 요소를 삽입하는것이 목적임.
   • 정렬은 마지막에 리스트의 sort 함수를 사용할 예정
2. 따라서, 각 인원에 대해서 조사
   • 인원의 승률을 구할 때는, 한번도 붙어보지 않은 경우에는 0, 한번이라도 붙어본 경우에는 W의 개수 / (W의 개수 + L의 개수)
   • 몸무게가 무거운 복서를 이긴 횟수를 구할 때는, 상대가 나보다 무거우면서 head2head의 값이 W인 개수를 구하면 된다.
   • 마지막에 현재 인원의 몸무게와 번호를 뒤에 붙여서 최종 리스트에 넣어주면 된다.
3. 최종 리스트 정렬
   • 정렬을 할 때, 승률로는 내림차순, 무거운 복서 이긴 횟수로 내림차순, 몸무게로 내림차순, 번호로 오름차순 순으로 정렬한다.
   • 파이썬에서 오름차순의 경우는 그냥 써주면 되지만, 내림차순의 경우는 약간의 꼼수로 -를 붙여주면 된다.
4. 번호만 따로 뽑아서 answer에 저장한 후 리턴해주면 된다.

소스 코드

def solution(weights, head2head):
    # [승률, 몸무게가 무거운 복서를 이긴 횟수, 몸무게, 번호]
    answer = []
    people_count = len(weights)
    result = []
    for i in range(people_count):
        if head2head[i].count('N') == len(head2head[i]): 
            winrate = 0
        else: 
            winrate = head2head[i].count('W') / (head2head[i].count('W') + head2head[i].count('L')) 
        heavy_win_count = len([1 for j in range(people_count) if weights[i] < weights[j] and head2head[i][j] == 'W'])
        result.append([winrate, heavy_win_count, weights[i], i+1])

    result.sort(key=lambda x:(-x[0], -x[1], -x[2], x[3]))

    for _, __, ___, n in result:
        answer.append(n)

    return answer

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