초니로그

문제 URL : https://school.programmers.co.kr/learn/courses/30/lessons/42885

문제 설명

사람들의 무게를 담은 배열과 구명보트 1개가 최대로 담을 수 있는 무게의 한계값(limit)이 주어짐

이를 토대로 필요한 구명보트 수의 최솟값을 구해야 함

단, 구명보트에는 최대 2명만이 탑승할 수 있음

풀이법 구상

무게 배열을 정렬하고, 가장 큰 값과 작은 값을 더해서 limit을 넘는지 안 넘는지를 토대로 개수를 구함

[큰 값과 작은 값을 더했을 때 limit 이하인 경우]

-> 두 사람(큰 값, 작은 값)이 보트 하나에 탔다고 치고, 큰/작은 값에 해당하는 인덱스를 한 칸씩 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

[큰 값과 작은 값을 더했을 때 limit 초과인 경우]

-> 한 사람(큰 값)만 보트에 태우고, 큰 값에 해당하는 인덱스를 한 칸 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

코드 구현 (Java)

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int idx = 0;
        for (int i=people.length-1; i>=idx; i--) {
            if (people[i]+people[idx] <= limit) idx++;
            answer++;
        }
        return answer;
    }
}

문제 링크 - https://softeer.ai/practice/6282

문제 설명

배열의 크기 n과 n*n의 배열값이 입력됨(0: 장애물X, 1: 장애물O)

좌측 최상단을 0,0으로 여기는 n*n의 2차원 배열을 탐색하며,

상하좌우로 연속된 장애물 구역의 총 개수와 각 장애물 구역 내의 장애물 개수를 오름차순으로 출력

풀이법 구상

기본 DFS/BFS를 통한 탐색 문제

코드 구현 (자바 사용)

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));
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
        for(int i=0; i<N; i++) {
            char[] input = br.readLine().toCharArray();
            for(int j=0; j<N; j++) map[i][j] = Character.getNumericValue(input[j]);
        }
        
        // BFS를 활용한 블록 탐색
        ArrayList<Integer> block = new ArrayList<>();
        
        boolean[][] ch = new boolean[N][N]; // 방문 여부 확인용(방문O - true / 방문X - false)
        Queue<int[]> q = new LinkedList<>();
        
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == 1 && !ch[i][j]) {
                    int cnt = 1; // 장애물 개수
                    q.offer(new int[]{i,j});
                    ch[i][j] = true;
                    while(!q.isEmpty()) {
                        int[] cur = q.poll();
                        for(int d=0; d<4; d++) {
                            int nx = cur[0] + dx[d];
                            int ny = cur[1] + dy[d];
                            
                            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 지도 범위를 벗어난 경우
                            if(map[nx][ny] == 0) continue; // 도로인 경우
                            if(map[nx][ny] == 1 && ch[nx][ny]) continue; // 이미 방문한 장애물일 경우

                            q.offer(new int[]{nx,ny});
                            ch[nx][ny] = true;
                            cnt++;
                        }
                    }
                    block.add(cnt);
                }
            }
        }

        // 결과 출력
        Collections.sort(block);
        System.out.println(block.size());
        for(int b : block) System.out.println(b);
    }
}

코드 구현 (파이썬 사용)

def dfs(x,y):
    if x<0 or x>=n or y<0 or y>=n: return False
    if arr[x][y] == 1:
        sum.append(1)   # 연속된 구역 내 장애물 개수 +1
        arr[x][y] = 0   # 방문처리
        # 상하좌우 탐색
        dfs(x,y+1)
        dfs(x,y-1)
        dfs(x-1,y)
        dfs(x+1,y)
        return True
    return False
        

n = int(input())
arr = []
for _ in range(0,n): arr.append(list(map(int, input())))

sum = []  # 연속된 구역 내 장애물 개수를 추가할 배열
sum_arr = []
for p in range(0,n):
    for q in range(0,n):
        if dfs(p,q) == True: 
            sum_arr.append(len(sum)) # 연속된 하나의 구역을 탐색한 후, 구역 내 장애물 개수를 결과에 추가
            sum = []   # 새로운 연속된 구역 내 장애물 개수를 파악하기 위해 초기화

sum_arr.sort()
print(len(sum_arr))
for i in range(0,len(sum_arr)): print(sum_arr[i])