나만의 길

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 입출력 인덱싱과 R처리만 구현하면 크게 어렵지 않았던 문제. 남들은 시간초과가 발생했다고 했는데, 오히려 틀렸습니다.. 이후 정답.. 생각보다 문제에 잘 접근했었던 것 같습니다. 시간초과를 해결하는 중요 포인트가 R에서 reverse를 최종적으로 1번만 처리하는 것입니다. 이에 대해서는 아래에서 설명하겠습니다. ※ 고려사항 1. 입력 인덱싱 2. 함수 처리 3. 출력 처리 1. 입력 인덱싱 생각보다 이 곳에서 시간을 많이 소비했습니다. split과 st..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 시간 초과를 어떻게 해결하느냐가 중요했던 문제입니다. 3번의 시간초과 끝에, 문제를 풀 수 있었습니다. 해당문제에서 중요한 것은 heap을 통한 Queue 구현인데, 바로 2개의 heap을 통해서 문제를 해결했어야 합니다. 개인적으로 시간초과를 해결하는 데까지 굉장히 어려웠던 문제였습니다. ※ 고려사항 1. heap, 방문 처리 2. 연산처리 3. 출력처리 1. heap, 방문 처리 해당문제에..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 시간초과로 굉장히 고생을 많이 했던 문제입니다. 제가 시간초과가 발생한 이유를 확인해보면서 문제에 접근해보도록 하겠습니다. 해당문제는 최소힙, 최대힙 문제를 구현했으면, heap 자료구조를 이용하여 문제에 접근하면 됩니다. 그러나, 절댓값을 고려해야 하므로, 적절한 정렬방법이 요구됩니다. 해당문제는 절댓값과 입력값을 동시에 heap에 push하여 정렬하는 접근이 필요로 되는 ..