뱀 #3190

골드 4

문제 이해

• 그리드 크기: N
• 시작점
  • 위치: (0, 0)
  • 뱀의 길이: 1
• 탐색 종료 시점 2가지
  • (1) x 또는 y 좌표가 그리드를 벗어날 때
    • x < 0 또는 y < 0 또는 x >= N 또는 y >= N
  • (2) 뱀이 자기 자신의 몸과 부딪힐 때
• 탐색 방법 2가지
  • (1) 사과가 없는 좌표로 이동할 때
    • 몸 전체가 좌표를 한칸씩 전진
  • (2) 사과가 있는 좌표로 이동할 때
    • 몸 길이를 늘려서 사과 있는 좌표까지 몸을 뻗음
• 이외 정보
  • (시간, 방향)이 주어지면 시간 값 이후로 방향을 전화해서 이동함

해결방안 고안

• 그리드 int[][] grid
  • 0 은 기본 (사과 없음, 뱀 없음)
  • 1 은 뱀의 몸이 존재하는 좌표
  • 2 는 사과가 존재하는 좌표
    • 입력값으로 주어지는 K개의 사과 좌표들에 대해 grid[y][x] = 2 처리한다.
• 뱀 LinkedList<int[]> snake
  • 뱀이 차지한 좌표에 대한 링크드 리스트
  • 0번째 값은 꼬리의 좌표, snake.size()-1번째 값은 머리의 좌표에 해당한다
  • 용도: 사과가 없는 좌표로 이동할 때 꼬리 좌표를 0처리하고 머리 좌표를 새 좌표로 이동해야 한다. 이 때 꼬리 좌표는 grid[tailY][tailX]=0을 처리하고, 이 링크드리스트에 대해 removeFirst를 수행해서 꼬리 좌표를 업데이트한다.
• 이동 방향 int[] dyx = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
  • 뱀의 이동 방향은 동쪽에서 시작해서 시계방향 또는 시계 반대방향으로 90도씩 바뀔 수 있다.
  • 오른쪽(D)로 90도는 dyx에서 인덱스+1, 왼쪽으로 90도는 인덱스-1로 처리한다.
  • 인덱스 범위 내로 값을 유지하도록 (directionIdx+4+(방향이동)) % 4)로 처리한다.

입력 받기

• int N : 그리드 한 변의 크기
  • grid = new int[N][N] : N으로 그리드를 초기화한다
• int K : 사과 개수
  • K로 for loop을 수행해서 좌표값 y와 x를 받는다
  • 이 때 배열 좌표로 사용하기 위해서는 y와 x에 각각 1을 빼줘야 한다
  • grid[y][x] = 2로 그리드에 사과를 표시한다
• int L : 방향 이동 시점 및 오른쪽/왼쪽 여부
  • int[][] moves = new int[L][2]에 담는다
  • moves[i][0]에 방향 바꾸는 시점을 담는다
  • moves[i][1]에 오른쪽으로 도는지, 왼쪽으로 도는지 담는다
    • 오른쪽(D)이면 1, 왼쪽(L)이면 -1

탐색 로직

탐색은 (1) 방향 이동 배열에 관한 탐색 과정 (2) 방향 이동은 모두 끝난 시점에서 탐색 과정의 2 개의 반복문으로 구성했다.

(1) 방향 이동 배열에 관한 탐색

• 변수 선언 및 초기화

  • int headY = 0, int headX = 0 : 뱀의 머리 좌표를 저장한다
  • int tailY = 0, int tailX = 0 : 뱀의 꼬리 좌표를 저장한다
  • int directionIdx = 0 : 방향 배열의 좌표를 저장한다
    • 오른쪽으로 90도 꺾으면 (D) 이 변수에 1을 더한다
    • 왼쪽으로 90도 꺾으면 (L) 이 변수에 1을 뺀다
  • int prevTime = 0 : 현재 시점을 저장한다
  • int ny = 0, int nx = 0 : 탐색할 좌표를 저장한다

