728x90

https://school.programmers.co.kr/learn/courses/30/lessons/178870#

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

처음에는 이중 for문으로 풀었다. 테스트 코드는 통과하였으나 

시간 초과가 났다. 

 

어떻게 애들을 더해서 k를 비교할까 고민하다가 

처음에 이중for문으로 생각한 방법은 이렇게 시작 인덱스를 줄여서 더해가다가 k 값과 비교해서 해야지~였다.

def solution(sequence, k):
    answer = []
    min_difference = float('inf')
    selected_numbers =None
    for i in range(len(sequence)):
        total_sum =0
        for j in range(i, len(sequence)):
            total_sum+= sequence[j]
            if total_sum ==k: 
                if (abs(j-i) < min_difference):
                    min_difference = abs(j-i)
                    selected_numbers = (i,j)
                    break

    return selected_numbers

 

문제는 조회하는 배열의 최대 길이가

 

5 ≤ sequence의 길이 ≤ 1,000,000

 

였기에 이중포문을 하면 이차시간으로 계산되어 제곱이 되어 초과된다. 

 

시간복잡도 참고)

출처:&nbsp;https://jeleedev.tistory.com/70

그다음에 for문을 사용하지 않고 어떻게 맨앞자리 인덱스를 줄일지 고민했다. 

여기서 오래 막혔다. 

시간초과 없애려고 이중포문 없애고 해봤는데

i부터 j까지 계속 더해지는거 i를 조작못했다.

 

2차 시도 (사실 2차는 아니긴한데..)

    index = 0
    start = 1
    
    for i in range(start, len(sequence)):
        sequence[index] += sequence[i]
        print("sequence[index]:",sequence[index])
        if i == len(sequence)-1:
            index += 1
            start +=1

    return selected_numbers

이 코드는 그저 처음부터 끝까지 더하기만 한다. 

 

 

처음에 포인터로 시작과 끝을 가리키는 방법을 쓰려했는데 for문으로 어차피 다 조회하니까 시작만 

가리키면 되겠다고 생각해서 반복문에 집착한 것이 나의 실수였다..결국 한참 헤매다가 답지를 봤다.

 

최종 코드 

def solution(sequence, k):
    answer =[]
    start = 0
    end =0
    min = 1000000000
    total = sequence[0]
    while (start <= end < len(sequence)):
        if (total == k):
        
            if min > end- start+1:
                min = end - start+1
                answer =[start, end]
            total -= sequence[start]
            start += 1
        elif (total < k):
            end+= 1
            if end< len(sequence):
                total += sequence[end]  
        elif (total > k):
            total -= sequence[start]
            start += 1
          
    return answer

1.  start end 시작과 끝 두 포인터의 관계 설정이 중요

start <= end

시작포인터와 끝포인터는 같은 곳에서 시작하고 만나서 같을 수는 있어도 넘어서는 안된다. 

나는 계속 전체 배열의 길이만 넘지 말라고 맞춰서 리스트에서 벗어나는 에러가 발생했다. 

 

2. 전체 배열의 값을 더하는 total을 어떻게 처리할지

total 정의할 때 sequence[0] 첫번째 값을 할당하고 시작하면 된다. 

total은 구하고자 하는 k값을 기준으로 나뉜다. 

 

<바로 생각하기 힘들었던 부분>

1. total == k일 때 시작과 끝 두사이 거리가 최소인 값을 찾고 나서 

배열 끝까지 다시 시작과 끝을 움직여야 하는데 

end를 움직여도 될거라 생각했다. 

그렇게 한 결과 end값이 먼저 배열범위보다 커져버려서 테스트 통과를 못했다. 

전체에서 start인덱스의 값을 빼주고 start인덱스를 옮기는 것으로 수정했다. 

 

2. while범위에서 배열의 범위만큼 돌라고 했으니 문제 없을거라 생각했지만

end를 하나씩 추가하고  그 값을 sequence의 인덱스로 넣기 위해 조건을 안 걸면 저렇게 에러가 났다. 

 

 

 

결론 반복문에 그만 집착하고 효율적인 풀이를 생각해보자

컴퓨터가 우리 뇌구조랑 비슷하겠다는 생각을 했다. 생각한게 맞을 수도 있으니 포기말고 구현해봐라

 

728x90

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

프로그래머스 Lv.3 최고의 집합  (1) 2023.09.07
728x90

정렬은 주어진 데이터를 일정하게 재배열하는 것이다. 

데이터를 재배열하는 정렬 종류는 다양하다

 

 

1) 버블 정렬

비교해서 큰 데이터를 오른쪽으로 보내서 재배열하는 방법

전체 배열를 모두 조회해서 데이터를 비교한다. -> 반복 : 큰데이터에는 효율적이지 못한 알고리즘이다.

2) 선택 정렬

가장 작은 최솟값을 골라서 맨앞에 보내는 식으로 재배열한다. 

가장 작은 최솟값 고르려면 전체 배열을 모두 조회해야한다. -> 반복 : 마찬가지로 큰데이터에는 효율적이지 못한 알고리즘

 

이처럼 정렬 알고리즘의 성능을 평가하는데에는 주로 '시간복잡도' 개념이 쓰인다. 

시간복잡도란 알고리즘 수행시간이 입력한 값에 따라 얼마나 증가하는지를 나타내는 지표이다. 

출처 : https://junghyun100.github.io/Time-Complexity/
출처: https://wikidocs.net/34790

 

 

 

3) 힙정렬

힙 - 더미, 데이터를 특정한 형태로 쌓아올리는 것을 의미. 

노드간의 관계를 나타내는 이진트리구조에서 힙 구조가 나타난다. 

기본 리스트를 힙정렬로 만들려면 일단 최대 혹은 최소값을 가지는 루트를 설정하고 

루트를 기준으로 값(노드)를 정렬한다. 

 

 

4) 삽입정렬

삽입정렬은 버블정렬과 비슷해보이지만 

모든 데이터를 조회하며 비교하는 버블정렬과 달리

이미 정렬된 부분과 정렬되지 않은 부분을 유지하며

정렬된 부분에는 요소를 삽입하여 배열하므로 버블 정렬보다 효율적인 정렬이다.

 

5) 퀵 정렬

기준을 세워 분할한다(보통 중간값을 기준으로 함).작은 요소는 왼쪽, 큰 요소는 오른쪽에 위치한다.

분할하고 배열하고를 재귀적으로 반복 후 합쳐서 정렬.

 

6)병합 정렬

리스트를 반으로 나눈다. 리스트 크기가 1이하가 될때까지 반으로 나눈다.

나눈 작은 리스트를 정렬한다. 나눴던 리스트의 가장 작은 요소를 비교해서 

작은 순서대로 병합한다. 

입력크기와 상관없이 일정한 시간복잡도를 가진다. 

 

 

 

 

 

 

728x90

+ Recent posts