1250 - 색칠된 공들

https://www.acmicpc.net/problem/1250

1250번: 색칠된 공들

메모리 관리가 주된 어려움이다.

이문제를 푸는건 어렵지 않지만, 말 그대로 언어에 정통한 이해를 가지고 있어야 한다.

난 그정도는 아니다.
책을 펼치고 정석으로 공부한게 아닌게 좀 부끄럽다.

기존에 내 풀이로 짠 코드에 필요한 리소스만 땡겨서 제출했는데, 메모리 초과가 난다.

다른 풀이를 여기에 적었다.

이 문제는 128MB이라는 극악한 환경에서 수행되어야 하는 코드를 짜야한다.

체감이 안될 수도 있는데, _int32 * 10,000,000은 40MB정도 이다.

얼마나 아껴야 하는지 감이 잡히는가???

일단 입력만 받아도 굉장히 힘들다.

Char 2byte * 10,000,000

허…. 벌써 몇이 날아간건가..
19.0734 MB가 증발했다.

• 2023. 10. 4 ) 이 부분은 char배열을 만들어 두지 않고, cin.get()을 활용하여, 바이트 단위로 읽어들인다. 그렇게 20MB를 아낀다.

C++을 겉핥기로 해서, 입력받을 때, 사용한 메모리를 다시 해제시켜, 프로그램에 필요한 리소스로 할당해주지 못한다.

이부분은 공부해야 한다. 애초에 가능한건가..

일단 연속된 문자열들을 합쳐서 이러한 형태의 링크드 리스트를 만든다.

(3, ‘A’) - (1, ‘K’) - (6, ‘H’)

이때, 이 구조를 포인터로 만들지… 배열에 동적 할 당 시키고, 적당한 간격으로 청소해주어야 하는지 모르겠다.

청소는 대충 더미노드가 sqrt(N)개 쌓일 때마다, 하면 되겠는데, 이게 시간초과 날 수 있어서 적당한 값을 정해 일정 주기 마다 청소하면 되겠다.

더블 링크드 리스트를 만들고 우선순위 큐를 만든다.

메모리를 아끼기 위해, 26가지 밖에없는 경우의 수를 표현할 때, 더 작은 자료형을 사용한다. (_int8)

이때, M번째, 수의 경우를 A라고 할 때, M먼째, 문자열이 포함되어 있는 문자집합을 경우의 수 27이라고 정의한다.
경우 A와 경우 27이 합쳐질 때, 27이 될 수 있도록 케이스 워크를 해준다.

그렇게 하면 별다른 리소스 할당 없이, M번째 문자열을 제거하는 것을 알 수 있다.

문제는 그럼 경우 27을 뽑고, 우선순위에서 존재하는 노드를 제거 한 횟수가 되겠다.

우선순위 큐에서 뺀다음에, 노드의 양옆을 접근, 합칠 수 있으면 합친뒤 우선순위 큐에 다시 넣는다.

이 부분이 문제가 된다. 합쳐지면서, 새롭게 넣느라, 메모리를 더 써야하고, 더미노드들도 안에 존재해서 어떻게든 해야 한다.

이런 합쳐 지는 현상은 O(N)꼴로 일어난다.
(대략 합쳐지는게 이진트리 꼴이니까)

즉 그만큼 구조체를 더 생성해야 한 다는 것인데, 이걸 중간에 한번 싸악 돌면서 없애면서 메모리 관리를 해야 할 수도 있다.

이건 뭐, N이 워낙 크니까 적당히 수를 잡으면서 트라이 해 주면 되겠다.

시간을 비효율적으로 쓰더라도, 메모리를 아끼는것이 제일.. 중요하다.

흠… 특징만 봐서는 우선순위 큐를 쓰지 않고, select sort 를 이용해서 O(1)에도 처리 할 수 있어 보이긴 하는데.. 어떻게 든 메모리를 줄이는 것이 관건이다.

이 부분에 대해 공부를 좀더 해봐야 겠다.
뭐… 코드를 짜서 실행을 해보고 무수한 트라이를 내야 풀 수 있을 것 같은데 생각을 좀 거 해봐야 겠다.