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

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

처음에 문제를 읽고 너무 단순하다고 생각했다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        int len = citations.length;
        for(int i=0; i<len; i++){
            int tmpH = citations[i];
            // 현재 위치 포함해서 남은 논문 편 수
            int left = len - i;
            if(tmpH > left){
                break;
            }else{
                answer = tmpH;
            }
        }
            
        return answer;
    }
}

정렬해서, 처음부터 각 원소를 돌면서 남은 논문 편수를 비교해 종료조건을 설정해주면 되는 게 아닌가? 라고 생각했다.

이러면 문제가, 모든 논문의 인용횟수가 len 보다 크다면 바로 끝나버린다. 그리고 H-index의 정의를 제대로 반영하지 못했다.

"h번 이상 인용된 논문이 h편 이상"이라는 문장이 그건데, 나는 현재 인용된 논문 횟수와 단순히 남은 논문 수를 기준으로 비교하고 있어서 틀린 답이 나올 수 밖에 없다.

인용횟수가 중심이 아니라, 증가하는 H-index에 맞는 인용 조건을 찾는게 문제 해답이었다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        ArrayList<Integer> arr = new ArrayList();
        for(int c: citations){
            arr.add(c);
        }
        arr.sort(Collections.reverseOrder());

        int len = citations.length;
        for(int i=0; i<len; i++){
            int tmpH = arr.get(i);
            if (tmpH < i + 1) {
                break;
            } else {
                answer = i + 1;
            }
        }
        
        return answer;
    }
}

정렬 순서부터 바꿨다. 아예 인용횟수가 많은 논문 부터 보게 하는 것이다.

종료 조건은 인용횟수가 h-index 후보 보다 작아질 때다. 이렇게 하면 i번째 논문을 확인할 때, 이미 i편의 논문이 현재 논문 이상으로 인용되었음을 알 수 있다. 오름차순 정렬을 해버리면 h-index 조건에 맞는 지 검증하는 로직이 하나 더 필요한데, 내림차순으로 하면 보장되어있어서 더 효율적이다.

조건이 단순했는데 말이 좀 모호하게 되어있어서 애먹었던 문제다. 처음 틀리고서 왜 틀렸는 지 감이 안잡혔다.

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

새로 시작한 프로젝트에서는 멀티모듈의 장점을 더 극대화 하기 위해서 feature 별로 모듈을 모두 나누고 있다. core도 합쳐서 쓰던걸 data, network, ui의 형태로 다 분리해서 사용 중이다. 이렇다보니 매번 build.gradle.kts 파일에 똑같은 코드들을 넣어줘야 했는데, 이 부분이 너무 불편해서 방법을 찾아보던 중 build-logic이라는 것을 발견했다.

version-catalog와 같이 사용할 수 있는 도구로 빌드에 필요한 공통 로직들을 따로 빼내어 관리할 수 있는 도구로, 지금은 해보지 않았지만 debug, release 모드를 나눠서 빌드 내용을 분리할 수 있는 기능도 갖고 있다고 한다.

나는 Now in Android 를 교보재로 build-logic을 구현했다.

폴더 구조다. build-logic 자체는 따로 build.gradle.kts를 갖지 않고 convention 모듈에서 해당 파일을 관리한다. build-logic에는 `settings.gradle.kts`를 생성해서 이걸 build할때 가져가도록 세팅한다.

build-logic을 만들고, `settings.gradle.kts` 를 아래처럼 작성하자.

dependencyResolutionManagement {
    repositories {
        google()
        mavenCentral()
    }
    versionCatalogs {
        create("libs") {
            from(files("../gradle/libs.versions.toml"))
        }
    }
}

rootProject.name = "build-logic"
include(":convention")

build-logic 자체는 그냥 directory로 만들고, convention 모듈만 따로 만들어주면 된다. 프로젝트에 있는 버전 카탈로그 파일을 가져와서 libs로 이름 붙이는 코드가 들어있다. 모듈을 만드는 도구로 만들면, Project 수준의 `settings.gradle.kts` 파일에 include 되어있을텐데, 이걸 삭제해줘야한다. build-logic모듈은 프로젝트가 빌드할 필요없는 모듈이고, 빌드에 사용될 모듈이기 때문이다.

그래서 project 수준 gradle을 보면 아래와 같다.

pluginManagement {
    includeBuild("build-logic")
    ... 생략
}

rootProject.name = "DRTAA"

include(":app")
// ...

build-logic을 build때 사용하기 위해 `includeBuild`로 감싸줘야한다.

멀티모듈의 효율을 올려주기 위해 `gradle.properties`도 추가해준다.

org.gradle.parallel=true
org.gradle.caching=true
org.gradle.configureondemand=true

순서대로 보자.

