배열

메모리 상에 원소를 연속적으로 배치한 자료구조

 

특성

1. O(1)에 k번째 원소를 확인/변경 가능

2. 추가적으로 소모되는 overhead가 거의 없음

 

연산과 시간 복잡도

1. 임의의 위치에 있는 원소를 확인/변경 O(1)

2. 원소를 끝에 추가 O(1)

3. 마지막 원소를 제거 O(1)

4. 임의의 위치에 원소를 추가 O(N)

추가하는 위치 뒤에 있는 원소들을 한칸씩 뒤로 밀어야 하기 때문에 O(N) 소모

추가하는 위치가 뒤쪽에 가까울 수록 소요되는 시간은 줄어듬

5. 임의의 위치에 원소를 제거 O(N)

지운 원소 뒤에 있는 원소들을 앞으로 한칸씩 당겨 와야하기 때문에 O(N) 소모

 

BOJ 문제 풀기

문제 

문제집: 0x03강 - 배열 (BaaaaaaaaaaarkingDog)

1. q10808

문제: 문자열 s의 각 알파벳 수를 출력한다

풀이: 각 알파벳의 개수를 셀 배열을 만들어서 문자열을 순회하며 각 알파벳이 얼마나 등장했는지 확인한다

a 가 아스키코드 96이기때문에 이를 0으로 취급해서 index를 설정하고 카운트 한다

    for (c in s) {
        alphabet[c - 'a'] += 1
    }

해결: O

 

2. q2577

문제: 세 개의 자연수를 곱한 계산 결과에서 0~9까지 각각의 숫자가 몇 번씩 쓰였는지 출력한다

풀이: q10808과 비슷한 방식으로 해결

   for (num in result) {
        frequency[num - '0'] += 1
    }

해결: O

 

 

3. q1475

문제: 방번호를 만들 수 있는 숫자 세트(0~9)가 몇개 필요한지 출력 (6, 9 뒤집어서 이용 가능)

풀이: 숫자 빈도 카운트, 제일 많이 카운트된 숫자 수만큼 세트가 필요하기 때문에 카운트 배열에서의 최대값을 구한다.

이때 6,9는 교차 가능하므로 같은 숫자로 취급해야 한다. 편의상 배열에 저장할 때 9가 나오면 6의 카운트 증가 시키고

한세트당 6,9가 들어있기 때문에 6+9 카운트를 2.0으로 나눠주고 그 값을 올림해준다.

    val frequency = IntArray(9)

    for (c in roomNumber) {
        val index = if (c == '9') '6' - '0' else c - '0'
        frequency[index] += 1
    }
    frequency[6] = ceil((frequency[6] / 2.0)).toInt()
    val maxCount = frequency.maxOrNull()

해결: O

 

 

4. q3273

문제: 수열 a와 자연수 x가 주어졌을 때 , ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 출력

풀이: n의 범위가 10만이기 때문에 O(n^)으로는 통과 못할 가능성이 크기 때문에 O(NlogN), O(N)의 방법을 고려.

배열을 두고 등장하는 수 체크하는 방식으로 풀려고 했으나 계속 ArrayIndexOutOfBounds 오류가 남

어디서 잘못된 건지 모르게씀 ^^; 

해결: X

 

5.  q10807

문제: n(1~100)개의 정수가 주어졌을 때, 정수 v(-100 ~ 100)가 몇 개인지 출력

풀이: for 돌면서 숫자 세기

해결: O

 

6. q13300

문제: 조건에 맞게 방에 배정할 경우 모든 학생을 배정하기 위해 필요한 방의 최소 개수

* 같은 학년, 같은 성별끼리 최대 인원수를 넘기지 않고 배정하기

풀이: 2차원배열로 방을 만들고 조건에 맞게 학생들을 넣는다. 방에 있는 인원을 최대인원수로 나눠 주고 필요한 방의 수를 카운트 한다

    // 성별, 학년
    val room = arrayOf(IntArray(6) { 0 }, IntArray(6) { 0 })

    for (i in 0 until n) {
        val tokenizer = StringTokenizer(readLine())
        val s = tokenizer.nextToken().toInt()
        val y = tokenizer.nextToken().toInt()

        room[s][y - 1] += 1
    }

    var roomCount = 0
    for (i in 0..1) {
        for (j in 0..5) {
            val numberOfStudents = room[i][j]
            roomCount += ceil(numberOfStudents / k).toInt()
        }
    }

해결: O

 

7. q11328

문제: 첫번째 테스트 케이스 문자열로 두번째 테스트 케이스 문자열을 만들 수 있는지?

테스트 케이스 수 1~1000개, 문자열 최대 길이 1000

시간 제한 2초이고 테스트 케이스도 작기 때문에 O(n^)으로 풀어도 가능할듯

풀이: 같은 문자열을 만들기 위해선 크기가 같아야 함 이부분을 조건으로 걸어주고, 
첫번째 문자열을 검사하며 나오는 알파벳을 배열에서 + 시키고

두번째 문자열을 검사하며 나오는 알파벳을 배열에서 - 시킴

해서 0이 아닌게 있다면 다른 문자열

(boolean 값을 초기화 해주지 않아서 틀렸었다)

        val arr = IntArray(26) { 0 }

        if (s1.length != s2.length) {
            possibility = false
        } else {
            for (c in s1) {
                arr[c - 'a']++
            }

            for (c in s2) {
                arr[c - 'a']--
            }

            for (j in arr) {
                if (j != 0)
                    possibility = false
            }
        }

해결: O

 

8. q1919

문제: 두 단어가 애너그램 관계가 되기 위하여 제거해야 할 문자의 수 출력하기

풀이: 위 문제와 비슷한 논리. 첫번째 문자열에선 ++, 두번째 문자열에선 -- 시켜서 0이 아닌 수들의 합이 제거해야 할 문자 수

    for (c in s1) {
        arr[c - 'a']++
    }

    for (c in s2) {
        arr[c - 'a']--
    }

    for (i in arr.indices) {
        if (arr[i] != 0) {
            count += abs(arr[i])
        }
    }

해결:O

 

함수 정리

1. ceil(): 소수점 올림

2. maxOrNull(): max() 대신 사용

3. abs() : 절대값 구하기 (음수 -> 양수)

 

kotlin 에서 Array

생성

val numbers = arrayOf(4, 5, 6, 3)
val nullArray = arrayOfNulls<Type>(arraySize)

arrayOf() : 기본 생성자

Array() : 기본 생성자

arrayOfNulls(): 빈 배열 생성자

 

접근/변경

val nullArray = arrayOfNulls<Int>(5)
nullArray[1] = 1 // set(1, 1)
print(nullArray[1]) // get(1)

접근 : arr[index] or arr.get(index)

변경 : arr[index] = value or arr.set(index, value)

 

추가/ 제거

val arr1 = intArrayOf(1, 2, 3, 4, 5)

val arr2 = arr1.plus(6)
println("arr2: ${Arrays.toString(arr2))}") // arr2: [1, 2, 3, 4, 5, 6)

val arr3 = arr1.sliceArray(0..3)
println("arr3: ${Arrays.toString(arr3))}") // arr3: [1, 2, 3, 4]

선언된 배열의 길이는 수정 불가하기 때문에

추가하고 싶다면 plus()를 통해 새 배열을 만들어야 함

plus(value) : 새로운 요소를 추가하기 위한 함수

sliceArray(시작 인덱스..끝 인덱스) : 배열을 자르기 위한 함수

 

https://junyoung-developer.tistory.com/86