728x90
반응형
문제
풀이 (brute-force)
- 상세 풀이 주석
- 시간 복잡도 O(n)
/**
* 1. 문제
* - listNode1, 2 가 주어짐.
* - listNode1 의 a,b 번째를 삭제한다.
* - 그 사이에 listNode2 를 채운다.
*
* 제약 조건
* 3 <= list1.length <= 104
* 1 <= a <= b < list1.length - 1
* 1 <= list2.length <= 104
*
* 2. 풀이 (brute-force)
* - list1 을 순회하면서 ListNode result 에 추가한다.
* - list1 a 를 만나면 list2 를 result 에 추가한다.
* - list1 b 까지 순회하고, 나머지를 result 에 추가한다.
* - 시간복잡도 O(n)
*
*/
fun mergeInBetween(
list1: ListNode,
a: Int,
b: Int,
list2: ListNode
): ListNode {
// a 는 1이상이니 list1[0] 인덱스를 처음에 넣어준다.
val result = ListNode(list1.`val`)
// tail 은 항상 result 의 마지막 next 를 가리켜야 함. tail 을 사용하는 이유는 매번 끝까지 조회하는 것은 비용이 크기 때문
var tail = result
// idx 는 listnode1 의 index 를 의미. a 는 1이상이니 idx 는 1부터 시작
var idx = 1
// list1 의 current listnode
var current = list1
// list1 을 순회하면서 list2 를 넣는다.
while (current.next != null) {
// list2 를 추가할 조건
if (a <= idx && idx <= b) {
// 마지막을 list2 에 연결시켜줌
tail.next = list2
// 마지막은 list2 의 마지막을 가리켜야 함
tail = getLastListNode(list2)
// a 부터 b 까지 제거할 예정이니 b+1 까지 current 를 순회
while (idx <= b) {
current = current.next!!
idx++
}
}
// tail.next -> result 마지막 next 가리킴
tail.next = ListNode(current.next!!.`val`)
// tail.next 는 result 마지막의 next 의미. 그것을 다시 tail 붙여서 result 마지막 next 를 가리킴
tail = tail.next!!
current = current.next!!
idx++
}
return result
}
// listNode 마지막 return
fun getLastListNode(listNode: ListNode): ListNode {
var tmp = listNode
while (tmp.next != null) {
tmp = tmp.next!!
}
return tmp
}
'algorithm > leetcode' 카테고리의 다른 글
Leetcode61.RotateList (kotlin) (0) | 2024.04.13 |
---|---|
Leetcode 41. First Missing Positive (0) | 2024.04.09 |
Leetcode 930.BinarySubarraysWithSum (0) | 2024.03.26 |
[leetcode] Number of Islands 정리 (0) | 2022.01.28 |
leetcode Employees Earning More Than Their Managers 풀이 (0) | 2020.09.30 |
댓글