병렬 build를 활성화 했고, 빌드 캐시를 사용하게 만들어서 이전 빌드 결과를 재사용해 변경사항이 없다면 더욱 빠른 빌드가 가능하다. configureondemand를 true로 하면 전체 gradle 빌드가 아니라 현재 태스크에 필요한 것만 빌드한다고 한다.

이제 내가 삽질을 가장 많이한 convention 모듈을 구현해보자.

import org.jetbrains.kotlin.gradle.dsl.JvmTarget

plugins {
    `kotlin-dsl`
}

group = "com.drtaa.convention"

java {
    sourceCompatibility = JavaVersion.VERSION_17
    targetCompatibility = JavaVersion.VERSION_17
}

kotlin {
    compilerOptions {
        jvmTarget = JvmTarget.JVM_17
    }
}

dependencies {
    compileOnly(libs.android.gradlePlugin)
    compileOnly(libs.kotlin.gradlePlugin)
}

tasks {
    validatePlugins {
        enableStricterValidation = true
        failOnWarning = true
    }
}

gradlePlugin {
    plugins {
        register("AndroidHiltPlugin") {
            id = "drtaa.plugin.hilt"
            implementationClass = "AndroidHiltConventionPlugin"
        }
        register("AndroidCorePlugin") {
            id = "drtaa.plugin.core"
            implementationClass = "AndroidCoreConventionPlugin"
        }
        register("AndroidCommonPlugin") {
            id = "drtaa.plugin.common"
            implementationClass = "AndroidCommonConventionPlugin"
        }
        register("AndroidCoreNetworkPlugin") {
            id = "drtaa.plugin.network"
            implementationClass = "AndroidCoreNetworkConventionPlugin"
        }
        register("AndroidFeaturePlugin") {
            id = "drtaa.plugin.feature"
            implementationClass = "AndroidFeatureConventionPlugin"
        }
    }
}

gradlePlugin 스코프안에 있는 게 내가 커스텀으로 만들 플러그인들이다. implementationClass는 실제로 내가 만든 class 파일이고, id로 사용하면 된다.

나는 AGP 8.5.0을 사용하고 있어서 jvm 타겟을 17 이상으로 해야된다. 이제 compileOnly에서 첫번째 삽질이 발생한다. 내 버전 카탈로그에는 저게 없는데, 어느 예시를 보더라도 저걸 사용하고 있다.

침착하게 아래 코드를 toml에 추가해주자. gradle 도구에 사용되는 플러그인 같은데 기본 toml 구성에는 빠져있기 때문에 추가해줘야한다,

[libraries]
android-gradlePlugin = { group = "com.android.tools.build", name = "gradle", version.ref = "agp" }
kotlin-gradlePlugin = { module = "org.jetbrains.kotlin:kotlin-gradle-plugin", version.ref = "kotlin" }

여기까지 마쳤으면, 이제 작업할 공간은 `build-logic/convention/src/main/kotlin` 이다.

다른 예제를 보면 Application(gradle 파일의 android 스코프)까지 build-logic에 넣고 있었는데 일단 나는 dependency 반복을 막는게 목적이라서 해당 부분은 넘기겠다.

기본 dependency만 일단 모아둔 파일 먼저 보자.

internal class AndroidCommonConventionPlugin : Plugin<Project> {
    override fun apply(target: Project) {
        with(target) {
            dependencies {
                add("implementation", libs.findLibrary("androidx.core.ktx").get())
                add("implementation", libs.findLibrary("androidx.appcompat").get())
                add("implementation", libs.findLibrary("material").get())
                add("implementation", libs.findLibrary("junit").get())
                add("androidTestImplementation", libs.findLibrary("androidx.junit").get())
                add("androidTestImplementation", libs.findLibrary("androidx.espresso.core").get())
                add("implementation", libs.findLibrary("timber").get())
            }
        }
    }
}

이 모듈 밖에서 사용하지 않을 것이기 때문에 internal로 선언하여 외부로 부터 공개를 막는다. 그리고 dependency 스코프에 들어갈 각 implementation 구문을 추가해준다. 여기서 아주 중요한 점이 있다. 버전 카탈로그에서 라이브러리 정보를 긁어올 때 사용하는 저 `libs`가 build-logic의 settings.gradle.kts에 있는 `create("libs")`일까? 아니다.

create("libs")는 libs라는 이름을 붙여서 원래 루트 수준 버전 카탈로그 내용을 사용해 새 버전 카탈로그를 생성하며 settings.gradle.kts 파일에서 사용할 수 있게 하는 것이고 `val Project.libs get()` 는 위에서 정의한 libs 버전 카탈로그에 접근할 수 있도록 한 코드다. 빌드 스크립트나 플러그인 코드 내에서 사용하려면 이 방법을 사용해야된다.