• 방향 이동 배열에 대한 for loop

  • 현재 시점에서 다음 방향이 이동이 일어나는 시점까지 지금 방향으로 계속 이동한다
  • for (int i = 0; i < L; i++)
  • 현재 시점에서 방향이 이동하는 시점(moves[i][0]) 간 시간차(int timeInterval)를 구한다
  • 1초마다 1칸씩 움직인다 => 1초마다 다음으로 탐색할 좌표 (ny, nx)를 확인한다
    • 1초마다 움직이기 때문에 for (int j = 1; j <= timeInterval; j++) for loop을 구현한다

• nested for loop (timeInterval에 대한 for loop) 내부 구현

  • 매초 ny, nx 값을 업데이트한다
    • ny = headY + dyx[directionIdx][0]
    • nx = headX + dyx[directionIdx][1]
  • ny, nx 값이 그리드를 벗어나거나, 뱀이 이미 차지한 좌표 (grid[ny][nx]==1)라면 게임이 끝나니 현재 시점 (prevTime + j)를 리턴한다
  • 리턴 조건이 만족되지 않은 경우 다음 2가지를 수행한다
    • (1) headY, headX (머리 좌표) 값을 업데이트하고, 뱀 링크드리스트에 추가한다
    • (2) 사과가 없는 좌표면 꼬리 좌표의 값(grid[tailY][tailX])을 1에서 0으로 바꾸고, snake.removeFirst()로 꼬리 좌표를 최신 업데이트한다
    • 사과가 있는 좌표면 이동이 아닌 몸 늘리기이기 때문에 추가적으로 수행할 건 없다.

• nested for loop이 끝나면 다음 방향 이동 건으로 넘어가기 전에 directionIdx와 prevTime을 업데이트한다

  • directionIdx = (4+directionIdx+moves[i][1]) % 4
  • prevTime = moves[i][0]

(2) 방향 이동이 끝난 시점에서부터의 탐색

방향 이동이 모두 완료됐음에도 아직 게임이 끝나지 않았으면, 게임 종료 조건을 만족할 때까지 마지막 방향 이동에서 정해진 방향으로 계속 이동한다.

그래서 while loop을 활용해서 매 루프마다 다음을 수행한다

• ny, nx 값을 업데이트한다
  • ny = ny + dyx[directionIdx][0]
  • nx = nx + dyx[directionIdx][1]
• 현재 시점 업데이트
  • prevTime++
• 게임 종료 조건 확인
  • if (ny < 0 || nx < 0 || nx >= N || ny >= N || grid[ny][nx] == 1) return prevTime;

코드 설명 및 보완

뱀 #3190 풀이 코드

일단 빨리 풀고 싶어서 코드를 짜다보니 깔끔한 코드는 아니고.. 통과할 수 있는 코드를 짠 것 같다.

아예 outer for loop을 while 문으로 대체해서 탐색 2파트를 하나의 파트로 합칠 수 있을 것 같다.

---

(깍두기) 뉴스 전하기 #1135

골드 2

문제 이해

• 길이 N의 입력 배열 A가 주어진다
  • i번째 요소의 부모(직속 상사)는 A[i] 다
  • 단, 민식이는 상사가 없어서 위 조건을 만족하지 않는다
• 직속 부모만 전화할 수 있다

해결 방안 고안

상식적으로 가장 오래 걸리는 자식 (서브 트리)부터 전화를 걸어야지 최소 시간을 얻을 수 있다.

예를 들어 루트 노드 (0)이 3개의 서브트리 A, B, C를 갖는다고 가정하자.

서브트리 A는 총 2초가 걸리고, 서브트리 B는 총 3초, 그리고 서브트리 C는 총 1초가 걸린다. 그러면 B-A-C 순으로 방문해야 한다. 그런데, 루트 노드에서 동시에 3개의 서브트리 전부를 방문할 수 없기 때문에 가장 오래 걸리는 서브트리부터 순차적으로 1초씩 걸려서 방문해야 한다.

