https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

푸는 동안 사고과정 및 개선점

처음에 진짜 감이 안잡혔다. 접두어 처리를 해서 contains를 하면 될 것 같은데, 이게 Hash가 맞나?? 이런 생각이 머리 속에 맴돌았다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        TreeSet<String> ts = new TreeSet();
        for(String phone: phone_book){
            ts.add(phone);
        }
        
        // 각 전화번호의 모든 접두어를 확인
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) { // 길이는 1이상
                String prefix = phone.substring(0, i);
                if (ts.contains(prefix)) {
                    answer = false;
                }
            }
        }
        
        return answer;
    }
}

2중 포문은 어쩔 수 없는 것 같다. 그래도 contains로 해서 조회 때 O(1)을 해줘서 좀 빠른 게 아닐까

중복된 번호가 없으니까 HashSet에 넣어서 조회 성능을 올려주고, 각 번호를 돌면서 substring을 잘라 이게 HashSet에 존재하는 것인지 찾는다. 이러면 존재할 경우 접두어가 있는 Set이 된다.

# 추가 공부

substring은 ` [ startIndex, endIndex ) ` 다. 이상, 미만이기 때문에 주의해야된다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

푸는 동안 사고과정 및 개선점

처음에는 진짜 두 배열을 정렬해서 비교하면 되겠지라고 생각했다. 근데 입력이 10만이라 아마 그렇게 했으면 효율성 검사에서 걸리지않았을까..
동명이인이 있는 상태라 Set은 못쓰고, 그래서 Map을 썼다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        TreeMap<String, Integer> tm = new TreeMap();
        for(String name: participant){
            tm.put(name, tm.getOrDefault(name, 0)+1);
        } // 트리맵에 저장해두기 -> 굳이 TreeMap일 필요없음
        // 이제 completion을 돌면서 처리하자
        for(String name: completion){
            tm.put(name, tm.get(name)-1);
        } // 0이면 완주했다는 의미가 될 것
        
        Iterator<String> keys = tm.keySet().iterator();
        while(keys.hasNext()){
            String key = keys.next();
            if(tm.get(key) != 0){
                answer = key;
                break;
            }
        }
        
        return answer;
    }
}

TreeMap을 쓰고, key를 이름, value를 인원수로 설정했다. 정렬이 필요없기때문에 HashMap을 쓰는 게 효율적이지만 그냥 숙련을 위해 TreeMap을 선택했다.

초기화할 때 getOrDefault를 쓴 이유는 value가 없을 때 null 반환하는 걸 막기 위함이다.

그렇게 다 처리를 하고 나서, 인원수가 1인 key를 찾아야 하는 게 문제였다. 위 코드처럼 keySet을 사용해도 되는데 이 경우 조회해야되는 값이 엄청 많다면 entrySet에 비해 엄청 느리다고 했다.

그리고 entrySet을 쓰면 iterator를 안써도 되기 때문에 아래처럼 해보는 건 어떨까

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        TreeMap<String, Integer> tm = new TreeMap();
        for(String name: participant){
            tm.put(name, tm.getOrDefault(name, 0)+1);
        } // 트리맵에 저장해두기 -> 굳이 TreeMap일 필요없음
        // 이제 completion을 돌면서 처리하자
        for(String name: completion){
            tm.put(name, tm.get(name)-1);
        } // 0이면 완주했다는 의미가 될 것
        
        for(Map.Entry<String, Integer> item : tm.entrySet()){
            if(item.getValue() != 0){
                answer = item.getKey();
                break;
            }
        }
        
        return answer;
    }
}

# 추가 공부

TreeMap 알아보기

// entrySet()을 사용하여 모든 항목 순회
for (Map.Entry<String, Integer> entry : tm.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + ": " + value);
}

// 특정 조건에 맞는 항목 찾기
for (Map.Entry<String, Integer> entry : tm.entrySet()) {
    if (entry.getValue() > 2) {
        System.out.println(entry.getKey());
    }
}

// 맵 수정하기
for (Map.Entry<String, Integer> entry : tm.entrySet()) {
    entry.setValue(entry.getValue() * 2);
}

Tree 시리즈 답게 레드블랙트리로 구현되어있고, SortedMap인터페이스의 구현체다.  키를 기준으로 정렬된 상태(기본은 오름차순)이며 entrySet을 사용하면 맵의 모든 key-value 쌍을 `Set<Map.Entry<K,V>>` 형태로 반환한다.

