[2023-01-01]

FrogJmp 문제

 

입력 범위가 1부터 10억까지이기 때문에

X와 Y가 각각 1과 10억이고 D가 1로 입력값이 들어오고 반복문을 돌려서 체크하게 되면

10억번 반복문이 돌아간다.

 

따라서 문제 그대로 구현하기보다는 최대한 반복문을 안 쓸 수 있는 방법을 택하는 것이 좋겠다.

 

 

 

---

PermMissingElem 문제

배열 원소 구성은 1부터 N+1로 되어있고 배열의 크기가 4라면 1 ~ 5로 구성되어 있다는 의미이다.

 

1부터 N + 1이 배열에 있는지 찾으려면 이중 for문으로 이루어져야 할 것이라고 생각했다.

시작값이 1이고 끝나는 값이 N+1인 for문이 하나 돌고 array에 1 ~ N+1이 있는지 확인하기 위한 for문이 돌아서 총 2개

 

최악의 경우 N이 100,000

100,000 * 100,000 일 경우 10,000,000,000로 아마 시간이 초과될 것이다.

 

따라서 boolean 배열에 한번 결과를 저장하고 저장된 결과를 통해 missing한 element를 찾는 방법을 선택했다.

이렇게 할 경우 단일 for문이 2번 돌기 때문에 시간복잡도는 O(N)이다.

 

 

---

TapeEquilibrium 문제

 

문제 그대로 푸는 것 말고 뚜렷하게 떠오르는 해결 방법이 없어서 이중 for문으로 풀었더니 아래와 같이 효율성에서 박살이 났다.

생각을 해보아야겠당..

 

 

어차피..P가 1부터 N-1까지 다 보아야하는 경우라면 배열의 총합을 구한 후 뒤에서 하나씩 빼면서 값을 비교하도록 구현을 변경하였다.

A[0] + A[1] + A[2] + A[3] + ... + A[N-1] 한 후

P가 N-1부터 1까지 1씩 빼면서 반복하도록 for문을 구성한다.

 

A[0] + ... + A[N-1] - A[N-1] * 2로 (A[0] + ... + A[P-1]) - A[N-1]를 만들 수 있다.

위에서 만든 (A[0] + ... + A[P-1]) - A[N-1]에서 다시 A[N-2] * 2를 하면 (A[0] + ... + A[P-1]) - (A[N-2] + A[N-1])이 된다.

 

 

---

FrogRiverOne 문제

 

코딜리티는 왜 이리 개구리를 좋아하는걸까..?

개구리가 강을 못 건너는 걸 보고 슬퍼한 개발진이 있는걸까.. 개구리가 언제쯤 강을 건널지 구하는 문제였다...

 

문제풀이가 어려웠던 것보다 영어해석이 더 어려운 문제로 기억될 것 같다.

 

문제 요약)

개구리는 강 건너편으로 건너고 싶어한다.

개구리가 점프를 해서 건널건데 강 위에 떨어지는 나뭇잎을 밟으면서 반대편으로 이동한다고 한다.

 

배열 A에는 언제 어느 위치에 나뭇잎이 떨어질지에 대한 정보가 들어있다.

A[K]는 K초에 나뭇잎이 떨어지는 위치이다.

 

이때 개구리는 모든 위치에 나뭇잎이 있어야만 강을 건널 수 있고 강물의 세기가 빠르지 않아서 나뭇잎의 위치가 변하지 않는다.

 

 

---

PermCheck 문제

연속되는 일련의 숫자 구성을 permutation이라고 한다.

 

계속 틀렸는데.. 처음에는 총합을 구해서 for문을 돌면서 element를 빼도록 구현했다.

 

그림에서 antiSum1, 2에서 sum으로 구현 시 예외 처리를 하고 있다.

예를 들어.. 1, 1, 4일 경우 sum이 0이 되기 때문에 permutation이라고 판단했다.

 

이러한 부분을 막기 위해 체크한 숫자인지를 파악했는데 이래도 extreme_values에 걸렸다..

추가적인 조건이 필요한 것인가 고민이 되던 찰나에 조건을 추가하지 말고 구현 방법을 바꿔야겠다는 생각이 들었고..

(제 스타일이..if문 추가하는 거 엄청 싫어해서여.. 코드가 if 범벅 되는거 혐오해여..)

 

배열에 있는 숫자를 꺼내서 List에 넣고 Collections.sort로 정렬 후 for문으로 1부터 N까지 체크하는 방법을 선택했다.

 

 

 

---

MaxCounters 문제

문제 해석하고..이해하는데 한바지 거의 15분쓰고..2분만에 풀었는데.. 아래와 같이 타임아웃나왔당..

다시 생각해보쟝..

 

max counter 부분에서 for문으로 전체 배열 요소의 값을 바꿔주는 것이 부담일까 싶어서 아래와 같이 변경하였다.

배열을 초기화하고 max 였던 값을 저장한다.

그리고 새롭게 increase를 하면서 만들어지는 최대값을 저장해서 max_num에 저장해서

max_counter를 수행해야할 때 max값에 더한다.

 

그랬지만.. 뭔가 아직 부족하다..

아마 처음 방법은 O(N^2)였을 것이고 지금은 O(N + M)까지 줄일 수 있었다.

 

예외처리가 되지 않은 부분이 extreme_large라는데.. 모든 기능이 max_counter operations일 때..! 라는 것 같은데..

 

 

최종 100% 받은 코드는 아래와 같다.

위에서 max counter로 인한 작업이 오래 걸리는 것 같아서..작업이 필요치 않은 경우에는 아래와 같이 작업을 건너뛰었다.

 

max_num은 increase를 했을때 초기화되는데, increase 작업이 없을 경우 max counter 작업이 이루어지지 않도록 예외처리했다.

increase 작업이 없을 경우에 대한 예외처리를 하니 위의 표시한 것처럼 1.292s 걸렸는데 이거를 체크하지 않았을 때는 6.820s 걸렸었다.

 

예외처리에 대한 고민이 얼마나 중요한지에 대해 생각할 수 있었다..

 

---

MissingInteger 문제

정렬 후 for문으로 배열을 돌리고 1부터 비교한다.

 

sequence라..! 연속된 숫자에 등장하지 않은..! 제일 작은 숫자를 말한다.

 

 

---

CountDiv 문제

 

A부터 B까지 나누면서 풀 수 있는 문제이지만 입력값 범위가 0부터 2억이고 K도 1부터 2억이라 효율적인 알고리즘 풀이는 아니다.

따라서 A, B를 K로 나누었을 때의 값과 나머지를 이용해서 문제를 풀었다.

O(N)이라도 입력범위로 인해 시간 초과가 날 수 있지만 위와 같이 풀면 시간복잡도가 O(1)이다.

성능 테스트할 때 보면 MAXINT로 테스트하는 것을 볼 수 있다.

 

 

---

GenomicRangeQuery 문제

 

minimal impact factor를 이해를 못해서 30분가량을 날려먹고 문제 그대로 구현하였다.

N과 M의 크기가 각각 100,000 와 50,000이라서 이중 for문이 돌았을때 괜찮을 거라고 생각했는데 지금 생각하니 왜 괜찮다고 생각한거지.. (최악이 5억인데..될리가..)

 

String을 어찌어찌..정리해서 하면 성능을 높일 수 있지 않을까..