인간 코딩(오류판)

19583 싸이버개강총회 

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

문제설명

스트리밍에서 특정 시간 범위에 참석한 사람들을 찾는다.

1. S: 시작 시간
2. E: 종료 시간
3. Q: 질문 시간

여러 사람의 출입 기록이 주어지며 각 기록은 시간과 이름으로 이루어져 있다.

S 시간 이전에 이벤트에 참석한 사람들 중 E 시간 이후 Q 시간 이전에도 참석한 사람들의 수를 세는 것이다.

문제풀이

• Set 사용:
  • S 시간 이전에 들어온 사람들의 이름을 저장한다.
  • E 시간 이후 Q 시간 이전에 들어온 사람들의 이름을 저장한다.
  • 모든 참석자의 이름을 저장한다.
• 시간 비교:
  • 각 기록의 시간과 S, E, Q를 비교하여 적절한 Set에 이름을 추가한다.
  • Set에 모두 포함된 사람의 수를 세어 출력한다.

O(N+M)  시간복잡도

• 입력 처리: 각 출입 기록을 한 번씩 읽으므로 O(N)이다. 여기서 N은 입력된 기록의 수이다.
• Set의 탐색 및 삽입: Set에 삽입과 탐색을 수행하는데 상수 O(1)의 시간 복잡도를 가진다.
• 결과 계산: nameSet에 있는 모든 이름을 확인하므로 O(M)입니다. 여기서 M은 서로 다른 참석자의 수이다.

전체 알고리즘의 시간 복잡도는 O(N + M)이다.