set이 add, remove였다면 map은 put, get, remove(key로 삭제, entrySet에서 삭제, key-value로 삭제)가 있다.

삭제만 좀 보면 아래와 같다.

// 1. 키를 사용한 삭제
tm.remove("Apple");

// 2. 키와 값을 모두 사용한 삭제
tm.remove("Banana", 2);

신기한 건 removeIf가 있는데 아래처럼 사용한다. 람다식을 쓰는건데 그냥 이런게 있다 정도만 기억하고 넘어가야 될 것 같다.

// 짝수만 제거하기
tm.entrySet().removeIf(entry -> entry.getValue() % 2 == 0);

putIfAbsent도 있어서 이걸 활용하면 value에 Collection도 넣을 수 있다.

tm.putIfAbsent("A", 1);

기존의 put이 무조건 키를 덮어썼다면 putIfAbsent는 키가 없을 때만 동작한다. 그래서 Collection같은 걸 new로 넣어줄 때 쓰면 되겠다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

푸는 동안 사고과정 및 개선점

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        TreeSet<Integer> ts = new TreeSet();
        for(int i: nums){
            ts.add(i); // 일단 이러면 중복제거가 된다
        }
        if(ts.size() >= nums.length/2){
            answer = nums.length/2;
        }else{
            answer = ts.size();
        }
        
        return answer;
    }
}

분류는 Hash다. TreeSet으로 중복제거해서 최대 가지수를 뽑았다.

해시로 분류된 이유는 Set 자료구조를 이용해서 푸는 것 때문일 것으로 추정된다..

# 추가 공부

TreeSet 자료구조

import java.util.*;

TreeSet<Integer> ts = new TreeSet<Integer>();
TreeSet<Integer> tsInit = new TreeSet<>(Arrays.asList(1,2,3,3,3));

ts.add(1);
ts.add(2);
ts.add(2);
ts.add(3);
ts.remove(2);
ts.size(); // 크기
ts.clear(); // 전체 날리기

Treeset은 기본으로 레드블랙트리가 적용되어있는 Set 자료구조다. 

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드블랙트리는 부모노드 기준으로 작은게 왼쪽으로, 큰게 오른쪽으로 간다. 그래서 ts.first()는 트리에서 가장 작은 값, ts.last()는 트리에서 가장 큰 값을 출력한다. 오름차순 정렬이 기본이라고 할 수 있다.

그래서 그냥 new 로 만드는게 아니라 Collections.reverseOrder() 해주면 내림차순 정렬이 되는 TreeSet이 생성된다.

TreeSet<Integer> ts = new TreeSet(Comparator.reverseOrder());

Collection인데, Set구조라 순회가 좀 불편하다. Iterator로 감싸서 순회해야된다.

Iterator it = ts.iterator();
while(iter.hasNext()){
    System.out.print(it.next() + "\n");	
}

정렬된 순서대로 iterator가 순회한다.

HashSet을 쓰면 요소가 정렬되지않아있지만 해시테이블을 사용해서 O(1)의 속도를 자랑한다. 근데 TreeSet을 쓰면 정렬되어있어서 만약 범위검색 같은 게 필요하면 이걸 써야된다. O(logN)이거나 amortized O(1)이기 때문에 입력이 입력이 엄청 커서 조회에 시간이 막 걸리는 게 아니라면 TreeSet을 써도 될 것 같다.

범위검색은 headSet, tailSet을 쓴다. 이게 신세계다.

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4);
numbers.add(5);
numbers.add(6);

// headSet() 예시
System.out.println("headSet(4): " + numbers.headSet(4));
System.out.println("headSet(4, true): " + numbers.headSet(4, true));

// tailSet() 예시
System.out.println("tailSet(4): " + numbers.tailSet(4));
System.out.println("tailSet(4, false): " + numbers.tailSet(4, false));

headSet은 주어진 요소보다 작은 범위의 부분집합을 반환한다. 요소를 포함하고 싶으면 true를 같이 넣어주면 된다.

tailSet은 주어진 요소보가 크거나 같은 범위의 부분집합을 반환한다. 그래서 요소가 포함되어있는데, false를 넣어주면 시작 점이 제외된다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!

@Composable 과 Recomposition, 그리고 Modifier

@Composable
fun Greeting(name: String, modifier: Modifier = Modifier) {
    Text(
        text = "Hello $name!",
        modifier = modifier
    )
}

