[Kotlin] 배열과 Map에 대해 알아보기

요즘 필자는 알고리즘 문제를 풀고 있다.

알고리즘 문제를 풀다 보면 배열은 거의 대부분의 문제에서 사용하는 것 같고, HashMap도 종종 사용하는 것 같았다.

그래서 이번에 코틀린의 배열과 HashMap의 차이에 대해 간단히 설명해보고자 한다.

앞으로 이런 간단한 알고리즘 개념에 대한 포스팅이 올라올 것 같다.

 

1. 배열(Array)

배열은 코틀린을 공부하지 않은 사람이라도 프로그래밍 언어를 하나라도 공부해 본 경험이 있으면 바로 알 수 있을 것이다.

바로 데이터의 집합을 배열이라고 하는데 자바의 배열 선언과는 달리 코틀린의 배열은 상당히 편리하면서도 복잡(?)하다.(필자 기준)

필자가 왜 복잡하게 느꼈냐면, 코드로 설명해 주겠다.

 

자바의 경우에는 다음과 같이 배열을 만들 수 있다.

int[] intArray;
String[] stringArray;

int intArray[];
String stringArray[];

 

하지만 코틀린의 경우에는 다음과 같이 선언할 수 있다.

val intArray1 = intArrayOf()
val intArray2 = arrayOf<Int>()
val intArray3 = Array(3) {0}

코틀린과 자바의 List 형식은 Array만 있는 것은 아니지만(List 등) 예를 들어서 Array로만 설명했다.

 

Array는 List처럼 보는 List와 편집하는 List(MutableList)가 나뉘어 있는 것이 아닌 set과 get을 모두 할 수 있다.

val array = Array<Char>(5) { 'a' }
array[array.lastIndex] = 'b'
println("array set result: ${array.toList()}")
val get = array[array.lastIndex]
println("array get result: $get")

array[array.lastIndex] = 'b'는 array.set(array.lastIndex, 'b')를 변형한 코드이고

get 변수는 array.get(array.lastIndex)를 변형한 코드이다. 코틀린스럽게

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있을 것이다.

기존의 a, a, a, a, a의 배열에서 마지막 a를 b로 변경했고, 변경한 마지막 index를 가져온 모습이다.

하지만 단점도 있는데

배열의 크기를 바꿀 수 없다는 점이다!

처음에 배열을 선언할 때 배열의 크기를 정해야 하는데,

val array = Array<Char>(5) { 'a' }

나중에 저 array의 크기를 초과하는 index에 데이터를 삽입하거나 불러오려고 하면

ArrayIndexOutOfBoundsException이 발생할 것이다.

위의 단점 하나로도 알고리즘 문제를 풀 때의 선택지가 많이 떨어질 텐데, 또 다른 단점이 하나 더 있다.

왜인지는 모르겠지만 Array에서 drop이 되지 않았다.

필자는 위의 array에서 1번째의 index를 삭제하기 위해 drop을 사용했다.

array.drop(1)
println("array drop result: ${array.toList()}")

하지만 drop이 이루어지지 않았다.

drop이 된 모습을 print 해서 보이게 하려면 다음과 같은 방법을 써야만 했다.

println("array drop result: ${array.drop(1).toList()}")

array.drop()을 사용하면 바로 array에 반영되는 것이 아닌 따로 변수로 만들어 주어야 삭제된 버전의 array를 사용할 수 있는 듯했다.

위의 2개의 단점을 직접 프로그래머스를 풀면서 찾아낸(?) 단점들이다.

그래서 필자는 변경 가능한 리스트인 MutableList를 자주 사용한다 ㅎㅎ.

 

필자가 배열을 이용해 해결한 문제들(프로그래머스)

3번을 제외한 나머지 문제들은 2차원 배열을 이용해 풀었다.

1. 공원 산책(lv 1)

https://school.programmers.co.kr/learn/courses/30/lessons/172928

2. 바탕 화면 정리(lv 1)

https://school.programmers.co.kr/learn/courses/30/lessons/161990

3. 덧칠하기(lv 1)

https://school.programmers.co.kr/learn/courses/30/lessons/161989

 

2. Map(HashMap)

이번에는 Map을 알아볼 건데

map은 key와 value로 나뉘어 있어서 key로 특정 value를 찾을 수 있고, 특정 key에 여러 개의 value를 넣을 수 없다는 특징을 가지고 있다(key와 value가 1:1의 관계를 가진다.).

