[코딩테스트/JAVA] 사다리 타기, 연산 수를 줄이는 아이디어

문제출처 : [인프런] 김태원님의 '자바 코딩테스트 - it 대기업 유제' 강의

강의에서 제공되는 문제이기 때문에, 문제 설명을 자세하게 하진 않겠습니다. 이번 블로깅에서는 저의 풀이 방법과 개선된 풀이 방법을 정리하도록 하겠습니다.

 

문제 설명

---

해당 문제의 제목은 '사다리 타기'입니다. 일상에서 무언가를 선정할 때 사용되는 게임입니다. 가령 '밥값 내기' 혹은 '선물 뽑기' 같은 경우에도 사다리 게임을 하곤 합니다. 즉, 이 문제는 A, B, C, D,, 등의 이용자가 있을 때, 사다리 이후의 결과를 출력하는 것입니다.

이때 세로줄의 수, 사다리 연결 정보를 입력값으로 받습니다. 

그림 예시

a : 가로를 갖는 라인으로, 동일선상의 가로줄을 포함합니다. (위 그림의 총 a의 수는 3입니다.)

b: 하나의 가로라인에 존재하는 가로줄입니다. (위 그림에서 1번째 가로라인의 b는 2, 2번째의 b도 2, 3번째의 b도 2입니다.)

제한조건

• 3 <= 세로줄 수 <= 25
• 사다리 가로라인의 개수(a) <= 1,000
• 하나의 가로라인에 있는 가로줄의 개수(b) <= 10

 

나의 아이디어

---

STEP 1) 각각의 세로줄의 가로줄 존재 여부 체크

가로줄 존재 여부 저장 배열

먼저 사다리의 가로줄 정보를 저장할 수 있는 배열을 이차원 배열을 만들었습니다. 열의 크기는 사다리의 세로줄 수입니다. 각 행의 정보는 가로라인 depth에 해당합니다. 

그림 예시

각 세로줄이 가로라인마다 가로줄을 갖고 있는지의 여부를 1, 0, -1로 저장합니다. 여기서 1은 우측(세로줄 번호가 높아지는 방향), -1은 좌측(세로줄 번호가 낮아지는 방향)으로 가로줄이 존재한다는 의미입니다. 위 그림예시에 대한 정보 저장하면 아래 배열처럼 저장됩니다.

STEP 2) 각각의 위치에서 출발했을 때 도착 위치 체크

세로줄 각각의 위치에서 출발한다고 가정하여, 세로줄을 순차적으로 탐색합니다. 

저는 출발했을 때의 위치를 초기 예상 도착 위치라고 생각했습니다. 즉, 가로줄이 없다고 가정하면 1번 출발자는 1번, 3번 출발자는 3번에 도착하는 것입니다. 하지만 가로줄 존재 여부에 따라 좌 혹은 우로 이동하게 됩니다. 따라서 위에서 저장했던 가로줄 정보 배열에서 탐색하는 세로줄의 가로줄 여부를 체크합니다.

예를 들어 현재 기준을 A라고 하겠습니다. 이 A가 1번에서 출발했다면,
i) 첫 번째 가로라인에 우측으로 가는 가로줄로 인해서 2번 세로줄로 갑니다.
ii) 2번의 두 번째 가로라인도 우측으로 이동하는 가로줄이 있기 때문에 3번 세로줄로 이동하게 됩니다.
iii) 마지막 3번 세로줄의 세 번째 가로라인은 0으로 가로줄이 없기 때문에 A는 3번에 도착하게 됩니다.

위와 같은 방식으로 전체 세로줄을 탐색하면, [D, B, A, C, E]와 같이 결과를 출력합니다.

💻 구현 코드 

public char[] solution(int n, int[][] ladder){
	char[] answer = new char[n];

	int depth = ladder.length; // 가로라인 수
	int[][] ladderLine = new int[n][depth]; // 가로줄 여부 배열, -1:좌, 1:우, 0:없음

	// 1. 가로줄 여부 정보 저장
	// 쌍방 저장
  	for (int i = 0; i < depth; i++) {
       for (int j = 0; j < ladder[i].length; j++) {
               int lineIdx = ladder[i][j];
               ladderLine[lineIdx-1][i] = 1; // 좌 -> 우
               ladderLine[lineIdx][i] = -1; // 우 -> 좌
             }
     }

     // 2. 사다리의 0번부터 체크
     for (int i = 0; i < n; i++) {
              int move = i; // 기준 지정
              for (int j = 0; j < depth; j++) {
                      move+=ladderLine[move][j]; // 현재 세로줄의 가로줄 정보를 기준에 더함
               }
               answer[move] = (char) (i+65); // 기준이 인덱스였기 때문에 문자로 저장하기 위해 A(65) 더함.
      }

      return answer;
}

