Skip to content

2023.10.26 ‐ 2023.11.01

Jump to bottom
yumyeonghan edited this page Dec 28, 2023 · 6 revisions

유명한

크로아티아 알파벳

🦊 문제 해결 과정

  1. 변경된 크로아티아 알파벳을 배열로 담는다.
  2. 알파벳을 순회하면서
    1. 입력값에 포함되는게 있으면 “#” 으로 대체한다. (알파벳의 길이를 1로 세기 위해)
    2. 입력값에 포함되는게 없으면 그냥 둔다 (목록에 없는 문자는 길이를 1로 세기 위해)
  3. 대체된 입력값의 전체 길이를 구한다.

🐥 코드 풀이 과정

// 1번 해결 과정
String[] alpha = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};

// 2번 과정
for (int i = 0; i < alpha.length; i++) {
    if (input.contains(alpha[i])) {
        input = input.replace(alpha[i], "#");
    }
}

좌표 압축

🦊 문제 해결 과정

  1. 좌표의 순위를 정하는 문제
  2. 기존 배열과 정렬할 배열을 초기화 한다.
  3. 우선, 해당 좌표와 그 좌표의 랭킹을 저장할 맵을 초기화한다.
  4. 정렬할 배열을 오름차순 정렬을 한다.
  5. 정렬된 배열을 하나씩 순회할 때 만약, 맵에 키가 있으면 순위를 1 카운팅
  6. 기존 배열을 하나씩 순회하면서 순차적으로 랭킹을 출력

🐥 코드 풀이 과정

// 2, 3번 과정
int[] origin = new int[n];
int[] sorted = new int[n];
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < n; i++) {
    origin[i] = scanner.nextInt();
    sorted[i] = origin[i];
}

// 5번 과정
for (int v : sorted) {
    if (!map.containsKey(v)) {
        map.put(v, rank);
        rank += 1;
    }
}

// 6번 과정
for (int key : origin) {
    int ranking = map.get(key);
    stringBuilder.append(ranking).append(' ');
}

미로 탈출

🦊 문제 해결 과정

  1. 시작점 → 레버의 최단거리 + 레버 → 종료지점의 최단거리 를 bfs를 통해 해결
  2. 주어진 maps 배열의 정보를 가져와 Character[][] graph 초기화
    1. 이때 bfs에서 사용될 시작점 위치와 레버의 위치 정보를 각각 초기화
  3. bfs를 통해 시작점 → L(레버 위치) 와 레버 위치 → E(종료 지점) 의 최단 거리 구함
    1. 큐에 {x, y, count} 정보 추가
      1. x : x 좌표
      2. y: y coordinate
      3. count: 이동 거리
    2. 방문 처리 배열 초기화 (bfs()를 호출할 때마다 초기화 함)
    3. 큐가 빌때까지 반복
      1. 큐에서 정보를 꺼내와 만약 목적지점이라면 count 반환
      2. 그렇지 않으면 다음 위치로(4가지 방향) 이동하며 카운트 1 증가 (큐에 삽입)
      3. 이때 이동할 위치가 범위 안에 있고, 방문하지 않았으며, 벽(X)이 아니어야 함
    4. 큐가 비었음에도 목표지점에 못갔을 경우 -1 반환
  4. 최종적으로 두 최단 거리의 합 반환

🐥 코드 풀이 과정

// 2번 과정
for (int i = 0; i < maps.length; i++) {
    for (int j = 0; j < maps[0].length(); j++) {
        graph[i][j] = maps[i].charAt(j);
        if (graph[i][j].equals('S')) {
            start[0] = i;
            start[1] = j;
        }
        if (graph[i][j].equals('L')) {
            lever[0] = i;
            lever[1] = j;
        }
    }
}

// 4번 과정
int toLever = bfs(start, 'L');
int toExit = bfs(lever, 'E');

if (toLever == -1 || toExit == -1) {
    return -1;
}
return toLever + toExit;

// 3번 과정
private int bfs(int[] startPoint, Character targetPoint) {
    Queue<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{startPoint[0], startPoint[1], 0});
    boolean[][] visited = new boolean[graph.length][graph[0].length];
    while (!queue.isEmpty()) {
      int[] inf = queue.poll();
      int x = inf[0];
      int y = inf[1];
      int count = inf[2];
      visited[x][y] = true;
      if (graph[x][y].equals(targetPoint)) {
        return count;
      }
      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < graph.length && ny >= 0 && ny < graph[0].length && !visited[nx][ny]) {
          if (!graph[nx][ny].equals('X')) {
            visited[nx][ny] = true;
            queue.add(new int[]{nx, ny, count + 1});
          }
        }
      }
    }
    return -1;
}

정경원

잃어버린 괄호

🦊 문제 해결 과정

  1. sum을 초기화하고 주어진 문자열을 “-” 기호로 분리
    1. StringTokenizer 사용
  2. 반복문을 돌면서 주어진 토큰에 대해서 다시 “+” 기호로 분리
    1. 첫 값은 초기화하여 +sum
    2. 이후 값은 -sum
  3. 괄호를 추가하여 이 문자열의 최소 값을 구함

🐥 코드 풀이 과정

  1. 코드 단락, 이유 1
// 1번 해결 과정
int sum = Integer.MAX_VALUE; //'-'를 통해 분리된 문자열의 합
StringTokenizer st2 = new StringTokenizer(st.nextToken(), "+");
  • 해설
    • 주어진 문제에서 5자리보다 많이 연속되는 숫자는 없다 하였으므로 sum을 max값으로 초기화
    • cf: 0으로 초기화 하면 연산 도중 0이 나와서 잘못된 결과가 나올 수 있음
  1. 코드 단락, 이유 2
