HackerRank [Strings] Two Characters /알고리즘 해커랭크

---

문제 주소 : https://www.hackerrank.com/challenges/two-characters/problem

난이도 : easy
성공률 : 76.74%

 

문제 : 2개의 문자만 남기고 모두 지웠을 경우 가장 긴 길이 값을 가지는 문자열을 만들어라 그리고 그 문자열의 길이를 리턴하라
단 동일한 문자가 연속으로 위치하면 안된다 만들 수 없을 경우 0 리턴

 

풀이

1. 문자 종류별로 별도 리스트를 만든다 (lCharList)
2. 리스트에서 2개씩 뽑아서 문자열을 만든다 만드는 도중 연속된 문자이면 다음으로 넘어간다
3. 문자열이 완성 됐을 경우 길이를 구해서 최댓값과 비교한다
4. 모든 반복(2개의 문자로 문자열 만들기)이 끝난 후 최종 맥스 길이를 리턴한다

답안

#!/bin/python3

import math
import os
import random
import re
import sys

# 사용안함 각 문자가 몇개씩 있나 확인해보는 용도
def checkCharCnt(s):

    Dic = {}
    while(len(s)!=0):
        cTemp = s[0]
        Dic[cTemp] = s.count(cTemp)
        s = s.replace(cTemp, '')

    return Dic

#사용안함 연속된 문자 제거 기능, 전처리로 하면 속도개선이 될까 싶어 넣었는데 오히려 느려짐 타임아웃발생
def DelContinueChar(s):
    bEnd = True

    while(bEnd):
        nLen = len(s)
        for i in range(0, nLen-1):
            if s[i] == s[i+1]:
                s = s.replace(s[i], '')
                break
            elif i == nLen-2:
                bEnd = False
                break
    return s          
 

def alternate(s):

    # print(checkCharCnt(s)) 

    # s = DelContinueChar(s) 

    lCharlist = []
    sTemp = s
    nMaxCnt = 0
    
    while(len(sTemp)!=0):
        lCharlist.append(sTemp[0])        
        sTemp = sTemp.replace(sTemp[0], '')    

    for i in range(0, len(lCharlist)):      
        for j in range(i+1, len(lCharlist)):
            c1 = lCharlist[i]
            c2 = lCharlist[j]
            sTwochar = ''
            for k in range(0, len(s)):                
                if s[k] == c1:
                    sTwochar += c1
                elif s[k] == c2:
                    sTwochar += c2
                
                nTwoLen = len(sTwochar)
                
                if nTwoLen > 1:
                    if sTwochar[nTwoLen-2] == sTwochar[nTwoLen-1]:
                        sTwochar = ''
                        break
                
            if len(sTwochar) > nMaxCnt:
                nMaxCnt = len(sTwochar)

    if nMaxCnt < 2:
        nMaxCnt = 0            
    return nMaxCnt         

    

if __name__ == '__main__':
    # fptr = open(os.environ['OUTPUT_PATH'], 'w')
    fptr = sys.stdout

    l = int(input().strip())

    s = input()

    result = alternate(s)

    fptr.write(str(result) + '\n')

    fptr.close()

 

느낀 점

easy문제는 시간 없을 때 머리 식힐 겸 잠깐 푸는 거 제외하곤 풀지 않으려 했으나
easy 치고 성공률이 떨어지길래 풀어봄

처음엔 연속된 문자는 먼저 지워놓고
각 문자의 수를 구한 뒤 높은 순서의 문자 두 개로 문자열을 구축, 연속된 데이터가 있나 확인 후 
연속된 데이터가 없으면 해당 값 리턴 종료, 실패 시 다음번 높은 두 개 더하기 식으로 풀려고 했으나
dictionary에 value 값으로 정렬을 시키고 그걸 또 반복시키고 하는 과정이 너무 번 거로 울 거 같아서 
위 풀이 방식으로 수정함

---