그래서 루트 노드에서 서브트리 B를 방문하는데 1초, 그리고 서브트리 B에 걸리는 총 시간 3초를 더해 최종적으로 4초가 걸린다. 서브트리 A는 1 + 2 (서브트리 A에 걸리는 시간) = 3초가 걸린다. 서브트리 3은 총 2초가 걸린다.

하나의 노드가 동시에 여러 곳에 전화를 거는 것은 허용되지 않지만, 하나의 노드가 전화를 하는 사이에 다른 노드가 전화하는 동시 전화는 허용되기 때문에 위 값 중 최대 값을 답으로 반환하면 된다.

코드

프로그래밍으로 접근해보자.

<해결 방안 고안> 섹션에서 루트 노드서부터 부모, 그 다음 자식 순으로 접근했듯이 Top-down 방식으로 DFS를 수행하면 된다.

입력 배열을 List<List<Integer>> tree에 저장하는데, 각 인덱스에 자신의 자식들의 번호를 저장한다.

루트 노드 (0)부터 시작해서 현 노드의 자식에 대해 DFS를 수행해서 현 노드에 대한 서브트리에 걸리는 총 시간을 얻어낸다. 그러기 위해서는 DFS 내부 로직에 위에서 언급한 시간 연산 로직을 포함해야 한다.

• DFS 탈출 조건은 현 노드가 리프 노드일 때다. 리프 노드는 더 이상 전화 걸 곳이 없으니 0을 리턴하면 된다.
• 현 노드의 각 자식을 처리하는데 걸리는 시간을 모두 담을 List<Integer> children = new ArrayList<>()를 초기화한다.
  • 트리에 저장한 현 노드의 직속 자식부터 DFS를 수행해서 걸리는 시간의 값을 children 리스트에 추가한다.
  • 재귀로 리프 노드부터 각각 걸리는 시간을 (이 뒤에 설명할 로직 기반으로) 차곡차곡 쌓아올 것이다.
• 가장 오래 걸리는 노드부터 방문하기 때문에 children 리스트를 내림차순으로 정렬한 다음 time=1을 1초씩 추가해가며 더한다
• 이 연산값을 priority queue (max heap으로 바꿔서)에 저장해서 걸리는 최대 시간을 리턴한다

뉴스 전하기 # 1135 풀이 코드

보완

코딩테스트 스터디에서 우선순위큐 주제 관련으로 뽑은 문제였다. 문제 풀이 과정에서 최대 시간을 얻어내는 과정에서 우선순위큐를 사용했는데, for loop 내부에서 매번 pq.add() 연산을 해서 시간 복잡도가 O(n*log n)이다. 시간 복잡도 면에서는 단순하게 Math.max()를 하는 것이 더 좋았을 것 같다.

---

칸토어 집합 #4779

실버 3

문제 이해

입력 N이 주어졌을 때 3의 N승 길이의 "-" 문자열을 가정한다.
(예) N이 1이 주어지면 "---"을 가정한다.

문자열을 삼등분해서 중간 부분을 공백으로 대체하는데, 모든 연속 "-"의 길이가 1일 때까지 이 작업을 반복한다.

해결 방안 고안

탈출 조건 (연속 "-" 길이가 1)이 정해져 있어서 재귀 문제라고 판단했다.

"-"의 길이가 1이라면 "-" 사이의 공백 또한 1이라는 점에 집중했다.

삼등분 중 중앙의 "-"을 공백으로 대체하니 나는 공백의 시작점과 끝점을 알고 싶다는 생각이 들었다. 삼등분이라는 조건이 주어졌으니 문자열의 시작과 끝점을 알면 공백의 시작점과 끝점은 구할 수 있었다.

int diff = (end - start) / 3;
int mid1 = start + diff;
int mid2 = start + diff * 2;

그래서 나는 이 문제를 (문자열) + (공백) + (문자열)의 형태로 이해했다. 그래서 문자열의 시작점과 끝점을 인수로 받는 재귀함수를 구상했다.

private static String divide(int start, int end) {
    if (end == 1) return "-";
    int diff = (end - start) / 3;
    int mid1 = start + diff;
    int mid2 = start + diff * 2;
    if (mid2 - mid1 == 1)
        return "- -";
	return divide(start, mid1) + " ".repeat(diff) + divide(mid2, end);
}

