99클럽 코테 스터디 40일차 TIL + Greedy(Optimal Partition of String)

오늘의 과제

리트코드 medium으로 분류된 Optimal Partition of String 입니다.

 

이번 유형은 그리디 입니다.

문제

https://leetcode.com/problems/optimal-partition-of-string/description/

 

먼저 문제 요구사항 요약입니다.

 

문자열이 주어질 때 각 문자가 하나의 파티션에 최대 한 번씩만 등장하도록 파티션을 나눈 후 파티션의 개수를 반환하는 문제입니다.

 

먼저 살펴보아야 할 부분은 각 파티션에 문자가 중복되지 않게 어떻게 나누는가? 입니다. 문제의 유형이 그리디인만큼 매번 최선의 선택을 해야 하는데 제약 조건인 "문자가 중복되지 않는다"에 포커스를 맞추면 매우 쉽게 풀 수 있습니다.

 

문자열이 주어지면 contains를 통해 중복 여부를 확인하고 만약 중복된 문자가 들어왔을 때에 파티션을 나눠주면 중복되지 않게 문자열을 나눌 수 있습니다.

 

코드입니다.

import java.util.*;

class Solution {
     public int partitionString(String s) {
        ArrayList<Character> seen = new ArrayList<>();
        int partitions = 0;

        for (char c : s.toCharArray()) {
            if (seen.contains(c)) {
                partitions++;  // 새 파티션 시작
                seen.clear();  // 이전 파티션의 문자 기록 삭제
            }
            seen.add(c);  // 현재 파티션에 문자 추가
        }

        // 마지막 파티션을 포함하여 반환
        return partitions + 1;
    }
}

 

 

배운 점

처음 시도는 "중복"에 집중하여 HashSet을 이용하여 풀었으나 어차피 중복을 확인할거고, 중복이 있다면 리스트를 비워줄 것이기 때문에 일반 ArrayList로 변경하여 풀었습니다. 다른 사람의 풀이를 보니 26개의 알파벳 배열을 선언한 후 자기 자신이 나올 때 배열에 인덱스를 기록하고, 이후에 또 같은 문자가 나왔을 때 파티션의 카운트를 늘리는 방식으로 사용하는데 이 방식엔 List의 add와 clear 연산이 없으니 확실히 시간 효율이 더 좋게 나오는것을 확인했습니다.

 

문제의 정답을 구했어도 다양한 풀이가 있으니 개발시에 선택지를 늘리기 위해서라도 다른 사람의 코드를 보는 것에도 시간을 투자해야 할 것 같습니다.

 

 

오늘의 한줄평

선택지가 많아야 다양한 상황에서의 유연한 대처가 가능하다.