// 2번 해결 과정
    while (st.hasMoreTokens()) {

        int sum2 = 0; //토큰으로 분해된 값들의 개별 합 ex) 55,(50,40)
        StringTokenizer st2 = new StringTokenizer(st.nextToken(), "+");

        while (st2.hasMoreTokens()) {
            sum2 += Integer.parseInt(st2.nextToken());
        }
        if (sum == Integer.MAX_VALUE) {
            sum = sum2; // "-"로 분리된 첫번째 항이면 sum을 초기화
        }
        else{
            sum -= sum2; //아니라면 -sum2을 하여 최소값을 구함
        }
    }

스택

🦊 문제 해결 과정

  1. 명령에서 주어질 정수를 담을 stack & 명령을 출력할 객체 생성
  2. 반복문을 돌면서 주어진 명령에 대한 작업을 수행
    1. 수행하면서 나온 결과를 stringBuilder 객체에 저장
  3. 결과를 출력

🐥 코드 풀이 과정

  1. 코드 단락, 이유 1
// 1번 해결 과정
var s = new Stack<Integer>(); //명령에서 주어진 정수를 담을 stack
StringBuilder sb = new StringBuilder(); //명령을 출력할 객체
  1. 코드 단락, 이유 2
for (int i = 0; i < n; i++) {
        String order = sc.next(); //명령
        if (order.equals("push")) {
            s.push(sc.nextInt()); //stack에 push
        }
        if (order.equals("pop")) {
            if (s.isEmpty()) {
                sb.append(-1).append("\n");
            }
            else{
                sb.append(s.pop()).append("\n");
            }
        }
        if (order.equals("size")) {
            sb.append(s.size()).append("\n");
        }
        if (order.equals("empty")) {
            if (s.isEmpty()) {
                sb.append(1).append("\n");
            }
            else{
                sb.append(0).append("\n");
            }
        }
        if (order.equals("top")) {
            if (s.isEmpty()) {
                sb.append(-1).append("\n");
            }
            else{
                sb.append(s.peek()).append("\n");
            }
        }
    }

카드 뭉치

🦊 문제 해결 과정

  1. 문제에서 주어진 카드배열 요소를 비교를 쉽게 하도록 배열 → 리스트 옮겨 담음
  2. 반복문을 통해 목표 배열의 문자열이 나오지 않으면 종료
    1. 2개의 카드 요소 배열의 첫번째 요소를 탐색함
      1. 일치하면 해당 요소를 제거 → 카드 재사용이 안되기 때문에
      2. 일치하지 않으면 answer 값 → No로 변경하고 반복문 종료

🐥 코드 풀이 과정

// 1번 해결 과정
var cardList1 = new LinkedList<String>();
var cardList2 = new LinkedList<String>();

Collections.addAll(cardList1, cards1);
Collections.addAll(cardList2, cards2);

// 2번 과정

for (String goalCard : goal) {

    //goal 의 크기 > list 의 크기 라면 예외 처리
    if (!cardList1.isEmpty() && cardList1.peekFirst().equals(goalCard)) {
        cardList1.removeFirst();
    }
    else if (!cardList2.isEmpty() && cardList2.peekFirst().equals(goalCard)) {
        cardList2.removeFirst();
    }
    else {
        answer = "No";
        break;
    }
}

호텔 대실

🦊 문제 해결 과정

  1. 문제에서 주어진 배열을 2차원 배열에 옮겨 담음
    1. 시작 시각과 종료 시각을 분 단위로 하여 저장
  2. 배열 정렬
    1. 시간 순서대로 손님이 들어오므로 대실 시작 시각 순 정렬
    2. 우선순위 큐를 사용하여 큐에 들어온 손님의 종료 시각이 짧은 순 정렬
  3. 반복문
    1. 현재 큐에 있는 대실의 종료 시각과 다음 대실의 시작 시간 + 청소 시간(10분)을 비교
      1. 다음 대실 시작 시각 > 퇴실할 시각 + 청소 시각 → 다음 사용자가 대체
      2. 아직 퇴실할 시각이 아님 → 방 개수 증가
      3. answer = 현재 필요로하는 방의 개수

🐥 코드 풀이 과정

// 1번 해결 과정
int[][] hotel = new int[book_time.length][2];

for (int i = 0; i < book_time.length; i++) {
    String[] tmp1 = getSplitTime(book_time[i], 0);
    hotel[i][0] = getTime(tmp1); //대실 시작 시각 저장

    String[] tmp2 = getSplitTime(book_time[i], 1);
    hotel[i][1] = getTime(tmp2); //대실 종료 시각 저장
}

// 2번 과정
    //1. 대실 시작 시각 순 정렬
    Arrays.sort(hotel, Comparator.comparingInt(o -> o[0]));

    //2. 대실 종료 시각 순 정렬
    //시작 시각과 종료 시각을 비교하여 방을 생성할 list(queue) 생성
    PriorityQueue<int[]> room =
            new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));

// 3번 과정
for (int i = 1; i < hotel.length; i++) {

    int next_start = hotel[i][0]; //다음 대실 시작 시각
    int next_end = hotel[i][1]; //다음 대실 종료 시각

    //현재 대실 종료 시각 + 10분(청소 시간) 과 다음 대실 시작 시간을 비교
    while (!room.isEmpty() && next_start >= room.peek()[1] + 10) {
        room.poll();
    }
    room.add(new int[]{next_start, next_end});
    answer = Math.max(answer, room.size());
}

//1-a 메서드 
//시와 분을 나눔
private static String[] getSplitTime(String[] book_time, int x) {
    return book_time[x].split(":");
}

//시간을 저장
private static int getSaveTime(String[] time) {
    return Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
}
Clone this wiki locally