763-kir3i.md

763. Partition Labels

Solution

• 시간복잡도: O(N)

• 알고리즘

  라인스위핑

• 풀이설명

  입력으로 주어진 문자열 S를 총 두 번 스캔하여 해결합니다.

  1. 첫번째 스캔에서는 각 알파벳의 왼쪽 끝과 오른쪽 끝의 인덱스 값을 저장합니다. (le, re) 이렇게 저장해두면 각 알파벳의 분포는 선분으로 여길 수 있고, 우리가 찾는 partition은 겹치는 선분이 하나일 때만 쪼갤 수 있습니다.
  2. 두번째 스캔에서는 각 지점에서 겹치는 선분의 수를 cnt에서 셉니다. 스캔지점이 왼쪽 끝(le)에 해당할 때는 cnt에 1을 누적하고 오른쪽 끝(re)에 해당할 때는 cnt에서 1을 뺍니다.
  3. 스캔하면서 겹치는 선분의 수(cnt)가 하나일 때 sp에 새로운 partition의 시작점을 저장합니다. 만약 겹치는 선분의 수가 하나이면서 스캔지점이 오른쪽 끝 지점이라면 sp를 이용하여 partition의 길이를 구해서 ans에 추가합니다.
  4. 두번째 스캔까지 마치면 ans에는 각 partition의 길이가 저장됩니다.

• 소스코드

  • C++

  #define ORD(C) C-97
  
  class Solution {
  public:
  	int le[26];
  	int re[26];
  	vector<int> ans;
  	vector<int> partitionLabels(string S) {
  		memset(le, -1, sizeof(le));
  		memset(re, -1, sizeof(re));
  		int sz = S.size();
          
  		// First Scan
  		for (int i = 0; i < sz; i++) {
  			if (le[ORD(S[i])] == -1)
  				le[ORD(S[i])] = i;
  			re[ORD(S[i])] = i;
  		}
          
  		// Second Scan
  		int cnt = 0, sp = 0;
  		for (int i = 0; i < sz; i++) {
  			if (!cnt)	sp = i;
  			if (le[ORD(S[i])] == i)	cnt += 1;
  			if (cnt == 1 && re[ORD(S[i])] == i)
  				ans.push_back(i - sp + 1);
  			if (re[ORD(S[i])] == i)	cnt -= 1;
  		}
  
  		return ans;
  	}
  };

  • Python

  class Solution:
      def partitionLabels(self, S):
          S = [ord(c) - 97 for c in S]
          le = [None] * 26
          re = [None] * 26
  
          # First Scan
          for i, x in enumerate(S):
              if le[x] == None:
                  le[x] = i
              re[x] = i
  
          # Second Scan
          ans = []
          cnt = 0
          sp = 0
          for i, x in enumerate(S):
              if cnt == 0:
                  sp = i
              if le[x] == i:
                  cnt += 1
              if cnt == 1 and re[x] == i:
                  ans.append(i-sp+1)
              if re[x] == i:
                  cnt -= 1
  
          return ans