[프로그래머스] 09/30 (1/3)

[파일명 정렬]-[2018 KAKAO BLIND RECRUITMENT]

My answer

def solution(s):
    answer=[]
    tmp=[[ 0 for i in range(4)] for j in s]
    for index,i in enumerate(s):
        for j in range(len(i)):
            if(i[j].isdigit()==1):
                tmp[index][0]=i[:j].upper()
                for k in range(j,len(i)):
                    tmp[index][3]=index
                    if(k==len(i)-1):
                        tmp[index][1]=int(i[j:])
                        break
                    if(k==j+5 or i[k].isdigit()==0):
                        tmp[index][1]=int(i[j:k])
                        tmp[index][2]=i[k:]
                        break
                break
    tmp= [s[i[3]] for i in sorted(tmp,key=lambda x:(x[0],x[1],x[3]))]
        
    return tmp

Another answer

def solution(files): 
	tmp = [] 
    for idx1,i in enumerate(files): 
    head = num = tail= '' 
    for idx2,j in enumerate(i): 
    	if j>='0' and j<='9': 
        	if len(num)>=5: break 
            num+=j 
        elif len(num)==0: 
        head+=j 
        else: break 
     tail+=i[idx2:] 
     tmp.append([head.lower(),int(num),tail,idx1]) 
return [files[tp[3]] for tp in sorted(tmp,key=lambda x:(x[0],x[1],x[3]))]
--------------------------------------------------------------------------------
import re

def solution(files):

    def key_function(fn):
        head,number,tail = re.match(r'([a-z-. ]+)(\d{,5})(.*)',fn).groups()
        return [head,int(number)]

    return sorted(files, key = lambda x: key_function(x.lower()))

[내 코드] 

우선 첫문자가 나오기 전까지를 head로 지정한다. 이후 5자가 넘어가거나 숫자가 아닌 문자가 나오거나 파일명이 종료될 경우를 numbers에 집어넣고, 나머지는 tail에 집어넣는다. 이 때 head은 전부 대문자로 통일, numbers는 001등의 0을 없애고 숫자를 비교하기 위해 int형으로 바꿔서 넣어준다. 마지막으로 조건에 맞게 정렬한뒤 중간에 우리가 원래 파일명을 쪼개고 수정했었으므로 정렬된 인덱스만 가져와서 원본파일명을 인덱스 순서에 맞게 가져온다.

[두번째 코드]

numbers배열을 만들고 이 배열에 숫자가 들어오기 전까지는 전부 문자로 넣는다. 이후 5글자가 넘거나 문자가 나올때까지 number에 넣고 나머지는 tails에 넣는다. 다음은 나와 동일하다. 하지만 시간복잡도는 훨씬 적게걸린다.

마지막코드는 정규표현식을 이용한 풀이이다. 대부분의 짧은 풀이들은 정규표현식을 이용한 것 같다.

 

내가 문제를 거의 다 풀고 헤맸던 이유는 tails가 비어있을 경우를 생각안하고 tmp에 할당을 해준것이 문제였다. tails가 비어있을경우에 numbers나 tails index 모두에 값이 안들어가게 코드를 짰었다. 따라서 중간에 조건문을 한번 더 넣어서 해결해줬다.

 

[[3차] 압축]-[2018 KAKAO BLIND RECRUITMENT]

My answer

def solution(msg):
    answer=[]
    # for i in range(1,27):
        # dic[chr(ord('A')+(i-1))]=i  
    dic = {chr(e + 64): e for e in range(1, 27)}
    while(msg):
        for i in range(1,len(msg)+1):
            if(msg[:i] in dic):
                tmp=msg[:i]
            else:
                answer.append(dic[tmp])
                tmp=[]
                dic[msg[:i]]=len(dic)+1
                msg=msg[i-1:]
                break 
        # 반복이 끝났는데, tmp에 문자가 남아있을 때
        if(tmp):
            answer.append(dic[tmp])
            msg=[]
    return answer

Another answer

def solution(msg):
    answer = [] 
    s = "" 
    dic = {chr(e + 64): e for e in range(1, 27)}
    for m in msg: 
        s+=m 
        if s not in dic: 
            answer.append(dic[s[:-1]]) 
            dic[s] = len(dic)+1
            s=s[-1] 
    answer.append(dic[s])
    return answer

chr()함수는 아스키코드값을 문자로 바꿔주는 함수고, ord()함수는 문자를 아스키코드 값으로 바꾸는 것이다. 난 맨처음에 ord함수로 A의 아스키코드값을 구해주고 계산했는데, A는 64란다. 내 코드보다 아래코드가 시간복잡도가 O(n)이어서 더 효율적으로 보인다

[가장 큰 정사각형 찾기]

My answer-시간초과

def solution(board):
    maxs=[0]
    for index,i in enumerate(board):
        for j in range(len(i)):
            tmp=[]
            if(i[j]==1):
                for k in range(j,len(i)):
                    # 0을 만나서 끝났을 때
                    if(i[k]==0):
                        breaka
                # 0을 안만나고 열의 끝에 가서 끝났을 때
                if(i[k]==1): k+=1
                # 세로 길이가 board의 크기를 넘어설 때
                if(index+k-j<=len(board)):
                    # tmp에 임시 보드를 넣어둠 
                    tmp=[l[j:k] for l in board[index:index+k-j]]
                    # tmp에 0이 하나라도 있으면 안됨
                    for t in tmp:
                        if 0 in t: break
                    # 최대 넓이 구하기 
                    else:
                        maxs.append((k-j)**2)      
    return max(maxs)

Another answer

def solution(board):
    answer = 0
    dp=[i for i in board]
    
    if(len(board)==1 and len(board[0])==1):
        if(board[0][0]==0): return 0
        else: return 1
                
    for i in range(1,len(board)):
        for j in range(1,len(board[0])):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
            answer = max(dp[i][j],answer)

    return answer**2

우선 내 코드는 테스트케이스는 모두 맞았으나 시간초과가 떴다. 5중 for문이니 그럴만하다. 아래 코드는 동적 프로그래밍(Dynamic Programming) 알고리즘을 이용한 코드이다. 동적프로그래밍 자체는 큰 문제를 작은 문제로 나누어 푸는 알고리즘. 큰 문제를 작은 문제들로 분할하여 그것을 이용해 큰 문제를 해결하는 방법이다. 이걸 실제로 적용하는 방법은 모든 작은 문제들은 한 번만 풀어야 하므로 정답을 구한 작은 문제를 어딘가에 메모해 놓고, 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용하는 것이다.. 그러나 작은 문제들에서 반복이 일어나고, 같은 문제는 구할 때마다 정답이 같다는 조건하에서만 적용시킬 수 있다.

[동적프로그래밍]

 https://galid1.tistory.com/507