[Leet Code] Ambiguous Coordinates

기면지·2021년 5월 14일

Leet Code algorithm

LeetCode

목록 보기

6/20

안녕하세요!
오늘은 5월 2주차 6번째 알고리즘인 Ambiguous Coordinates 풀이를 적어보겠습니다.

문제

요약
주어진 문자열 s 로 만들 수 있는 유효한 정수 또는 실수 쌍을 return하는 문제입니다.

처음 시도한 방법

자료형을 사용할까, 배열을 사용할까 고민했습니다.

s 문자열을 배열로 split 해서 유효한 글자만큼의 index를 구해서 문자열을 만드는 방법을 했습니다.

하지만 제대로 풀리지 않는 것을 보고 이 방법이 틀렸다는 것을 알게되었습니다.

두번째로 시도한 방법

처음에는 s 문자열을 처음부터 하나씩 분리했는데, 그렇게 하는 것이 아닌 for문을 순회하면서 1~length-1 사이의 범위에서 잘라서 임의의 배열을 만들었습니다.
그 후에 배열의 각 숫자가 유효한지 확인하고, answer 리스트에 추가하는 방식으로 진행했습니다.

로직을 생각해낸 시간도 오래걸렸고, 코드를 짜는 것도 오래걸려서 약 2시간정도 걸려서 Accept를 받았습니다.
이제부터 로직을 조금 더 자세하게 설명하겠습니다.

코드 설명

private List<String> answer, firstStrings;

Solution 클래스의 멤버 변수로 답을 저장할 answer 리스트와 answer 의 처음에 등장할 문자열들의 모음인 firstStrings 를 선언합니다.

answer = new ArrayList<>();

함수 내에서 answer 리스트를 초기화해줍니다.

for (int i = 2; i < s.length() - 1; i++) {
    String[] strings = {s.substring(1, i), s.substring(i, s.length() - 1)};
    firstStrings = new ArrayList<>();
    for (int j = 0; j < 2; j++) {
        isValid(strings[j], j);
    }
}

for문을 순회하면서 input 으로 받은 문자열에서 1~i, i~length-1 범위의 숫자들을 분리해서 strings 배열에 저장합니다.
그리고 해당 배열에 있는 숫자 중에서 유효한 숫자 조합을 저장하기 위해 firstStrings 리스트를 초기화합니다.

그리고 다음 for문은 strings 배열에 저장된 first , second 숫자들의 유효성을 검사하고 유효하다면 answer 또는 firstStrings 리스트에 저장하기 위한 과정입니다.

예를 들어서 s 가 (08345) 라면 for-i 문을 순회하면서 strings 는 { "0", "8345 } - { "08", "345" } 등이 될 것입니다.
그 후에 for-j 문에서는 strings[0]("0") , strings[1]("08") 의 유효성을 검사해서 리스트에 저장합니다.

private void isValid(String string, int index) {
    if (string.length() == 1 || string.charAt(0) != '0') addToList(string, index);
    if (string.length() > 1 && string.charAt(string.length() - 1) != '0')
        addToList(string.substring(0, 1) + "." + string.substring(1), index);
    if (string.length() > 2 && string.charAt(0) != '0' && string.charAt(string.length() - 1) != '0') {
        for (int i = 2; i < string.length(); i++) {
            addToList(string.substring(0, i) + "." + string.substring(i), index);
        }
    }
}

isValid 함수에서는 숫자들의 문자열에서 가능한 정수, 실수 조합을 찾습니다.
유효한 정수, 실수 조합에는 3가지 조건이 있습니다.

0으로 시작하는 1자리 이상의 수는 정수가 아니어야 한다.
(ex. 01, 001 등은 불가능)

가장 마지막 숫자가 0인 1자리 이상의 수는 실수가 아니어야 한다.
(ex. 1.230, 3.240 등은 불가능)

0이 양 끝에 등장하지 않으면 항상 유효하다.

이 조건의 순서대로 if 문을 설정해줍니다.
else if 문으로 하지 않은 이유는, 정수도 가능하고 실수도 가능한 경우들도 있기 때문입니다.
(예를 들어서, 108 의 경우 가능한 조합은 108, 1.08, 10.8 가 됩니다.)

private void addToList(String string, int index) {
    if (index > 0) {
        for (String s: firstStrings) {
            answer.add("(" + s + ", " + string + ")");
        }
    } else {
        firstStrings.add(string);
    }
}

그 후에 index 가 1일 경우에는 answer 에 더해주고, index 가 0일 경우에는 firstStrings 에 추가해줍니다.

index 는 쉽게 말해서 배열의 인덱스입니다.
index = 1 이라면 두번째 숫자의 유효성 검사까지 끝났다는 의미이므로 answer 리스트에 문자열을 만들어 추가합니다.
index = 0 이라면 첫번째 숫자의 유효성 검사를 끝냈다는 의미이므로 첫번째 문자열들이 저장되는 firstStrings 리스트에 해당 문자를 추가합니다.

전체 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<String> answer, firstStrings;

    public List<String> ambiguousCoordinates(String s) {
        answer = new ArrayList<>();

        for (int i = 2; i < s.length() - 1; i++) {
            String[] strings = {s.substring(1, i), s.substring(i, s.length() - 1)};
            firstStrings = new ArrayList<>();
            for (int j = 0; j < 2; j++) {
                isValid(strings[j], j);
            }
        }

        return answer;
    }

    private void isValid(String string, int index) {
        if (string.length() == 1 || string.charAt(0) != '0') addToList(string, index);
        if (string.length() > 1 && string.charAt(string.length() - 1) != '0')
            addToList(string.substring(0, 1) + "." + string.substring(1), index);
        if (string.length() > 2 && string.charAt(0) != '0' && string.charAt(string.length() - 1) != '0') {
            for (int i = 2; i < string.length(); i++) {
                addToList(string.substring(0, i) + "." + string.substring(i), index);
            }
        }
    }

    private void addToList(String string, int index) {
        if (index > 0) {
            for (String s: firstStrings) {
                answer.add("(" + s + ", " + string + ")");
            }
        } else {
            firstStrings.add(string);
        }
    }
}