코드 설명

칸토어 집합 #4779 코드

삽질

삽질은 예상치 못한 곳에서 발생했다. 파일의 끝에서는 프로그램을 종료해야 한다는데 입력을 몇 개 줄지 알려주지도 않고 어떻게 프로그램을 종료해야 할지 이해가 안 갔다.

br.readLine()로 입력을 받는다고 가정하면 이에 대한 Integer.parseInt를 하는 줄에 try-catch 문을 걸어서 에러 발생시 프로그램을 종료하면 된다.

---

특별상이라도 받고 싶어 #24460

실버3

문제 이해

• 2의 제곱인 N이 입력으로 주어진다
• N의 제곱 개의 점수가 주어진다
• 그리드를 같은 크기의 정사각형 네 개로 나눠서 각 구역에서 재귀적으로 두번째로 점수가 작은 사람을 뽑는다

해결 방안 고안

4개의 점수 중 두번째로 작은 값을 찾는 게 가장 기본적인 연산이라 판단해서 베이스 케이스를 한 변의 길이가 2인 경우로 결정했다.

N=2이고, x=0, y=0인 경우에는 해당 구역에 {{0, 0}, {0, 1}, {1, 0}, {1, 1}} 의 좌표가 존재한다. 이 좌표들은 {0, 0}을 기준으로 각각 이동 없음, 오른쪽으로 한 칸, 아래로 한칸, 대각선으로 한칸 이동이기 때문에 사방 탐색 로직으로 dx, dy 배열을 선언했다.

• int[][] dyx = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}
  • dy, dx 배열로 나눠서 선언했으면 더 깔끔했을 것 같다
  • int[] dy = {0, 0, 1, 1}
  • int[] dx = {0, 1, 0, 1}

이렇게 구한 좌표들을 기반으로 4개 값을 가져오면 이 중 두번째로 작은 값을 구하면 된다.

배열을 오름차순으로 정렬한 다음 인덱스 1의 값을 가져오면 직관적이지만, 시간 복잡도를 최소화하기 위해 Math.min을 활용하고자 했다. 4개 값 중 최소 값을 찾아 제거하고, 남은 3개 값 중 최소 값을 찾아 리턴하는 함수를 설계했다.

풀이 코드

특별상이라도 받고 싶어 #24460 풀이 코드

삽질

로직은 직관적이였지만, 테스트케이스 통과 97%에서 시간 초과 에러가 발생해서 어려움을 겪었다.

1. PriorityQueue

맨 처음으로 시도했던 방법이다. Priority Queue (디폴트로 min heap) 에 네 좌표의 값을 추가해서 두번째 .poll()의 값을 리턴하는 방식으로 두번째로 작은 값을 얻었다.

하지만 우선순위큐의 시간 복잡도를 간과했다. .poll()은 단순히 루트 노드를 리턴하기 때문에 O(1)이지만 .add()는 O(log N)를 가진다. 데이터 추가 후 heapify 과정을 통해 min heap의 구조를 유지해야 하기 때문이다.

2. Arrays.sort()

백준이 테스트케이스 검증에 사용하는 Java11 기준으로 quick sort를 사용해서 해당 함수를 구현하기 때문에 O(n)에서 O(n^2)까지 걸릴 수 있다. 평균적으로는 O(n * log(n))이지만 최악인 O(n^2)을 생각하면 좋지 못한 선택이다.

참고로 Java 14부터는 최악의 경우에도 O(n * log (n))를 보장하도록 구현되었다고 한다

자료 출처

https://velog.io/@becooq81/JAVA-Priority-Queue%EB%A5%BC-%EC%82%AC%EC%9A%A9%ED%95%B4%EB%B3%B4%EC%9E%90
https://stackoverflow.com/questions/22571586/will-arrays-sort-increase-time-complexity-and-space-time-complexity

---

키로거 #5397

실버2

문제 이해