컴포저블 어노테이션이 붙은 함수는 UI를 생성하고, 관리할 수 있는 함수가 된다. 이 어노테이션이 붙은 함수는 컴파일러가 따로 처리를 하고, 런타임때 통합하기 위해 코드가 따로 생성된다. 중요한 점은 UI를 생성하는데, return형식이 아닌 emit 형식이어서 반환값이 따로 없다는 점이다. 

UI를 구성하는 요소이기 때문에 Recomposition에 대한 개념도 엮여있다. 데이터가 변경되면 Compose는 새 데이터로 Composable함수를 다시 실행하여 업데이트된 UI를 만든다. 경우에 따라 필요한 부분만 UI 업데이트해서 성능을 최적화해주는데, 객체의 reference만 비교하는게 아니라 내용까지 비교해서 내용이 같은경우 따로 재구성을 하지 않는다. 그럼 필요한 부분만 어떻게 감지할까? 그건 상태 객체에 달려있다. MutableState, State로 감싸진 상태객체가 있는데, 얘네가 UI recomposition을 트리거하는 객체들이다.

이 객체들은 값 변경이 발생할 때 Compose 시스템이 알 수 있다. 또 remeber가 붙은 함수를 사용하면 이전 연산결과를 가져와서 사용하는게 가능하기 때문에 리컴포지션을 방지하는 효과가 있다.

Column, Row, Box 컴포저블은 모두 컨테이너다.

@Preview(showBackground = true)
@Composable
fun UserProfile() {
    Column {
        Text("유저")
        Text("abcd@a.b")
        var likes by remember { mutableStateOf(0) }
        Text("Likes: $likes")
        Button(onClick = { likes++ }) {
            Text("Like")
        }
    }
}

@Preview는 정적 화면을 미리 보여주는 어노테이션으로, 실 기기 화면처럼 보고싶다면 아래와 같이 설정하면 된다.

@Preview(showBackground = true, widthDp = 320)

코드로 돌아와서, 재구성이 되는 부분은 `Text("Likes: $likes")` 이부분이다. Text로 Like가 적혀있는 Button을 누르면 likes값이 증가해서 이 TextComposable이 재구성된다. UserProfile Composable 전체가 재구성되지는 않는다. 여기서는 따로 안만들었지만, like를 변경했는데 이전과 값이 같다면 재구성이 일어나지 않는다.

`var likes by remember { mutableStateOf(0) }`

이 부분이 이번 Composable의 핵심이다. by로 위임시킨것부터 봐야된다.

`val likes = remember { mutableStateOf(0) }`

이게 위임시키기 전 형태다.  MutableState값을 remember로 감싸서 likes 에 할당한 형태로, 값에 접근할때마다 .value 프로퍼티를 사용해야된다. get, set이 MutableState 객체 안에 있는데 거기게 value 프로퍼티로 접근한다고 보면 된다. LiveData를 사용할 때 봤던 경우다. remember로 감싸게 되면,  recomposition 사이에서 상태를 유지할 수 있다. 초기화 할 때만 람다 내부의 코드를 실행하고, 재구성이 발생할 때는 저장된 값을 반환하는 형태다. 따라서 매번 MutableState객체를 배정해서 쓰는게 아니라 remeber된 걸 꺼내서 쓰게 된다.

by로 위임하게 되면, get, set에 접근하기 위해 value 프로퍼티를 사용하던 귀찮은 방법을 사용하지 않아도 된다. 바로 likes로 사용가능하다.  `likes.value = likes.value+1` 이 `likes++` 로 바뀌었다고 생각하면 체감될 것이다.

# Modifier

`Modifier`는 Compose에서 거의 xml에서 할수있는 모든 것들을 정의하는 객체이며, 따로 지정하지않으면 기본 modifier가 사용된다. 사용할 때는 체이닝을 쓴다.

Modifier
    .padding(16.dp)
    .background(Color.Gray)
    .clickable { /* 클릭 동작 */ }

컴포즈에서는 margin을 지정하지 않고 padding만 지정한다. margin을 명시적으로 하는게 아니라 offset으로 위치 조정만 한다고 생각하면 되겠다. match_parent같은 건 `fillMaxWidth, fillMaxHeight, fillMaxSize` 같은걸로 접근하면 된다. 클릭리스너도 여기서 달면 된다.

근데 xml과 아주 다른점이 존재한다. 체이닝 순서가 결과를 다르게 만든다는 점이다.

