結果
問題 | No.205 マージして辞書順最小 |
ユーザー | S. Miya |
提出日時 | 2016-09-15 18:30:48 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 31 ms / 5,000 ms |
コード長 | 1,326 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 10,864 KB |
実行使用メモリ | 9,388 KB |
最終ジャッジ日時 | 2023-08-10 20:40:15 |
合計ジャッジ時間 | 2,279 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
9,228 KB |
testcase_01 | AC | 26 ms
9,168 KB |
testcase_02 | AC | 28 ms
9,168 KB |
testcase_03 | AC | 27 ms
9,308 KB |
testcase_04 | AC | 27 ms
9,340 KB |
testcase_05 | AC | 27 ms
9,216 KB |
testcase_06 | AC | 24 ms
9,220 KB |
testcase_07 | AC | 30 ms
9,256 KB |
testcase_08 | AC | 31 ms
9,236 KB |
testcase_09 | AC | 30 ms
9,228 KB |
testcase_10 | AC | 30 ms
9,332 KB |
testcase_11 | AC | 31 ms
9,388 KB |
testcase_12 | AC | 30 ms
9,232 KB |
testcase_13 | AC | 29 ms
9,172 KB |
testcase_14 | AC | 26 ms
9,296 KB |
testcase_15 | AC | 25 ms
9,240 KB |
testcase_16 | AC | 25 ms
9,320 KB |
testcase_17 | AC | 25 ms
9,272 KB |
testcase_18 | AC | 26 ms
9,368 KB |
ソースコード
import string class StringMerge: def __init__(self): self.atoi = lambda a: ord(a)-ord('a') # alphabet to index self.endchar = chr(ord('z')+1) self.strmat = [[] for _ in range(len(string.ascii_lowercase))] def add(self, word): self._add(word+self.endchar) def _add(self, word): index = self.atoi(word[0]) self.strmat[index].append(word) def merge(self): cur_top = 0 # init index = 'a'(=0) buff = [] while cur_top < len(self.strmat): if len(self.strmat[cur_top]) > 0: self.strmat[cur_top].sort() # sorted by char e.g. fae,fab->x fab,fae->o tar = self.strmat[cur_top].pop(0) buff.append(tar[0]) if len(tar) >= 3: # !! include endchar # rest sub string, add self._add(tar[1:]) # update top index or_top = self.atoi(tar[1]) if cur_top > or_top: cur_top = or_top else: # miss index, walk next cur_top += 1 return ''.join(buff) if __name__ == '__main__': n = int(input()) sm = StringMerge() for _ in range(n): line = input() sm.add(line) print(sm.merge())