• 테스트케이스가 T개 주어진다
• 각 테스트케이스는 길이가 L(1<=L<=1,000,000)인 문자열이다
• 문자열은 키보드 입력으로 특수한 케이스를 구별해야 한다
  • '<' : 화살표 왼쪽 이동
  • '>' : 화살표 오른쪽 이동
  • '-' : 백스페이스

해결 방안 고안

입력을 인덱스 0부터 순차적으로 탐색하는 while loop으로 설정한 다음, 각각 입력에 대해서 특수 케이스 3개와 일반 키보드 입력을 구분하는 if-else 구조로 가고자 한다.

입력에 대한 인덱스 말고도, 결과(링크드리스트로 관리)에 대한 인덱스도 관리했다. 입력 인덱스는 키보드 입력의 인덱스고, 결과 인덱스는 다음 입력값을 저장할 인덱스라고 정의한다.

예를 들어, a<b라는 입력이 주어진다면, while loop가 다음과 같이 진행 될 것이다

1. 입력 인덱스=0, 결과 인덱스=0
2. 입력 인덱스=1, a 입력, 결과 인덱스=1 (다음 입력은 a 다음 요소로 받을 것)
3. 입력 인덱스=2, < 입력, 결과 인덱스=0 (다음 입력은 a 이전 요소로 받을 것)
4. 입력 인덱스=3, b 입력, 결과 인덱스=1 (다음 입력은 b 다음 요소로 받을 것)

1. <

왼쪽 이동인 경우 결과 인덱스에서 1을 뺀다. 하지만 그 연산의 결과가 음수면 인덱스 범위를 벗어나기 때문에 0으로 재설정한다

2. >

오른쪽 이동인 경우 결과 인덱스에 1을 더한다. 하지만 그 연산의 결과가 링크드리스트(현재까지의 결과값을 저장한 것)의 크기보다 크면 인덱스의 범위를 벗어나기 때문에 링크드리스트의 크기 값으로 저장한다.

3. -

백스페이스는 두 가지 조건을 충족해야 값을 제거할 수 있다.

1. 링크드리스트에 값이 있어야 한다
2. 현재 결과 인덱스가 0보다 커야 한다

현재 결과 인덱스가 0이고, 글자를 추가하게 되면 내가 의도한 대로 링크드리스트의 맨 앞에 값을 추가할 수 있다. 하지만 글자를 제거하고자 할 때는 커서가 맨 앞에 있으니 아무것도 지워지면 안되는데, list.remove(0)는 링크드리스트의 첫 값을 제거한다. 그러니 list.remove(idx-1)로 구현해야 한다.

4. 일반 입력

알파벳 대소문자와 숫자 등 일반 입력이 들어오면 단순히 결과 인덱스 위치에 글자를 추가하면 된다. 매번 글자를 추가할 때마다 결과 인덱스 값을 1씩 늘려야 한다.

코드 설명

키로거 #5397 풀이 코드

삽질

1. Stack

~~생각을 깊이 안하고... 이번주 스터디 주제가 스택/큐니까 스택을 쓰자라고 생각했는데... 하여튼 특정 인덱스에서 글자를 제거하거나 추가해야 할 일이 많기 때문에 .push(), .pop()으로 해결할 수 있는 문제가 아니였다. ~~

스택으로 풀릴 수 없는 문제라고 생각했는데, 문제점은 스택을 하나만 사용했다는 거였다. 스택을 2개 사용해서 커서의 왼쪽과 오른쪽에 있는 값들을 비교하면 되었다. 이 풀이는 깃허브 링크에 있다.

2. ArrayList

그래서 removeAt(), add(int idx, Object o) 함수를 갖는 ArrayList를 사용하고자 했으나, 시간초과가 났다. ArrayList는 순차적인 데이터 추가 및 삭제에 빠르기 때문에 예상할 수 없는 인덱스에서 데이터를 제거하거나 추가해야 하는 해당 문제에는 적합하지 못한 자료구조였다.

3. LinkedList

링크드리스트는 비순차적인 데이터 추가 및 삭제에 빠르다.