본문으로 건너뛰기

3403 - Find the Lexicographically Largest String From the Box I

info

풀이 키워드​

스포주의

문자열


풀이 코드​

info
  • 메모리: 52700 KB
  • 시간: 10 ms
class Solution {
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) return word; // corner case

        // lex order first, desc length order then
        final int n = word.length();
        final int mxLen = word.length() - (numFriends-1);

        Set<String> candSet = new TreeSet<>(Collections.reverseOrder());
        char mxChar = 'a';
        char[] wordArr = word.toCharArray();
        for (char ch : wordArr) mxChar = mxChar < ch ? ch : mxChar;

        for (int i = 0; i < n; ++i) {
            if (wordArr[i] != mxChar) continue;
            int j = Math.min(i+mxLen, n);
            candSet.add(word.substring(i, j));
        }
        
        return candSet.iterator().next();
    }
}

풀이 해설​

문자열을 친구 수만큼 빈 문자열이 되지 않도록 쪼개고,

그 문자열들 중에서 lexicographically largest한 문자열을 반환해야 하는 문제이다.

...길어서 lex라고 하겠다. lex largest string을 구하려면

  1. 사전순으로 뒤에 있는 것 우선
  2. 비교 가능한 범위에서 문자 구성이 모두 동일하면 길이가 긴 문자열 우선

이 2가지 기준으로 문자열을 필터링해야 한다.

이는 결국 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" 보다 "z" 가 더 lex largest 하다는 뜻이라서,

mxChar을 사전에 결정하고 해당 문자로 시작하는 인덱스에서만 후보군을 탐색하도록 그리디한 접근 방식을 떠올렸다.


자바의 TreeSet 사용해보기​

TreeSet은 RBT로 구현된, '자동정렬 unique 우선순위 큐' 같은 것이라고 생각하면 된다.

그냥 set이 필요한데 정렬도 필요하다 싶으면 TreeSet 쓰면 된다.

Set<String> candSet = new TreeSet<>(Collections.reverseOrder());

root에 lex largest한 문자열이 놓이도록 내림차순으로 생성했고, iterator().next()로 root에 접근했다.

TreeSet을 선택한 이유는 다음과 같다.

  • 후보 문자열의 중복을 제거하여 후보군 탐색시 복잡도를 최적화할 수 있기 때문
  • 자동 정렬 조아용 🤗💕

caution

corner case 조심 ❗​

public String answerString(String word, int numFriends) {
    if (numFriends == 1) return word; // corner case
틀리기 쉬운 반례
"gh"
1
답: "gh"

상단의 corner case가 별도로 처리되지 않는다면 어떻게 로직이 돌아갈지 분석해보자.

final int mxLen = word.length() - (numFriends-1);

char mxChar = 'a';
char[] wordArr = word.toCharArray();
for (char ch : wordArr) mxChar = mxChar < ch ? ch : mxChar;

별다른 처리가 없을 시 mxLen은 정상적으로 2로 설정되지만

그리디하게 가장 사전순으로 높은 알파벳을 추리는 과정에서 mxChar이 h로 설정되고

여기서 candSet엔 뭐가 들어갈까요?
for (int i = 0; i < n; ++i) {
    if (wordArr[i] != mxChar) continue;
    int j = Math.min(i+mxLen, n);
    candSet.add(word.substring(i, j));
}

결국 for문 순회에서 i = 0일때 g로 시작하는 문자열은 스킵되며

i = 1일때 h로 시작하는 문자열 중에서 j가 min(1+2, 2) = 2로 설정되어 "h"가 candSet에 들어가게 된다.

하지만 numFriends가 1이었기에 사실 "gh"는 쪼개질 수가 없었다 (!)

완전히 예외 케이스인 것이다.


✨ 다른 풀이 방법​

TreeSet을 사용하지 않고 compareTo 메소드를 사용하여 더 나은 문자열 발견시 그때그때 바꿔주면

수행시간이 5ms로 줄어든다. (대다수가 이렇게 풀이한듯?)

class Solution {
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) return word; // corner case

        // lex order first, desc length order then
        final int n = word.length();
        final int mxLen = word.length() - (numFriends-1);

        char mxChar = 'a';
        char[] wordArr = word.toCharArray();
        for (char ch : wordArr) mxChar = mxChar < ch ? ch : mxChar;

        String ans = "";
        for (int i = 0; i < n; ++i) {
            if (wordArr[i] != mxChar) continue;
            int j = Math.min(i+mxLen, n);
            String cand = word.substring(i, j);
            if (ans.compareTo(cand) < 0) ans = cand;
        }

        return ans;
    }
}

메모​

  • 코테 연습용으로도 괜춘한듯
  • corner case 말고는 전반적으로 무난한 난이도
    • 기본적으로 입력의 최소값은 좀 테스트해보십쇼 🙂...