[LeetCode] 816. Ambiguous Coordinates

문제

816. Ambiguous Coordinates · Medium

"(1, 3)", "(2, 0.5)" 같은 2차원 좌표에서 쉼표, 소수점, 공백을 전부 지워 "(13)", "(205)" 같은 문자열 s가 남았습니다. 원래 좌표로 가능했던 것을 모두 구하는 문제입니다.

조건은 두 가지입니다.

• 원래 숫자에는 불필요한 0이 없습니다. 00, 0.0, 1.0, 001, 00.01 같은 숫자는 나올 수 없습니다.
• 소수점 앞에는 반드시 숫자가 하나 이상 있습니다. .1 같은 숫자는 나올 수 없습니다.

Input:  s = "(0123)"
Output: ["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"]

접근

s의 길이가 최대 12이므로 괄호를 빼면 숫자는 최대 10개입니다. 경우의 수가 작아서 전부 만들어 보면 됩니다.

1. 숫자 문자열을 x좌표와 y좌표 두 조각으로 나누는 위치를 모두 시도합니다.
2. 각 조각에 대해 소수점을 찍을 위치를 모두 시도해서, 유효한 숫자만 모읍니다.
3. x 후보와 y 후보를 조합합니다.

핵심은 2번의 유효성 검사입니다. 숫자를 정수부와 소수부로 나눠서 보면 규칙이 단순해집니다.

부분	규칙	걸러지는 예
정수부	"0" 자체는 되지만, 길이가 2 이상이면 0으로 시작하면 안 됨	00, 01, 012
소수부	0으로 끝나면 안 됨	1.0, 0.10

풀이

function ambiguousCoordinates(s: string): string[] {
  const digit = s.slice(1, -1);

  const getNums = (str: string) => {
    const nums: string[] = [];

    for (let i = 1; i <= str.length; i++) {
      const int = str.slice(0, i);
      const dec = str.slice(i);

      if (int.length > 1 && int.startsWith('0')) continue;
      if (dec.endsWith('0')) continue;

      nums.push(dec ? `${int}.${dec}` : int);
    }

    return nums;
  };

  const coordinates: string[] = [];
  for (let i = 1; i < digit.length; i++) {
    for (const x of getNums(digit.slice(0, i))) {
      for (const y of getNums(digit.slice(i))) {
        coordinates.push(`(${x}, ${y})`);
      }
    }
  }

  return coordinates;
}

i === str.length일 때는 소수부가 빈 문자열이 되어 소수점 없는 정수 하나로 처리됩니다. 빈 문자열은 endsWith('0')에 걸리지 않으므로 따로 분기할 필요가 없습니다.

삽질 포인트

처음에는 정수부 검사를 이렇게 썼습니다.

if (int.startsWith('0')) continue;

01, 00을 거르려던 의도였지만, 이렇게 쓰면 "0" 자체도 걸러집니다. 그 결과 0, 0.1, 0.011처럼 0으로 시작하는 정상 숫자가 하나도 만들어지지 않고, "(0123)"을 넣으면 빈 배열이 나옵니다.

"0으로 시작하면 안 된다"가 아니라 "두 자리 이상인데 0으로 시작하면 안 된다"가 정확한 조건입니다.

if (int.length > 1 && int.startsWith('0')) continue;

복잡도

숫자 개수를 n이라고 하면 다음과 같습니다.

• 시간: O(n⁴). 좌표를 나누는 위치 n개, 조각마다 소수점 위치 n개, 문자열 생성에 n이 듭니다.
• 공간: O(n³). 결과 문자열의 총 길이입니다.

n이 최대 10이라 충분히 통과합니다.