@Preview(showBackground = true)
@Composable
fun TestBox() {
    Column {
        Box(modifier = Modifier
            .size(200.dp)
            .padding(40.dp)
            .background(Color.Red)) {
        }
        Box(modifier = Modifier.size(0.dp, 20.dp))
        Box(modifier = Modifier
            .padding(40.dp)
            .size(200.dp)
            .background(Color.Red)) {
        }
    }
}

사이즈를 지정하고 패딩을 준것과, 패딩을 먼저 주고 사이즈를 지정한 것은 아예 다르다. 전자는 컨텐츠 크기가 160, 후자는 200이다.

then을 사용해서 조건부로 다른 Modifier를 붙이는 작업도 가능하다.

@Preview(showBackground = true)
@Composable
fun TestBox() {
    var isSelected by remember { mutableStateOf(false) }

    Column {
        Box(
            modifier = Modifier
                .size(200.dp)
                .padding(40.dp)
                .background(Color.Red)
        ) {
        }
        Box(modifier = Modifier.size(0.dp, 20.dp))
        Box(
            modifier = Modifier.padding(40.dp)
                .size(200.dp)
                .then(
                    if (isSelected) Modifier
                        .background(Color.Blue)
                    else Modifier
                        .background(Color.Red)
                )
        )
        Button(onClick = { isSelected = !isSelected }) {
            Text(if (isSelected) "선택됨" else "선택 안됨")
        }
    }
}

이렇게 하면 버튼을 누를때, isSelected값이 토글되면서 하단 Box의 Modifier가 같이 토글된다.

# Surface 

@Composable
fun Greeting(name: String, modifier: Modifier = Modifier) {
    Surface(color = MaterialTheme.colorScheme.primary) {
        Text(
            text = "Hello $name!",
            modifier = modifier
        )
    }
}

컴포즈에서 Surface는 컴포저블 컨테이너 중 하나다. 근데 이제 Material Design을 곁들인 형태로, 알아서 해주는 기능이 많은 컴포넌트다. 머터리얼 디자인에서 나온 컴포넌트 답게, color에 primary로 지정하면, colorScheme에 존재하는 primary 대응하는 onPrimary색깔로 컴포넌트 대비를 이뤄서 가독성을 보장한다. 

# 호이스팅과 상태관리

웹 개발에서 처음 접한 단어인데, 컴포즈에도 등장한다.

Composable 함수에서 여러 곳에 쓰이는 상태는 공통 상위항목에 위치해야된다. 이걸 상태 호이스팅이라고 말하며 하위 컴포저블에서 상태 재사용이 간편해서 좋은 방법이다. Datasource가 이런 곳에 속한다.

flowchart LR
    B(상태제공 - MutableStateOf 객체)
    B --> D[A]
    B --> E[B]
    B --> F[C]

상태값을 상위요소랑 공유하는 게 아니라, 상태값에 액세스 해야되는 공통 상위 요소 쪽으로 상태값을 이동시키면 된다.

즉 단방향성으로 상위 요소는 하위 요소로 상태를 전달하고, 하위 요소는 그걸 받아 이벤트를 상위 요소로 제공하는, 거의 웹 개발에서의 호이스팅과 동일한 형태다. 간단한 카운터 코드랑 같이 보자.

@Composable
fun ParentComponent() {
    var count by remember { mutableStateOf(0) }
    
    HoistedCounter(
        count = count,
        onIncrement = { count++ }
    )
}

최상위 컴포저블이다. 여기서 count를 관리한다.

@Composable
fun HoistedCounter(
    count: Int,
    onIncrement: () -> Unit
) {
    Column {
        Button(onClick = onIncrement) {
            Text("증가증가")
        }
        Text("개수: $count")
    }
}

상태를 Parent한테 받고, 상태를 관리할 동작을 람다로 넘겨 받는다. 그래서 이 호이스팅 받는 컴포저블에서는 클릭이벤트만 관리하게 된다. 어딘가 익숙하게 느껴진다면, recyclerview adapter를 사용할 때 클릭이벤트를 이렇게 넘긴 형태가 있어서다. 호이스팅이 상태관리를 단방향으로 해주긴 하지만, 너무 depth가 깊어지면 리컴포지션이 발생할 수도 있어서 필요한 부분만 파편화해서 상태를 좀 더 작은 단위로 관리하는 기술이 필요하다.

리컴포지션을 최소화하기 위해 이전에 사용했었던 remember를 선택할 수도 있고, key나 derivedStateOf를 사용해서 캐싱해두는 방식으로 좀 더 성능을 끌어올릴 수 있다. remeber를 사용할 때 주의할 점은, 컴포저블이 컴포지션에 유지되는 동안에만 작동한다는 것이다. 그래서 화면회전과 같은 이벤트가 발생하면 날아간다. 그때는 rememberSaveable을 써주면 끝난다.