사다리의 원리를 그대로 구현했는데요. 풀이를 보다시피, 그렇게 간략하지는 못합니다. 중요한 것은 시간복잡도 체크입니다.
1) 먼저 가로줄 여부를 저장하는 과정은 O(depth * ladder[i].length)입니다. depth는 최대 1,000개 ladder[i].length는 최대 10개입니다. 따라서 최대 연산은 10,000번 발생하겠습니다.
2) 두 번째 사다리 결과를 체크하는 과정에선 O(n*depth)입니다. n은 최대 25, depth는 최대 1,000이기 때문에 최대 25,000번의 연산이 발생하겠습니다.
다행히도 데이터의 양이 많지 않아서 큰 무리가 없습니다.

 

개선된 아이디어

---

위에서 설명한 방법과는 다른 색다른 아이디어가 있었습니다. 이 아이디어를 생각하지 못했다는 점에 아쉽고, 더 분발해야겠다고 생각했습니다.

저 같은 경우엔 결과를 도출하는 과정에서 세로줄을 순차적으로 탐색했다면, 이 방법은 전체를 한 번에 탐색한다고 볼 수 있습니다.

STEP 1) 가로줄이 없다고 가정하고 도착 정보 저장

그림 예시

위 그림에서 가로줄이 없었다면, [A, B, C, D, E]로 저장되었을 것입니다.

STEP 2) 입력받은 사다리 정보에 따라 도착 정보 내의 결과 위치 변경

그림 예시에 맞게 입력받는 사다리 정보는 이렇습니다. {{1,3}, {2,4}, {1,4}}

첫 번째 상위 배열의 각 인덱스는 가로 라인을 의미합니다. 각각의 가로라인에는 가로줄 위치가 적혀있습니다. 예를 들어서 {1,3}은 1번과 2번 세로줄 사이 그리고 3번과 4번 세로줄 사이에 가로줄이 있음을 의미합니다. 

예처럼 가로줄은 쌍방으로 존재합니다. 즉, 자리가 변경된다는 것을 알 수 있습니다.

가로줄 존재 위치를 체크합니다. 아래 설명은 위 그림의 세로줄 번호를 기준으로 합니다. 결과에는 -1을 적용한 인덱스라고 이해해 주시기 바랍니다.
i) 첫번째 정보는 1입니다. 1번과 2번 세로줄 사이에 가로줄이 존재하기 때문에, 미리 저장했던 도착정보 [A, B, C, D, E]에서 A와 B의 위치를 변경합니다. 이로 인해서 [B, A, C, D, E]가 됩니다.
ii) 두 번째는 3입니다. 3번과 4번인 C와 D의 위치를 변경합니다. 이로 인해서 [B, A, D, C, E]가 됩니다.
iii) 다음은 두번째 라인에서 2입니다. 2번과 3번의 위치를 변경하여 [B, D, A, C, E]가 됩니다.
iv) 다음은 4입니다. 4번과 5번의 위치를 변경하여 [B, D, A, E, C]가 됩니다.
v) 다음은 세 번째 라인에서 1입니다. [D, B, A, E, C]가 됩니다.
vi) 마지막으로 4입니다. [D, B, A, C, E]가 됩니다.

💻 구현 코드

    public char[] solution(int n, int[][] ladder){

        char[] answer = new char[n];
        // 1. 사다리 결과 초기화 (초기는 가로줄이 없다고 가정)
        for (int i = 0; i < n; i++) answer[i] += (char) (i+65);
        // 2. 가로줄의 depth를 0부터 순회
        for (int i = 0; i < ladder.length; i++) {
            // 3. 포함되는 세로줄의 자리교환
            for (int j = 0; j < ladder[i].length; j++) {
                    char temp = 0x00;
                    int line = ladder[i][j];
                    temp = answer[line];
                    answer[line] = answer[line-1];
                    answer[line-1] = temp;
                }
            }
            return answer;
        }
    }

해당 방법도 이중 반복문이 사용되었지만, 절차와 연산 수가 단축된 것을 확실히 알 수 있습니다. 또한 가로줄 존재 여부를 저장하는 배열을 별도로 만들지도 않았습니다. 메모리 효율도 개선되었습니다.