전체코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String S = st.nextToken();
        String E = st.nextToken();
        String Q = st.nextToken();

        Set<String> before = new HashSet<>();
        Set<String> after = new HashSet<>();
        Set<String> nameSet = new HashSet<>();
        String str = null;

        while((str = br.readLine()) != null) {
            String[] arr = str.split(" ");
            String time = arr[0];
            String name = arr[1];

            nameSet.add(name);
            if(S.compareTo(time) >= 0) {
                before.add(name);
            }else if(E.compareTo(time) <= 0 && Q.compareTo(time) >= 0) {
                after.add(name);
            }
        }

        int ans = 0;
        for(String name : nameSet) {
            if(before.contains(name) && after.contains(name)) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

1743 음식물 피하기 

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

문제설명

N×M 크기의 격자(grid)에서 음식물 쓰레기를 찾고, 가장 큰 연결된 덩어리의 크기를 구한다.

음식물 쓰레기는 특정 좌표에 위치하며, 연결된 덩어리는 상하좌우로 인접한 음식물 쓰레기로 정의된다.

문제풀이

• 격자의 크기 N, M과 음식물 쓰레기의 개수 K를 입력받고
• 모든 격자의 셀을 확인하면서 아직 방문하지 않은 음식물 쓰레기
• (map[i][j]가 true이면서 visited[i][j]가 false인 경우)에 대해 BFS를 수행한다.
• BFS를 시작하면 연결된 모든 음식물 쓰레기를 방문하며, 그 크기를 카운트한다.

• • 최대 크기 업데이트:
    • 각 BFS 호출 후, 현재 덩어리의 크기가 지금까지 기록된 최대 크기보다 크면 업데이트한다.

O(N×M)  시간복잡도

모든 셀을 한 번씩 방문하며, BFS는 각 연결 요소의 모든 셀을 탐색하므로 전체 격자를 한 번 스캔하는데 걸리는 시간이다.

전체코드

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

public class Main {
    static int N,M,K,ans,cnt;
    static int dx[]= {-1,1,0,0};
    static int dy[]= {0,0,-1,1};
    static boolean[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new boolean[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[r-1][c-1]=true;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(!visited[i][j] && map[i][j]) {
                    cnt=0;
                    bfs(i,j);
                    ans = Math.max(ans, cnt);
                }
            }
        }
        System.out.println(ans);

    }

    private static void bfs(int x, int y) {
        Queue<point> q = new LinkedList<>();
        q.add(new point(x, y));
        visited[x][y] = true;
        cnt++;
        while(!q.isEmpty()) {
            point temp = q.poll();

            for (int k = 0; k < 4; k++) {
                int xx = temp.x +dx[k];
                int yy = temp.y +dy[k];
                if(xx<0 || yy<0 || xx>=N || yy>=M)continue;
                if(!visited[xx][yy] && map[xx][yy]) {
                    q.add(new point(xx, yy));
                    visited[xx][yy]=true;
                    cnt++;
                }
            }
        }
    }

    static class point{
        int x;
        int y;
        public point(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
    }
}

20436 ZOAC 3

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

문제설명

QWERTY 키보드에서 문자열을 입력하는 데 필요한 시간을 계산한다.

자음과 모음을 구분하여 각각 왼손과 오른손으로 입력한다.

문제풀이

• QWERTY 키보드에서 자음과 모음은 각각 다른 맵에 저장된다.
• 각 키는 (행, 열) 좌표로 표현되며, 키보드의 각 위치가 미리 정의되어 있다.
  
  • 프로그램은 현재 왼손과 오른손의 위치를 추적한다.
  • 입력 문자열의 각 문자에 대해:
    • 문자가 자음인지 모음인지 검사한다.
    • 현재 손의 위치에서 해당 문자의 위치까지의 거리를 계산한다.
    • 맨해튼 거리 공식을 사용하여 거리를 계산한다. 거리=∣x1−x2∣+∣y1−y2
    • 문자를 입력한 후 손의 위치를 업데이트하고, 각 문자 입력에 대해 1초를 추가한다.

O(N) 시간복잡도

메서드는 키보드의 레이아웃을 초기화하는데, 상수 시간 O(1)이 소요된다.

 키보드 레이아웃은 고정되어 있다.

전체코드

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

public class Main {
    // 3D 배열로 5x5x5 미로 정의
    static int[][][] maze = new int[5][5][5], mazeCopy = new int[5][5][5];
    // 회전 및 층 정보를 저장할 배열
    static int arr[] = new int[5], floor[] = new int[5];
    // 층 사용 여부를 체크하는 배열
    static boolean check[] = new boolean[5];
    // 최단 경로 결과를 저장할 변수
    static int result = Integer.MAX_VALUE;
    // BFS에서 사용할 카운트 배열
    static int[][][] count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 미로 정보를 입력받기
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int l = 0; l < 5; l++) {
                    // 미로의 각 위치에 대한 값을 저장
                    maze[i][j][l] = Integer.parseInt(st.nextToken());
                }
            }
        }

        // 층 조합을 체크하여 가능한 모든 조합 탐색
        floorCheck(0);
        // 최단 경로가 발견되지 않았다면 -1 출력
        System.out.println((result == Integer.MAX_VALUE) ? -1 : result);
    }

    // 층 조합을 체크하는 메소드
    static void floorCheck(int k) {
        // 5개 층이 모두 선택되었을 때
        if(k == 5){
            // 회전 조합을 위한 백트래킹 호출
            backTracking(0);
            return;
        }

        for(int i = 0; i < 5; i++) {
            if(!check[i]) { // 사용되지 않은 층일 경우
                check[i] = true; // 층 사용 표시
                floor[k] = i; // 층 저장
                floorCheck(k + 1); // 다음 층으로 진행
                check[i] = false; // 층 사용 취소
            }
        }
    }

    // 회전 조합을 체크하는 백트래킹 메소드
    static void backTracking(int k) {
        if(k == 5) { // 5개 회전이 모두 선택되었을 때
            for(int i = 0; i < 5; i++) {
                rotation(); // 선택된 층을 회전
            }

            // 시작점과 목표점이 열려있는지 확인
            if(mazeCopy[0][0][0] == 1 && mazeCopy[4][4][4] == 1) {
                bfs(); // BFS를 통해 최단 경로 탐색

                if(count[4][4][4] != 0) { // 목표점에 도달한 경우
                    result = Math.min(result, count[4][4][4]); // 최단 경로 갱신
                    if(result == 12) { // 최단 경로가 12일 경우 즉시 종료
                        System.out.println(12);
                        System.exit(0);
                    }
                }
            }
            return;
        }

        for(int i = 1; i < 5; i++) { // 회전 종류를 선택
            arr[k] = i; // 현재 회전 저장
            backTracking(k + 1); // 다음 회전으로 진행
        }
    }

    // 선택된 층을 회전시키는 메소드
    static void rotation() {
        for(int i = 0; i < 5; i++) {
            int idx = floor[i]; // 현재 층 인덱스
            int rotationNum = arr[i]; // 현재 회전 번호
            for(int j = 0; j < 5; j++) {
                for(int l = 0; l < 5; l++) {
                    // 각 회전 방식에 따라 미로 복사
                    if(rotationNum == 1) {
                        mazeCopy[idx][j][l] = maze[i][j][l]; // 0도 회전
                    }
                    if(rotationNum == 2) {
                        mazeCopy[idx][l][4 - j] = maze[i][j][l]; // 90도 시계 방향 회전
                    }
                    if(rotationNum == 3) {
                        mazeCopy[idx][4 - j][4 - l] = maze[i][j][l]; // 180도 회전
                    }
                    if(rotationNum == 4) {
                        mazeCopy[idx][4 - l][j] = maze[i][j][l]; // 90도 반시계 방향 회전
                    }
                }
            }
        }
    }

    // BFS로 최단 경로를 찾는 메소드
    static void bfs() {
        int[][] dist = {{-1, 0, 0}, {1, 0, 0}, {0, 0, -1}, {0, 0, 1}, {0, 1, 0}, {0, -1, 0}}; // 방향 배열
        Queue<Pair> queue = new LinkedList<>(); // 큐 생성
        boolean[][][] visit = new boolean[5][5][5]; // 방문 여부 체크 배열
        count = new int[5][5][5]; // 경로 길이 저장 배열
        visit[0][0][0] = true; // 시작점 방문 처리
        queue.add(new Pair(0, 0, 0)); // 시작점 큐에 추가

        while (!queue.isEmpty()) { // 큐가 빌 때까지 반복
            Pair cur = queue.poll(); // 현재 위치 가져오기
            for(int i = 0; i < 6; i++) { // 6방향 탐색
                int nz = cur.z + dist[i][0];
                int nx = cur.x + dist[i][1];
                int ny = cur.y + dist[i][2];
                // 경계를 벗어나거나 이미 방문했거나 벽인 경우 continue
                if(nz < 0 || nz >= 5 || nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
                if(visit[nz][nx][ny] || mazeCopy[nz][nx][ny] != 1) continue;

                count[nz][nx][ny] = count[cur.z][cur.x][cur.y] + 1; // 경로 길이 증가
                if(nz == 4 && nx == 4 && ny == 4) {
                    return; // 목표점에 도달하면 종료
                }
                visit[nz][nx][ny] = true; // 방문 처리
                queue.add(new Pair(nz, nx, ny)); // 큐에 다음 위치 추가
            }
        }
    }

    // 좌표를 나타내는 Pair 클래스
    public static class Pair {
        int x; // x 좌표
        int y; // y 좌표
        int z; // z 좌표

        public Pair(int z, int x, int y) {
            this.x = x;
            this.y = y;
            this.z = z; // 생성자
        }
    }
}