여기서 HashMap과 MutableMap의 차이를 궁금해하는 경우가 있을 수 있는데,

HashMap은 MutableMap Interface에 속하는 다양한 Map 중 하나라고 한다. 그렇기에 hashMap은 mutableMap의 한 종류라고 한다.

관련 자료 링크: https://velog.io/@moonpiderman/Kotlin-MutableMap-vs-HashMap

[Kotlin] MutableMap vs HashMap

 

바로 예제를 통해 확인해 보자.

key가 int이고 value도 int인 map을 생성해 주었다.

map의 생성 방법은 Map<Type, Type>()을 이용해서도 생성할 수 있지만, 우리가 사용하는 언어는 kotlin이기 때문에 좀 코틀린스러운(?) map 생성을 해주도록 하자.

val map = mapOf(0 to 0, 1 to 1, 2 to 2)
val mutableMap = mutableMapOf(0 to 0, 1 to 1, 2 to 2)

기본 Map은 mapOf()으로, MutableMap은 mutableMapOf()으로 생성 가능하다.(그럼 hashMap도 어떻게 생성하는지 감이 잡힐 것이다.)

출력하면 간단하게 이런 형식으로 출력된다.

이제 map의 데이터를 수정해 보겠다.

참고로 기본 map은 데이터 수정과 수정, 삭제가 불가능한 불변형이기 때문에 mutableMap을 이용해 데이터를 변경해 보겠다.

mutableMap[3] = 3
println("mutableMap set result: $mutableMap")
mutableMap.remove(3)
println("mutableMap remove result: $mutableMap")
mutableMap[2] = 5
println("mutableMap modify result: $mutableMap")

코드 순서대로 설명하자면,

1. mutableMap에 key가 3이고, value가 3인 데이터를 추가한다.
2. mutableMap에 key가 3인 데이터를 삭제한다.
3. mutableMap에 key가 2인 데이터의 value를 5로 변경한다.

이다. 실행 결과는 다음과 같다.

아까 필자가 한 개의 key에 여러 개의 value가 들어갈 수 없다고 했었는데, 그래서 기존의 데이터인 2가 사라지고 새로운 데이터인 5로 덮어 씌워진 것을 확인할 수 있다.

 

필자가 Map을 이용해 해결한 프로그래머스 문제는 다음과 같다.

1. 달리기 경주(lv 1)

https://school.programmers.co.kr/learn/courses/30/lessons/178871

 

위의 문제는 배열과 map을 모두 이용해서 해결할 수 있지만, 배열을 사용하면 시간 초과가 발생할 것이다.(내가 그랬었다 ㅠ)

 

3. 시간 복잡도

배열과 Map의 시간 복잡도를 아주 간단히 설명하자면,

배열에서 특정 값을 찾으려고 할 때, O(n)의 시간 복잡도를 가진다.

예를 들어서 배열 A에서 A[5]의 값을 찾으려고 할 때, A[5]를 찾기 위해 A[0] -> A[1]... 순서대로 검색하기 때문에 시간 복잡도는 O(n)이 된다.

만약 2차원 배열에서 특정 값을 찾으려고 한다면, O(n x n)의 시간 복잡도를 가지게 될 것이다.

 

Map에서 특정 값을 찾을 때에는 O(1)의 시간을 가지는데,

Map의 key에 접근해서 value를 알아내기 때문이다.

 

시간 복잡도의 더 자세한 설명은 다음의 글들을 보고 공부해 보면 좋을 것 같다.

https://bb-library.tistory.com/144

[Kotlin] 컬렉션(Collections)

 

4. 정리

• 둘 다 특정 상황에서 유용하게 사용할 수 있을 것 같다.
• 알고리즘을 풀 때에는 불변성보다 가변성이 좋은 것은 어쩔 수가 없는 것 같다. 가변성과 불변성의 차이도 추후게 공부해 봐야겠다.
• 한참 동안 놓고 있던 알고리즘을 다시 푸니까 옛날에 한참 풀 때의 감이 다 사라진 것 같다. 이래서 알고리즘 공부는 꾸준히 해야 한다는 말을 바로 이해할 수 있었다.
• 알고리즘 문제를 풀고 나면 역시 성취감이 컸다. 모든 테스트 케이스를 통과했을 때의 짜릿함(?)은 잊을 수가 없다.
  앞으로 종종 알고리즘 정리 포스팅도 올려야 할 것 같다.