[leetcode][735] Asteroid Collision
문제 : leetcode.com/problems/asteroid-collision/ 0이 아닌 정수 값을 가진 asteroids 배열이 주어진다. 요소의 절대값은 크기를 의미하고 부호는 방향을 의미한다. 같은 방향을 가지는 운석들은 부딪히지 않는다. 다른 방향을 가지는 운석들이 만날때 크기가 크거나 같은 운석들이 파괴된다. asteroids 배열에서 충돌가능한 운석들이 충돌한 뒤 남은 운석들의 배열을 반환하라. [1,2,3,4,-5] 가 주어졌을 때, -5는 4,3,2,1을 차례대로 파괴시킬 수 있고, 만약 [1,2,6,3,-5] 과 같은 운석들이 있다면 -5 운석은 3까지만 파괴시키고 6을 만나 파괴되므로 1,2 운석은 확인하지 않아도 되기 때문에 스택을 사용했다. 배열을 앞에서부터 탐색하면서 스택에 ..
2020. 10. 24.
[leetcode][189] Rotate Array
문제 : leetcode.com/problems/rotate-array/ Follow up에 적힌 공간복잡도 O(1)을 목표로 해보자. 예시로 나온 nums=[1,2,3,4,5,6,7], k=3을 예로 들어보면 일단 nums 배열은 모두 reverse 시킨다. nums=[7,6,5,4,3,2,1] 그리고 앞에서 k개의 원소를 reverse 시키고 nums=[5,6,7,4,3,2,1] k개 이후의 원소들을 다시 reverse 시키면 원하는 배열을 만들 수 있다. nums=[5,6,7,1,2,3,4] 이 때 k는 음수가 아니라는 말만 있고 nums 배열 크기보다 클 수도 있으므로 모듈러 연산해줘야 한다. k = k % |nums| 시간복잡도는 O(N). 공간복잡도는 O(1) 소스코드 : github.com/..
2020. 10. 16.