이거 때문에 2시간을 날렸다.

저 libs를 사용하기 위해 Project의 확장 프로퍼티를 만들어 주겠다.

val Project.libs
    get(): VersionCatalog = extensions.getByType<VersionCatalogsExtension>().named("libs")

이걸 사용하면 libs에 접근 가능하다. 이제 hilt도 한번 스크립트 화 해보자.

import extenstion.libs
import org.gradle.api.Plugin
import org.gradle.api.Project
import org.gradle.kotlin.dsl.dependencies

internal class AndroidHiltConventionPlugin : Plugin<Project> {
    override fun apply(target: Project) {
        with(target) {
            with(pluginManager){
                apply("com.google.dagger.hilt.android")
                apply("org.jetbrains.kotlin.kapt")
            }

            dependencies {
                add("kapt", libs.findLibrary("hilt.compiler").get())
                add("kapt", libs.findLibrary("androidx.hilt.compiler").get())
                add("implementation", libs.findLibrary("hilt.android").get())
            }
        }
    }
}

pluginManager로 지정해줘야 build.gradle.kts의 plugin 스코프에 들어간다. 주의할 점은 libs.findPlugin("").get()으로 접근하면 빌드가 안된다는 점이다. apply는 플러그인 id를 받아야되는데 get으로 접근하면 `Provider<PluginDependency>`를 제공해서 빌드에 실패한다.

libs를 활용하고 싶다면 아래처럼 바꿔야한다. 첫번째 get으로 Provider를 먼저 가져오고, 두번째 get으로 실제 플러그인 객체를 가져온 뒤, 그것에 대한 id를 가져오는 방식이다.

import extenstion.libs
import org.gradle.api.Plugin
import org.gradle.api.Project
import org.gradle.kotlin.dsl.dependencies

internal class AndroidHiltConventionPlugin : Plugin<Project> {
    override fun apply(target: Project) {
        with(target) {
            with(pluginManager){
                apply(libs.findPlugin("hilt.gradle.plugin").get().get().pluginId)
                apply(libs.findPlugin("kotlin.kapt").get().get().pluginId)
            }

            dependencies {
                add("kapt", libs.findLibrary("hilt.compiler").get())
                add("kapt", libs.findLibrary("androidx.hilt.compiler").get())
                add("implementation", libs.findLibrary("hilt.android").get())
            }
        }
    }
}

dependency는 implement나 kapt 같은 configure method로 객체 끌어다 쓰는 반면 plugin은 바로 사용하는 점 때문에 이런 차이가 발생한다.

이렇게 만든 플러그인들은 다른 플러그인을 정의할 때도 재사용 할 수 있다.

internal class AndroidFeatureConventionPlugin : Plugin<Project> {

    override fun apply(target: Project) {
        with(target) {
            with(pluginManager) {
                apply("drtaa.plugin.common")
                apply("drtaa.plugin.hilt")
                apply(libs.findPlugin("navigation.safe.args").get().get().pluginId)
            }

            dependencies {
                add("implementation", project(":core-data"))
                add("implementation", project(":core-ui"))
                add("implementation", project(":core-model"))
                add("implementation", libs.findLibrary("navigation.ui.ktx").get())
                add("implementation", libs.findLibrary("navigation.fragment.ktx").get())
                add("implementation", libs.findLibrary("androidx.hilt.navigation.fragment").get())
                add("implementation", libs.findLibrary("datastore.preferences").get())
                add("implementation", libs.findLibrary("glide").get())
                add("implementation", libs.findLibrary("lifecycle.runtime.ktx").get())
                add("implementation", libs.findLibrary("lifecycle.extensions").get())
                add("implementation", libs.findLibrary("coroutines.android").get())
                add("implementation", libs.findLibrary("coroutines.core").get())
            }
        }
    }
}

그럼 얼마나 보일러 플레이트가 줄었을까?

plugins {
    alias(libs.plugins.android.library)
    alias(libs.plugins.jetbrains.kotlin.android)
    alias(libs.plugins.hilt.gradle.plugin)
    alias(libs.plugins.kotlin.kapt)
    alias(libs.plugins.navigation.safe.args)
}

...

dependencies {
// modules
    implementation(project(":core-data"))
    implementation(project(":core-ui"))
    implementation(project(":core-model"))

    implementation(libs.androidx.core.ktx)
    implementation(libs.androidx.appcompat)
    implementation(libs.material)
    testImplementation(libs.junit)
    androidTestImplementation(libs.androidx.junit)
    androidTestImplementation(libs.androidx.espresso.core)

    implementation(libs.bundles.feature.default)

    kapt(libs.hilt.compiler)
    kapt(libs.androidx.hilt.compiler)
}

