Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[구현] 삼각 달팽이 - 프로그래머스 본문

프로그래밍

[구현] 삼각 달팽이 - 프로그래머스

yesungcho 2022. 2. 4. 13:37

https://programmers.co.kr/learn/courses/30/lessons/68645

 

코딩테스트 연습 - 삼각 달팽이

5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

programmers.co.kr

 

전에 월간 코드 챌린지를 참여했을 땐 시간 부족으로 풀지 못했던 문제인데

기회가 생겨 다시 풀게 되었다. 

 

당시는 규칙을 찾으려고 발버둥을 쳤던 문제였는데 단순 구현 문제였다. 

 

논리는 단순하다.

 

우선 다음과 같이 0을 담고 있는 빈 삼각형을 만들어준다.

다음으로 

[1] 첫 번째 요소를 채워주는 반복문을 구축한다.

[2] 다음으로 마지막 element요소를 채워주는 반복문을 구축한다.

마지막 element를 채운 뒤에는 마지막 요소를 제거한다. 

 

[3] 끝 열 중 0이 아닌 부분을 채운다. 

[4] 다음 단계로 넘어가면서 마찬가지의 단계를 수행해준다. idx를 통해 control 한다. 

 

총 0이 없을 때까지 수행한다. 

 

이러한 논리를 구현하는 코드를 작성하였는데 다만 복잡도가 꽤 커서 시간 복잡도가 걸릴지 걱정이었지만 다행히 통과하였다. 

 

def solution(n):
    triangle = []
    for i in range(1,n+1) :
        triangle.append([0]*i)

    ## 프로그램 시작
    idx = 0
    level = 0
    accum = 0
    total_result = []; flag = False

    def find_index(ls) :
        result = 0
        for i in range(len(ls)-1, -1, -1) :
            if ls[i] == 0 :
                result = i
                break
        return result
    while True :
        ## 초반 거 채우기
        for i in range(idx, len(triangle)) :
            if triangle[i][idx] == 0 :
                flag = True
                accum += 1
                triangle[i][idx] = accum
        if not flag :
            break
        ## 마지막 행 채우기
        for j in range(idx+1, len(triangle)) :
            if triangle[len(triangle)-1][j] == 0 :
                accum += 1
                triangle[len(triangle)-1][j] = accum
        ## 끝에 거 채우기
        total_result.append(triangle.pop())
        for k in range(len(triangle)-1, -1, -1) :
            ii = find_index(triangle[k])
            if triangle[k][ii] == 0 :
                accum += 1
                triangle[k][ii] = accum

        idx += 1
        flag = False

    for _ in range(len(triangle)) :
        total_result.append(triangle.pop())

    Final_result = []
    for ele in range(len(total_result)-1, -1, -1) :
        Final_result.extend(total_result[ele])
    return Final_result

 

'프로그래밍' 카테고리의 다른 글

[DP] 1, 2, 3 더하기 4 - 백준  (0) 2022.02.04
[DP] 퇴사2 - 백준  (0) 2022.02.04
[Greedy] 동전0 - 백준  (0) 2022.02.03
[DP] 평범한 배낭 - 백준  (0) 2022.02.03
[DP] 설탕 배달 - 백준  (0) 2022.02.02