val processedItems by remember(items) {
    derivedStateOf { items.map { it.uppercase() } }
}

이렇게 하면 items에서 변경이 있을때만 map 작업을 수행한다. 람다에 remember를 사용해서 매 리컴포지션 마다 새로운 람다가 생성되는걸 막는 방향으로 최적화를 할 수도 있다.

key가 중요한데, 컴포즈는 key 값으로 이전 컴포지션, 새 컴포지션의 차이를 구분한다. 그래서 동일한 키를 가지고 있으면 재사용되고, 아니라면 새로 생성한다. 아래 코드처럼 리스트가 주어질 때 사용하면 좋다. 만약 매번 리스트 내의 순서가 변경되면 성능이 떨어질 수 도 있다. key를 쓰면 그것만 업데이트 하면 돼서 리컴포지션 없는 효율적인 작업이 가능하다.

@Composable
fun KeyTestList(items: List<String>) {
    Column {
        items.forEachIndexed { index, item ->
            key(index) {
                Text(item)
            }
        }
    }
}

@Composable
fun MultipleKeysExample(items: List<Item>) {
    Column {
        items.forEach { item ->
            key(item.id, item.category) {
                ItemComponent(item)
            }
        }
    }
}

키를 몇개 조합해서 복합키로 쓸수도 있다. 이런 상태관리는 대규모 리스트 같은 곳에서 빛을 발하는데, 지금부터 알아보자. 

# `LazyColumn, LazyRow, LazyVerticalGrid...`

이 친구들은 완벽하게 RecyclerView의 상위호환이다. 코드 몇줄로 기존의 RecyclerViewAdapter를 완전히 대체해준다.

@Composable
private fun Greetings(
    modifier: Modifier = Modifier,
    names: List<String> = List(1000) { "$it" }
) {
    LazyColumn(modifier = modifier.padding(vertical = 4.dp)) {
        items(items = names) { name ->
            Greeting(name = name)
        }
    }
}

아이템 1000개짜리 리사이클러뷰가 완성됐다. RecycerView랑 동작방식이 좀 차이가 있는데, RecyclerView가 아이템 뷰를 계속 재활용하는 반면 Lazy 시리즈들은 그냥 새 아이템 컴포저블을 emit하는 방식이다. 아이템의 상태도 고정하고 싶다면 인덱스와 해당 아이템의 상태값을 rememberSaveable로 만들어서 관리하면 된다.

아까 key를 여기에 적용하면 아래처럼 쓸 수 있다.

@Composable
fun UserList(users: List<User>) {
    LazyColumn {
        items(users, key = { user -> user.id }) { user ->
            UserItem(user)
        }
    }
}

각 항목의 고유 키를 user의 id로 지정해주는 코드다.

@Composable
fun LazyColumnTest(items: List<String>) {
    LazyColumn(
        contentPadding = PaddingValues(horizontal = 16.dp, vertical = 8.dp),
        verticalArrangement = Arrangement.spacedBy(4.dp)
    ) {
        item {
            Text("Header")
        }
        
        items(items) { item ->
            Text(text = item)
        }
        
        itemsIndexed(items) { index, item ->
            Text("Item at $index is $item")
        }
        
        item {
            Text("Footer")
        }
    }
}

items에 아이템들이 들어가고, 그전에 있는 item은 헤더, 그 다음에 있는 item은 푸터다. 심지어 items를 여러개 넣으면 자동으로 concat recycerview다. itemsIndexed를 사용하면 인덱스번호와 같이 다룰 수 있어서 조금 더 개발 친화적이다. 

좀 더 충격적인건, LazyListState를 써서 list state를 받고, 그걸 기준으로 터무니 없이 쉽게 무한스크롤을 구현할 수 있다는 점이다.

val listState = rememberLazyListState()

LazyColumn(state = listState) {
	...
}
LaunchedEffect(listState) {
    snapshotFlow { listState.firstVisibleItemIndex }
        .collect { index ->
            if (index > items.size - 10) {
                items += List(20) { "새 아이템 ${items.size + it}" }
            }
        }
}

이렇게 무한스크롤 구현이 끝났다. 지금은 그냥 하드코딩으로 아이템을 늘려줬지만, 람다로 상위 컴포저블에서 아이템들을 받아오는 형태가 자주 쓰인다고 한다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!