이랬던 코드가 이렇게 바뀌었다.

plugins {
    alias(libs.plugins.android.library)
    alias(libs.plugins.jetbrains.kotlin.android)
    id("drtaa.plugin.feature")
}

...

dependencies {

}

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

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

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

import java.util.*;

class Solution {
    static boolean[] v; 
    static String[] out;
    static int n;
    static TreeSet<String> pq = new TreeSet<String>(Collections.reverseOrder());
    
    public static void perm(int[] num, int depth){
        if(depth == n){
            StringBuilder sb = new StringBuilder();
            for(String item: out){
                sb.append(item);
            }
            pq.add(sb.toString());
            return;
        }
        for(int i=0; i<num.length; i++){
            if(!v[i]){
                //방문하지 않았으면 다음위치에 넣기
                v[i] = true;
                out[depth] = Integer.toString(num[i]);
                perm(num, depth+1);
                v[i] = false;
            }
        }
    }
    public String solution(int[] numbers) {
        String answer = "";
        // 순열로 일단 만들 수 있는 모든 경우의수를 만들어서, PriorityQueue에 넣기
        n = numbers.length;
        v = new boolean[n];
        out = new String[n];
        perm(numbers, 0);
        
        answer = String.valueOf(pq.first());
        return answer;
    }
}

처음에는 순열로 접근하면 될 줄 알았다. TreeSet을 사용하기 전에는 우선순위 큐를 써서 만들었다. 근데 input을 보면

numbers 길이가 100000인데, 이러면 순열생성 시간복잡도가 n!라서 무조건 시간초과, 메모리 초과가 발생한다.

방법을 바꿔야된다. 

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] strNumbers = new String[numbers.length];
        
        for(int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }
        
        Arrays.sort(strNumbers, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return (b + a).compareTo(a + b);
            }
        });
        
        if(strNumbers[0].equals("0")) return "0";
        
        StringBuilder answer = new StringBuilder();
        for(String s : strNumbers) {
            answer.append(s);
        }
        
        return answer.toString();
    }
}

String으로 다 바꾼다음, Comparator를 새로 정의하는 방식을 사용했다. 이런 문제를 몇번 풀었는데 이렇게 하는 건 처음이다...

# 추가 공부

`Arrays.sort(arr, new Comparator<T>(){ })`

Arrays.sort(strNumbers, new Comparator<String>() {
    @Override
    public int compare(String a, String b) {
        return (b + a).compareTo(a + b);
    }
});

오랜만에 Comparator를 사용하니까 진짜 생각이 안났다.

Arrays는 배열을 파라미터로 받아서 처리하는데, 안쓰면 계속 까먹어서 일단 적어둔다. 같을 때(기존 순서 유지), 작을 때(-1), 클 때(1)를 각각 기준으로 두고 정렬 순서를 결정한다.

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

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

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

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        LinkedList<Character> stack = new LinkedList();
        for(int i=0; i<s.length(); i++){
            char tmp = s.charAt(i);
            if(stack.isEmpty()){
                if(tmp == ')') return false; 
                stack.add(tmp);
            }
            else if(stack.peekLast() != tmp){
                stack.pollLast();
            }else{
                stack.add(tmp);
            }
        }
        if(stack.size() != 0){
            answer = false;
        }

        return answer;
    }
}

스택 문제 하면 떠오르는 전형적인 괄호검사 문제다.

몇 달전 HSAT문제에도 괄호문제가 나왔었는데 그 때는 예외처리를 꼼꼼하게 안해서 틀린 기억이 있다...

# 추가 공부

ArrayDeque

ArrayDeque을 쓰면 양방향 큐 구현체이기 떄문에 큐나 스택 모두 가능하다. 

ArrayDeque<String> deque = new ArrayDeque<>();

deque.addFirst("First");     // 앞쪽에 추가
deque.addLast("Last");       // 뒤쪽에 추가
deque.offer("Offered");      // 뒤쪽에 추가 (큐처럼 사용)
deque.push("Pushed");        // 앞쪽에 추가 (스택처럼 사용)
deque.peekFirst();
deque.peekLast();
deque.pollFirst(); // 기본동작임
deque.pollLast();
deque.poll(), deque.pop(); // 첫번째 요소 제거 -> push가 스택처럼 쓰인다는 이유

추가, 제거 하는 경우만 잘 익히면 된다.

First, Last를 쓰는게 아무래도 좀 알아보기 쉬워서 자주 썼는데, 앞으로도 해당 메서드를 쓸 것 같다.

deque.contains("1");
deque.clear();
deque.removeIf(e -> e % 2 == 0); // 짝수인 요소 모두 제거

contains도 있어서 값이 큐나 스택에 포함되어있는 지 바로 알 수 있다.

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