2469 사다리 타기

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

문제설명

사다리 게임을 시뮬레이션한다.

문자들이 위에서 아래로 이동하면서 사다리의 구성에 따라 재배치되는 방식이다.

주요 목표는 특정 지점(?이 있는 줄) 이후에 문자가 어떻게 재배치될지를 파악한다.

문제풀이

시작 위치를 나타내는 문자 배열과 예상 최종 위치 배열을 생성한다.

• ? 줄 이전의 모든 줄은 각 -는 시작 배열의 문자를 서로 스왑한다.
• ? 이후의 줄에서도 동일한 스왑 작업을 예상 위치 배열에 수행한다.
  
  • 두 배열의 최종 상태를 비교한다:
    • 두 인접 문자가 같으면 *를 추가한다.
    • 스왑이 가능한 경우(즉, 인접한 경우), 스왑을 수행하고 -를 추가한다.
    • 문자가 일치하지 않거나 스왑이 불가능한 경우 x를 출력한다.

O(n⋅(k−1)) 시간복잡도

• ? 이전 처리:
  • ? 이전의 각 줄에 대해 모든 - 문자를 처리한다. 각 줄에서 -가 나타날 경우, 인접한 두 문자를 스왑한다.
  • 이 과정은 각 줄에 대해 최대 k−1 번의 스왑이 발생한다.
  • ? 이전의 모든 줄에 대해 총 스왑 연산 수는:
    • n 줄 × 최대 (k−1)스왑 = O(n⋅(k−1))
• ? 이후 처리:
  • ? 이후의 줄에서도 같은 방식으로 스왑을 수행한다.
  • 이 경우도 마찬가지로 각 줄에 대해 최대 (k−1) 번의 스왑이 발생한다.
  • ? 이후의 모든 줄에 대해 처리하는 것도 O(n⋅(k−1))이 소요된다.

전체코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int k = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());

        char[] startChar = new char[k];
        for(int i = 0 ; i < k ; i++){
            startChar[i] = (char)('A' + i);
        }
        char[] destinationChar = br.readLine().toCharArray();

        char[][] map = new char[n][k-1];
        int lineIdx = 0;
        for(int i = 0 ; i < n ; i++){
            map[i] = br.readLine().toCharArray();

            if(map[i][0] == '?')
                lineIdx = i;
        }

        for(int i = 0 ; i < lineIdx ; i++){
            for(int j = 0 ; j < k-1 ; j++){
                if(map[i][j] == '-'){
                    char tmp = startChar[j];
                    startChar[j] = startChar[j+1];
                    startChar[j+1] = tmp;
                }
            }
        }

        for(int i = n-1; i > lineIdx ; i--){
            for(int j = 0 ; j < k-1 ; j++){
                if(map[i][j] == '-'){
                    char tmp = destinationChar[j];
                    destinationChar[j] = destinationChar[j+1];
                    destinationChar[j+1] = tmp;
                }
            }
        }


        for(int i = 0 ; i < k-1; i++){
            if(startChar[i] == destinationChar[i]){
                sb.append("*");
            } else if(startChar[i] == destinationChar[i+1] || startChar[i+1] == destinationChar[i]){
                sb.append("-");
                char tmp = startChar[i];
                startChar[i] = startChar[i+1];
                startChar[i+1] = tmp;
            } else{
                for(int j = 0 ; j < k-1 ; j++)
                    System.out.print("x");
                System.out.println();

                return;
            }
        }
        System.out.println(sb);
    }
}