[2023-01-24]

야무지게 설날 잘 쉬고..Start

flags 문제

 

정상마다 flag를 꽂고 싶어도 distance와 flag를 고려해서 꽂아야하는 문제.

 

많은 flag를 들고 등산을 가면 distance를 그만큼 넓게 해야하고

적은 flag를 들고 등산을 가면 distance는 좁아지는 대신 많은 flag를 꽂지 못한다.

 

퇴화라는 게 이런걸까..

 

설날이 뭐..얼마나 된다고..이지경으로 퇴화할 수 있는걸까..

peak가 하나도 없을 경우 peak 목록을 구한 ArrayList에서 get 메소드로 element를 구해오면 안 되었다..

아래 네모 부분을 추가해서 예외처리하였다.

 

정확도에서 또 체크해보니 정답보다 큰 값을 리턴하고 있었다.

 

현재 나는 최소 flag 계산식을 바탕으로 가장 큰 peak 인덱스에서 가장 작은 peak 인덱스를 뺀 값의 제곱근을 최소 flag라고 정의하였다.

하지만 가장 큰 peak 인덱스와 가장 작은 peak 인덱스가 멀리 떨어져있는 경우도 있기 때문에

peak 목록의 개수와 최소 flag를 비교해서 peak_count가 최소 flag보다 작을 경우 최소 flag를 peak_count로 정의했다.

 

퇴화한 두뇌 복구가 어느 정도 진행되었다..

 

정확도 테스트에서 time error가 발생한 부분이 있어서 고민해보았다.

min_flag로 정의하고 있는 부분이 정말 최소인가..?

 

공부한 부분을 다시 살펴보면 최소일 수가 없는게 최소 요구 조건이라고 써놓았다.

그러니까 peak의 구성이 저러할 때 최고로 많은 flag를 꽂을 수 있다는 뜻이다.

 

그러니까 최소 요구 조건만큼까지만 체크하면 최대 flag 개수를 구할 수 있다는 뜻이다.

 

성능 테스트만 고려하면 된다.

음.. 일단 이중 for문이 돌아가는 부분을 아래와 같이 수정하였다.

최대 flag 개수부터 1까지 가면서 최대인 값보다 작아지면 리턴하도록 했다. 

 

..? 달라진 것은 위의 부분밖에 없다. for문의 범위는 동일하다. 1부터 min_flags까지로 오름차순, 내림차순의 차이이다.

 

내림차순으로 정확도 테스트 100% 나온대로 다시 구했을 때는 정확도가 다시 100%가 나왔다.

break를 잡는 포인트가 잘못된 것 같아서 위의 wrong answer들을 바탕으로 야매..하게 고민해보았다.

 

문제에 나온 예제를 보았을 때, 4부터 시작했을 때 값이 3, flag 3을 들고 가면 값이 3.. 동일한 값이 나올 수 있기 때문에

지금까지 나온 값보다 무조건 작은 경우에만 break를 잡도록 했다.

 

찾아보니 이진탐색으로 구한 예시도 있다.

 

내가 찾아본 예시와 비슷하게 next_peak 배열을 구한 예시도 있다.

특히, 여기서 next_peak을 아래와 같이 구해서 가지고 와봤다.

이렇게 풀면 좀 더 쉬워질까..?

 

또한, peak에 flag를 꽂을 수 있을까 고려하는 부분에서 아래와 같이 범위를 설정하였다.

peak_count도 flag 개수 고려 시 같이 고려해주었다. (나도 해주고 있기는 한데.. for문 안에서 위와 같이 고려해줘도 되니까..)

또한, 추가적인 break를 해주지 않아도 문제없이 잘 풀리는 것으로 보아서는 불필요한 작업이 포함되어있는 것 같다..나한테..

 

---

peaks 문제

 

주어진 배열을 나누었을 때 peak가 포함되도록 나누려고 하는데, 언제까지 peak가 포함되는지.. 구하는 문제이다..

주어진 배열의 peak만큼 배열을 나눌 수 있다고 생각한다.

(최선을 고려했을 때 peak가 나누어진 배열에 하나씩 들어갈 수 있기 때문에..)

 

peak를 구한 후 배열과 똑같은 사이즈의 배열을 만든다.

주어진 배열과 똑같은 사이즈의 배열은 next_peak이고 다음에 올 peak 인덱스를 기록한다.

 

나누고자 하는 범위 안의 첫번째 인덱스의 next_peak값이 나누려고 하는 범위 안에 있으면

배열 안에 peak가 있다고 판단했다.

 

peak가 1개일 경우도 0으로 리턴하는 줄 알았는데 1로 리턴하는 것이어서 수정했다.

 

아래와 같은 반례를 생각하였는데,

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 4, 6, 3] 일 경우 peak는 2개이고 '4'의 인덱스에서 분할이 이루어져야 하는데, 배열의 size를 2분할해서는 구할 수 없다고 생각했다.

 

그래서 첫 divide에 peak가 없으면 소용이 없다..! 라는 생각으로 첫번째 peak 인덱스값을 바탕으로 구한 것이었는데,

[0, 1, 0, 0, 1, 0, 1, 0]의 경우 첫번째 peak 인덱스를 divide하는 기준으로 생각할 경우 문제가 생긴다.

 

[0, 1]과 [0, 0, 1, 0, 1, 0]일 경우는 문제가 없다.

[0, 1], [0, 0], [1, 0, 1, 0]일 경우는 중간 divide에 peak가 없기 때문에 문제가 있다. 따라서 내가 짠 코드에서는 제대로 돌아갈 수가 없다.

 

는.. 아래와 같은 조건에 의해 말이 안되는 부분이었다.

각 블록에 속한 element는 모두 같은 숫자로 나누어져야한다. 문제를 잘 풀고 싶으면.. 문제를 똑바로 읽자...허허..

 

모든 요소가 같기 위해서는 약수로 나눠줘야한다.

(성능 테스트에서 'prime length일 경우'를 의아하게 생각했었는데, 아마 문제에서 모두 똑같은 요소 개수로 배열을 나눠야한다는 조건 때문이었던 것 같다)

 

약수는 같은 lesson 10에서 풀었었던 약수 구하기 문제를 통해서 구했다.

구하고자하는 수 A를 1부터 A의 제곱근까지만 나눠서 나머지가 0인 수를 구한 후 그 수를 다시 A에 나누면 전체 약수 목록을 구할 수 있다.

 

코드를 아무리 바꿔도 위의 large_random 반례를 만족할 수가 없는데, timeout error가 아닌 wrong answer이기 때문에,

로직 상 문제가 있는 것 같다.

 

---

Lesson11 Start

 

 

---

CountNonDivisible 문제

 

배열에서 나눠지지 않는 수를 구하는 문제인데, 당장 떠오르는 방법이 없어서 아래와 같이 N^2로 구했다.

따라서 성능 테스트는 박살난 모습이었다.

위와 같이 성능테스트는 박살난 형태인데, 성능을 극복해보겠습니다.