오늘 강의를 들으면서 .class를 왜 사용하는걸까? 라는 의문이 들었다.

사실 안드로이드 코드를 짤 때 intent 이후 특정 Activity를 호출하기 위해 ::class.java라는 코드를 썼었는 데, 그때는 왜 쓰는지 몰랐다.

이번에는 그냥 넘어가기 좀 그래서 알아보았다.

내가 궁금했던 부분은 @Configuration과 @Bean을 사용하여 Spring Container에 구현체를 Bean으로 등록한 이후 AnnotationConfigApplicationContext에 AppConfig.class를 넘겨줄 때 왜..? 라는 생각이 들었다.

코드는 다음과 같다.

ApplicationContext applicationContext = new AnnotationConfigApplicationContext(AppConfig.class);

1. AnnotationConfigApplicationContext()에서 받는 인자는 무엇인가?

AnnotationConfigApplicationContext 코드를 보면 다음과 같이 되어 있다.

public AnnotationConfigApplicationContext(Class<?>... componentClasses) {
        this();
        register(componentClasses);
        refresh();
}

Class라는 Arguement를 받고 있고, 이 componentClasses를 register()라는 method로 등록하는 것을 확인할 수 있다.

그러면 .class 객체를 넘기는 데, instance를 넘기는 건지? 아니면 다른 특정값을 넘기는건지 생각이 든다.

아! 근데 확실한 것은 instance를 넘기진 않는다. 왜냐하면 new 키워드가 없기 때문이다. 그럼 AppConfig.class가 곧 Class Type이라는 건데, Class는 무엇인가?

2. Class는 무엇인가?

Class는 다음과 같이 나타나 있다.

public final class Class<T> implements java.io.Serializable,
                              GenericDeclaration,
                              Type,
                              AnnotatedElement,
                              TypeDescriptor.OfField<Class<?>>,
                              Constable {
    private static final int ANNOTATION= 0x00002000;
    private static final int ENUM      = 0x00004000;
    private static final int SYNTHETIC = 0x00001000;

    private static native void registerNatives();
    static {
        registerNatives();
    }

    private Class(ClassLoader loader, Class<?> arrayComponentType) {
        // Initialize final field for classLoader.  The initialization value of non-null
        // prevents future JIT optimizations from assuming this final field is null.
        classLoader = loader;
        componentType = arrayComponentType;
    }

• 코드를 보면 public 생성자가 없다. 다 private으로 생성된다. 그러면, 해당 객체의 생성은 당연히 JVM이 알아서 통제한다.

• 따라서 거의 모든 Java의 자료형(참조, 원시 포함)은 Class 객체로 표현할 수 있다.

그러면 .class를 쓰면 어떻게 바뀌는가?

3 .class(::class.java)를 쓰면 어떻게 바뀌는가?

.class는 클래스 리터럴을 나타내는 특별한 표기법이다. 이 클래스 리터럴은 class의 메타정보를 갖고 있는 데, class 리터럴을 통해 해당 클래스의 메타 정보를 갖고 올 수 있다.

무엇인지는 좀 더 봐야하겠지만, 아래의 코드를 보면 어느 정도 감이 온다.

    @CallerSensitive
    public static Class<?> forName(String name, boolean initialize,
                                   ClassLoader loader)
        throws ClassNotFoundException
    {
        Class<?> caller = null;
        @SuppressWarnings("removal")
        SecurityManager sm = System.getSecurityManager();
        if (sm != null) {
            // Reflective call to get caller class is only needed if a security manager
            // is present.  Avoid the overhead of making this call otherwise.
            caller = Reflection.getCallerClass();
            if (loader == null) {
                ClassLoader ccl = ClassLoader.getClassLoader(caller);
                if (ccl != null) {
                    sm.checkPermission(
                        SecurityConstants.GET_CLASSLOADER_PERMISSION);
                }
            }
        }
        return forName0(name, initialize, loader, caller);
    }

forName이라는 method는 Class<?> 타입을 return하고 있다. 그러면 무엇을 리턴하는가?

어떤 클래스의 이름, 초기화, loader, caller를 담아 return하고 있다. 해당 정보가 바로 메타 정보로 사용되는듯 싶다.

java의 경우 .class를 사용하나, kotlin의 경우 ::class.java를 사용한다.

4. .class를 사용하면, 사용된 class의 instance가 생성되는가?

아니다. 생성되지 않는다. forName을 통해 해당 클래스의 메타정보만 갖고올 뿐 인스턴스가 생성되는 것은 아니다.

그러면 앞서 작성했던

ApplicationContext applicationContext = new AnnotationConfigApplicationContext(AppConfig.class);

는 kotlin에서 아래와 같이 사용하면 된다.

val applicationContext = AnnotationConfigApplicationContext(AppConfig::class.java)

결국 .class(::class.java)를 사용하는 이유는 해당 class의 메타 정보를 얻기 위해서 사용된다. .getClass()를 사용해도 같은 결과를 얻을 수 있으니, 참고하자.

프로젝트의 할인 정책이 만약에 정액 할인에서 정률 할인으로 바뀐다면 어떻게 될까?

기존의 할인 정책인 고정 할인(FixDiscountPolicy)이 정률(RateDiscountPolicy)로 바뀌어야 한다.

Java

해당 클래스는 이미 구현이 완료된 상태이며, 주문시 작동해야 한다.

그렇다면, 어떻게 해야할까?

import hello.core.discount.DiscountPolicy;
import hello.core.member.data.Member;
import hello.core.member.repository.MemberRepository;
import hello.core.order.data.Order;
import hello.core.order.service.OrderService;

public class OrderServiceImpl implements OrderService {

    private final MemberRepository memberRepository = new MemoryMemberRepository();
    private final DiscountPolicy discountPolicy = new FixDiscountPolicy;

    @Override
    public Order createOrder(Long memberId, String itemName, int itemPrice) {

        Member member = memberRepository.findById(memberId);
        int discountPrice = discountPolicy.discount(member, itemPrice);

        return new Order(memberId, itemName, itemPrice, discountPrice);
    }
}

기존의 OrderServiceImpl class를 보면, MemoryMemberRepository와 FixDiscountPolicy에 의존하고 있다.

이는 DIP(의존 역전 원칙)를 위반하고 있다. 따라서 RateDiscountPolicy인 정률 할인 클래스가 구현이 완료된다고 해도, OrderServiceImpl에 Field 주입을 진행해야 한다. 즉, OrderServiceImpl를 수정해야 하는 문제가 생겨버린다.

결국에는 처음부터 Achitecture를 잘못 설계해버려서 Order에 관여될 때 마다 관련된 모든 code를 수정해야 하는 번거로움이 생겨버린다.

그렇기 때문에, 지금 바로 class(구현체)가 아닌, interface 또는 abstract class에 의존할 수 있도록 DIP를 준수하도록 code를 수정해보자.

우선 Field로 구현체를 주입하고 있는 Code를 다음과 같이 interface에 의존하도록 바꾸어보자.

import hello.core.discount.DiscountPolicy;
import hello.core.member.data.Member;
import hello.core.member.repository.MemberRepository;
import hello.core.order.data.Order;
import hello.core.order.service.OrderService;

public class OrderServiceImpl implements OrderService {

    private MemberRepository memberRepository;
    private DiscountPolicy discountPolicy;

    public OrderServiceImpl(MemberRepository memberRepository, DiscountPolicy discountPolicy) {
        this.memberRepository = memberRepository;
        this.discountPolicy = discountPolicy;
    }

    @Override
    public Order createOrder(Long memberId, String itemName, int itemPrice) {

        Member member = memberRepository.findById(memberId);
        int discountPrice = discountPolicy.discount(member, itemPrice);

        return new Order(memberId, itemName, itemPrice, discountPrice);
    }
}

이제 OrderServiceImpl class는 MemberRepository, DiscountPolicy interface에 의존하게 되었다.

위 코드는 interface 타입이 들어와 생성자를 생성하고 있으며, 해당 클래스를 주입해주면 된다.

어떻게 주입할 수 있을까?

답: 구현제 주입을 담당하는 class를 따로 만든다.

다음과 같이 AppConfig class를 만들어 구현제만을 관리하면 된다.

import hello.core.discount.DiscountPolicy;
import hello.core.discount.implement.FixDiscountPolicy;
import hello.core.member.repository.MemberRepository;
import hello.core.member.repository.MemberRepositoryImpl;
import hello.core.member.service.MemberService;
import hello.core.member.service.MemberServiceImpl;
import hello.core.order.implement.OrderServiceImpl;
import hello.core.order.service.OrderService;

public class AppConfig {


   /*...*/

    public OrderService orderService() {
        return new OrderServiceImpl(
                memberRepository(),
                disiscountPolicy()
        );
    }

    private MemberRepository memberRepository() {
        return new MemberRepositoryImpl();
    }

    private DiscountPolicy disiscountPolicy() {
        return new FixDiscountPolicy();
    }
}

위 코드를 살펴보면, OrderService 타입인 OrderServiceImpl를 return할 때, memberRepository(), disiscountPolicy()를 주입하고 있으며, 해당 method는 각각의 구현체를 return 하고 있다.

이제 원래의 목적인 할인 정책의 변동이 찾아왔을 때, FixDiscountPolicy()를 RateDiscountPolicy()로 바꾼다면, 곧바로 적용되는 것을 확인할 수 있다.

이렇게 Field가 아닌 생성자를 통해 주입하는 방식을 생성자 의존관계 주입이라고 한다.

Kotlin

아래는 Kotlin으로 바꾸었을 때의 코드이다.

kotlin으로 생성자 주입을 진행했을 때는 다음과 같이 OrderServiceImpl를 만들어주면 된다.

import hello.corekotlin.discount.DiscountPolicy
import hello.corekotlin.member.repository.MemberRepository
import hello.corekotlin.order.data.Order
import hello.corekotlin.order.service.OrderService

class OrderServiceImpl(
    private val memberRepository: MemberRepository,
    private val discountPolicy: DiscountPolicy
): OrderService {

    override fun createOrder(memberId: Long, itemName: String, itemPrice: Int): Order {
        val member = memberRepository.findById(memberId)
        val discountPrice = discountPolicy.discount(member, itemPrice)

        return Order(
            memberId,
            itemName,
            itemPrice,
            discountPrice
        )
    }
}

위 코드를 java로 Decompile했을 때, 생성자가 자동으로 만들어진다.

또한 AppConfig는 다음과 같다.

import hello.corekotlin.discount.DiscountPolicy
import hello.corekotlin.discount.implement.RateDiscountPolicy
import hello.corekotlin.member.repository.MemberRepository
import hello.corekotlin.member.repository.MemoryMemberImpl
import hello.corekotlin.member.service.MemberService
import hello.corekotlin.member.service.MemberServiceImpl
import hello.corekotlin.order.implement.OrderServiceImpl
import hello.corekotlin.order.service.OrderService

class AppConfig {

    /*...*/

    fun orderService(): OrderService = OrderServiceImpl(
        memberRepositoy(),
        discountPolicy()
    )

    fun memberRepositoy(): MemberRepository = MemoryMemberImpl()

    fun discountPolicy(): DiscountPolicy = RateDiscountPolicy()

}

오늘은 공부를 하는 도중에 기록했으면 좋겠다고 생각한 것이 있어 글을 작성하게 되었습니다.

현재 김영한님의 스프링 핵심 원리 - 기본편에서 주문과 할인 도메인 실행과 테스트를 듣고 있습니다. 여기서 할인 청책 테스트 코드를 작성하는 부분에서 자바코드를 kotlin으로 바꾸면서 진행하고 있는데요.

여기서는 코틀린의 scope function을 통해 간단히 자바 Test Code를 코틀린 Test Code로 바꾸어볼게요.

이번 Test는 단순히 정률 할인 정책 Class가 잘 작동하고 있는지 알아보는 Test입니다.

Java Code

import hello.core.member.data.Grade;
import hello.core.member.data.Member;
import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

class RateDiscountPoilcyTest {

    RateDiscountPoilcy rateDiscountPoilcy = new RateDiscountPoilcy();

    @Test
    @DisplayName("VIP는 10% 할인이 적용되어야 한다.")
    void vip_o() {
        //given
        Member member = new Member(
                1L,
                "memberA",
                Grade.VIP
        );
        // when
        int discount = rateDiscountPoilcy.discount(member, 10000);

        // then
        Assertions.assertThat(discount).isEqualTo(1000);
    }


    @Test
    @DisplayName("VIP가 아니면, 할인이 적용되면 안 된다.")
    void vip_x() {
        // Given
        Member member = new Member(
                1L,
                "memberA",
                Grade.BASIC
        );
        // When
        int discount = rateDiscountPoilcy.discount(member, 10000);

        // Then
        Assertions.assertThat(discount).isEqualTo(0);
    }
}

위 코드의 흐름은 정말 단순하고 이해하기 쉽죠.

1. RateDiscountPoilcy를 주입해줍니다. (따라서 RateDiscountPoilcyTest Class는 RateDiscountPoilcy Class에 의존하고 있습니다.)

2. Member 객체를 정의합니다.

3. rateDiscountPoilcy에 member와 가격(price)를 던져줍니다.

4. 반환 받은 dicount를 Assertions에 던져 실제 금액과 예상 금액이 맞는지 확인합니다.

그래서 VIP와 BASIC 2가지의 카테고리에 대한 테스트 함수 모두 같은 로직으로 흘러가고 있습니다.

그리고 아래는 제가 작성한 Kotlin Test Code 입니다.

Kotlin Code

import hello.corekotlin.member.data.Grade
import hello.corekotlin.member.data.Member
import org.assertj.core.api.Assertions
import org.junit.jupiter.api.Test

internal class RateDiscountPolicyTest {

    val rateDiscountPolicy = RateDiscountPolicy()

    @Test
    fun vip_o() {
        Member(
            1L,
            "memberA",
            Grade.VIP
        ).apply {
            Assertions
                .assertThat(rateDiscountPolicy.discount(this, 10000))
                .isEqualTo(1000)
        }
    }

    @Test
    fun vip_x() {
        Member(
            1L,
            "memberA",
            Grade.BASIC
        ).apply {
            Assertions
                .assertThat(rateDiscountPolicy.discount(this, 10000))
                .isEqualTo(0)
        }
    }
}

member 객체를 만들고 이를 apply로 바로 넘겨서 테스트를 진행!

이번 강의에서는 h2Database를 import 하는 과정에 대해 기록

Java건 Kotlin이건 Spring에서 h2Database를 연결할 때

다음과 같은 과정만 거치면 된다.

1. h2Database 설치

2. h2Database 터미널 실행(절대 끄지 말 것)

3. Gradle import & Synchronize

   • Java

     
     implementation 'org.springframework.boot:spring-boot-starter-jdbc'
     runtimeOnly 'com.h2database:h2'

   • Kotlin

     
     implementation("org.springframework.boot:spring-boot-starter-jdbc")
     runtimeOnly("com.h2database:h2")

4. application.properties

   • Java & Kotlin

     
     spring.datasource.url=jdbc:h2:tcp://localhost/~/test
     spring.datasource.driver-class-name=org.h2.Driver

5. Run 확인

   • Java

   • Kotlin

- 끝 -

해당 내용은 배달의 민족 김영한님의 스프링 입문 - 코드로 배우는 스프링 부트, 웹 MVC, DB 접근 기술 강의를 듣고 작성되었습니다.

일반적으로 Java를 통해 TestCode DI를 진행할 때, Service와 같은 repo를 사용하게 만들기 위해 생성자를 통해 주입한다. 하지만, Kotlin의 경우 @Autowired를 사용하면, 굳이 DI를 진행하지 않아도 자동으로 만들어 준다.

혹시 몰라 Autowired로 연결된 2개의 클래스를 java로 Decompile 했는데, 아니나 다를까 @Autowired를 통해 생성자를 주입받고 있었다.

정말 가능한 기능이었다.

아래는 @Autowired를 통해 자동으로 생성자를 주입받은 kotlin code이다.

@SpringBootTest
internal class MemberServiceTest @Autowired constructor(
    private val memoryMemberRepository: MemoryMemberRepository,
    private val memberService: MemberService,
) {
    ...
}

그리고 이를 java code로 compile하면 다음과 같은 코드로 요약된다.

public class MemberServiceTest {
   private final MemoryMemberRepository memoryMemberRepository;
   private final MemberService memberService;

   ...

   @Autowired
   public MemberServiceTest(@NotNull MemoryMemberRepository memoryMemberRepository, @NotNull MemberService memberService) {
      Intrinsics.checkNotNullParameter(memoryMemberRepository, "memoryMemberRepository");
      Intrinsics.checkNotNullParameter(memberService, "memberService");
      super();
      this.memoryMemberRepository = memoryMemberRepository;
      this.memberService = memberService;
   }
}

kotlin에서 private val로 생성했기 때문에

java에서도 private final로 작성되었고

이를 외부에서 주입하고 있는 모습을 확인할 수 있다.

케빈 베이컨의 6단계 법칙, 문제풀러가기!

전형적인 데이크스트라 문제로 간단하게 풀었습니다.

graph 만들고 실제로 순회할 부분만 따로 보기 위해 peoples라는 set을 만들었습니다. 문제에서 범위만 주어졌을 뿐이지 실제로 존재하는 노드가 1부터 차례로 시작인지는 확실하게 읽지를 않아서 확실한 node만 담기 위한 목적으로 서용했습니다.

다음은 똑같습니다. 데이크스트라 알고리즘을 사용하되, peoples에 있는 원소만 순회하여 문제에서 말한 level(제곱수의 합)을 구합니다. 그 중 가장 낮은 것을 찾으면 끝입니다.

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
INF = int(1e9)
peoples = set()

for _ in range(M):
    one, two = map(int, input().split())
    graph[one].append((1, two))
    graph[two].append((1, one))
    peoples.add(one)
    peoples.add(two)

peoples = list(peoples)
peoples.sort()

friends = [[0 for _ in range(N)] for _ in range(N)]

def dijkstra(start):

    init_dist = [INF for _ in range(N+1)]
    init_dist[start] = 0
    HQ = []
    heappush(HQ, (0, start))

    while HQ:
        cost, now = heappop(HQ)

        if init_dist[now] < cost: continue

        for add_cost, nxt in graph[now]:
            new_cost = cost + add_cost

            if init_dist[nxt] > new_cost:
                init_dist[nxt] = new_cost
                heappush(HQ, (init_dist[nxt], nxt))

    return init_dist

number = INF
answer = -1

for i in range(1, N+1):
    summm = sum(dijkstra(i)[1:])
    if number > summm:
        answer = i
        number = summm

print(answer)   

전쟁 - 전투, 문제풀러가기!

그냥 전형적인 dfs 문제

상 하 좌 우로 돌면서 dfs를 진행하되 전역으로 중요 정보를 관리, hash를 사용하여 답안 도출!

간단하게 풀었습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [list(input().strip()) for _ in range(M)]
visited = [[False for _ in range(N)] for _ in range(M)]

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

dic = {
    "W": 0,
    "B": 0
}

def dfs(y, x):
    global num

    visited[y][x] = True

    for idx in range(4):
        nx, ny = x + dx[idx], y + dy[idx]

        if not (0 <= nx < N and 0 <= ny < M): continue
        if visited[ny][nx]: continue
        if graph[ny][nx] != target: continue
        num += 1
        dfs(ny, nx)


for i in range(M):
    for j in range(N):
        if visited[i][j]: continue
        target = graph[i][j]
        num = 1
        dfs(i, j)
        dic[target] += num**2

for value in dic.values():
    print(value, end = " ")

그럼 바로 바꾸다가 기록할 만한 것부터 시작!

1. Optional은 Kotlin에서 굳이 쓰지 않아도 된다.

코드를 바꾸면서 Java SpringBoot의 경우 Optional로 Null값을 컨트롤하는 것을 보았다. 근데 굳이 Kotlin에서는 Optional 객체를 사용하지 않아도 된다. 무엇보다 Java에서 Kotlin으로 refactoring하는 이유가 코드 가독성도 어느 정도 포함되어 있으면서, Kotlin 문법을 최대한 활용해야 하는데, 코드가 거의 같다면 Refactoring 할 이유가 없으니 말이다.

따라서 강의에 나온 Repository

import hello.hellospring.domain.Member;
import java.util.List;
import java.util.Optional;

public interface MemberRepository {

    Member save(Member member);

    Optional<Member> findById(Long id);

    Optional<Member> findByName(String name);

    List<Member> findAll();

}

는 Kotlin으로 다음과 같이 변경할 수 있다.

package kotlinhellospring.demo.repository

import kotlinhellospring.demo.domain.Member

interface MemberRepository {

    fun save(member: Member): Member

    fun findById(id: Long): Member?

    fun findByName(name: String): Member?

    fun findAll(): List<Member>
}

?를 통해 Null값을 체크할 수 있으니, 굳이 Optional을 사용하지 않아도 된다.

또한 Kotlin은 코드를 java로 바꾸면 생각보다 많은 내용이 함축되어 있다. 이는 kotlin → java로 변경하면 바로 보인다.

public interface MemberRepository {
   @NotNull
   Member save(@NotNull Member var1);

   @Nullable
   Member findById(long var1);

   @Nullable
   Member findByName(@NotNull String var1);

   @NotNull
   List findAll();
}

위 코드는 kotlin코드를 java로 Decompile 한 것이다. kotlin에서의 ? 여부에 따라 Java @Notnull @Nullable이 생성되는 것을 확인 할 수 있다.

그리고 MemberRepository 구현체 중 Optional이 사용된 부분을 보자.

java를 보면 다음과 같다.

    @Override
    public Optional<Member> findByName(String name) {

        return store.values()
                .stream()
                .filter(
                        member -> member.getName().equals(name)
                )
                .findFirst();
    }

위와 같은 코드를 Kotlin에서는 아래와 같이 표현할 수 있다.

    override fun findByName(name: String): Member? = store
        .values
        .find {
            member -> member.name == name
        }

kotlin의 find는 찾는 즉시 해당 첫번 째 객체를 반환한다.

그리고 또한 java처럼 Stream에 굳이 올릴 필요가 없다. kotlin 내부에서 모두 처리 가능하기 때문에.. 왜냐면 java에서 Stream으로 올리는 이유가 lambda를 사용하여 코드 가독성과 함수형 코드를 진행하기 위해서인데, kotlin은 모두 지원해주기 때문이다.

2. Kotlin Test 코드 작성 시 주의! Repository, Component Annotation으로 Bean 등록 및 SpringBootTest, Autowired Constructor Annotation 사용.

난.. 말하는 감자도 아닌, 말도 못하는 감자다.. 해당 문제로 인해 몇 시간 동안 답을 찾으러 Google과 씨름했다..ㅠ

그거슨 바로 아래의 오류...!!

No ParameterResolver registered for parameter in constructor.......

Kotlin에서는 왜인지는 모르겠는데, Bean 등록이 잘 안..ㅎㅎ

그래서 구현한 부분을 Bean으로 등록하려면 @Component를 사용하던, @Repository를 사용하던 @Service를 사용하던 Bean으로 등록해야 한다.

또한 Test할 클래스 위에 @SpringBootTest를 붙여준다. 거기에 사용할 Bean으로 등록된 구현체를 생성자로 활용하기 위해서는

@Autowired constructor를 지정해준다. 우선 java 코드는 다음과 같다.

Java Code

MemoryMemberRepository class 파일

import hello.hellospring.domain.Member;
import java.util.*;

public class MemoryMemberRepository implements MemberRepository {
    private static Map<Long, Member> store = new HashMap<>();
    private static long sequence = 0L;
    ...
}

java는 @SpringBootTest를 붙이지 않아도 된다. AutoWired할 필요도 없다. 또한 아래 처럼

MemoryMemberRepositoryTest class 파일

import hello.hellospring.domain.Member;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class MemoryMemberRepositoryTest {

    MemoryMemberRepository memoryMemberRepository = new MemoryMemberRepository();

    @Test
    public void save() {
        ...
        // 여기서 테스트를 그냥 진행해도 아무런 문제가 없다.
    }

}

굳이 Bean으로 등록하지 않아도 알아서 관리해준다.

이제 Kotlin을 보자.

Kotlin Code

MemoryMemberRepository class 파일

import kotlinhellospring.demo.domain.Member
import org.springframework.stereotype.Repository
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap

/**
 * bean으로 등록하여 관리하려면
 * Component 또는 Repository Annotation을 사용하여 등록하면 된다.
 * 테스트 코드가.. 안ㄷ...
 */
@Repository
class MemoryMemberRepository : MemberRepository {

    companion object {
        /**
         * 가변성 제어는 다음 시간에
         */
        var store: HashMap<Long, Member> = hashMapOf()
        var sequence: Long = 0L
    }
}

위 구현체를 Bean으로 등록하기 위해 @Repository 또는 @Componenet를 사용한다.

MemoryMemberRepositoryTest class 파일

import kotlinhellospring.demo.domain.Member
import org.junit.jupiter.api.Assertions
import org.junit.jupiter.api.Test
import org.springframework.beans.factory.annotation.Autowired
import org.springframework.boot.test.context.SpringBootTest

@SpringBootTest
class MemoryMemberRepositoryTest @Autowired constructor(
    private val memoryMemberRepository: MemoryMemberRepository
) {

    @Test
    fun save() {
        ...
    }

}

또한 Test룰 하겠다는 명시적 의미와 생성자 Parameter를 사용하여 위해 @SpringBootTest와 @Autowired constructor를 지정한다.

프로젝트에서 굳이 Kotlin으로 바꿔할 이유가 없다면,, 안바꿔도 되지 않을까? 그래도 Kotlin으로 작성했을 때 코드 생산성이 증가하는건 인정!

본 코드는 Fastcampus의 실무 프로젝트로 배우는 Kotlin & Spring : 리팩토링부터 서비스 구현까지 라는 강의 보고 작성되었습니다.

지금부터 할 것은 자바의 main method를 작동시키면서 getter, setter는 koltin으로 되어 있는 경우를 사용하는 코드이다.

kotlin으로 getter, setter를 구현하는 경우는 매우 간편하다. data class를 통해 hashCode나 equals, toString를 자동으로 구현하게 할 수 있지만, 단순히 getter, setter를 구현하는 것이라면, kotlin의 class를 사용해도 상관없다. 다음과 같이 말이다.

💉 Kotlin의 getter, setter 그리고 Java

본래 kotlin의 코드는 다음과 같다.

import java.util.*

class Person {

    var name: String? = null

    var birthDate: LocalDate? = null
    // LocalDate는 따로 import 해주어야 한다.

    val age: Int = 10

}

위 코드를 java로 변경하면, 다음과 같이 바뀌게 된다.

import java.util.*

public final class Student {
   @Nullable
   private String name;
   @Nullable
   private LocalDate birthDate;
   private final int age = 10;

   @Nullable
   public final String getName() {
      return this.name;
   }

   public final void setName(@Nullable String var1) {
      this.name = var1;
   }

   @Nullable
   public final LocalDate getBirthDate() {
      return this.birthDate;
   }

   public final void setBirthDate(@Nullable LocalDate var1) {
      this.birthDate = var1;
   }

   public final int getAge() {
      return this.age;
   }
}

code를 작성해야 할 것이 확실히 줄어드는 것이다. 코드 생산성이 압도적으로 높아진다.

물론 kotlin에서 java로 어떻게 변경되는지 개인적으로 무조건 알아야 된다고 생각든다.

1. kotlin의 class는 java에선 final이다.
   • 무차별 상속을 막기 위해서 만들어진 기능이다.
   • 대규모 시스템의 경우 객체 지향의 특성 상 상속으로 인해 생기는 종속성을 최대한 방지하기 위한다고 생각하면, 왜 final을 default로 내렸는지 이해된다. 그리고 이러한 기능은 함수(method)에도 적용된다.
   • 참고로 상속을 하고 싶다면, class앞에 open이라는 keyword를 작성하면 된다.
2. kotlin의 var 키워드를 작성하면 getter와 setter가 자동으로 만들어진다.

kotlin에서의 class는 getter와 setter는 자동으로 만들지만, hashcode와 equals, toString은 만들어지지 않는다. 이점을 유의해야 한다.

그리고 이 둘 모두 java의 main이건, kotlin의 main이건 상관없이 작동한다.

public class Main {
    public static void main(String [] args) {

        Student student = new Student();
        student.setName("junku");
        sutdent.setBirthDate(LocalDate.of(2022, 10, 23));

        System.out.println(student.getName()); // junku
        System.out.println(student.getBirthDate()); // 2022-10-23
    }
}

그러면 지금의 반대는 어떻게 될까? java의 class를 이용하면서 main을 kotlin으로 두고 code를 짜면 다음과 같다.

import java.util.*

public class Student {

    private String name;

    private LocalDate birthDate;

    private int age;

    public String getName() {
        return this.name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getBirthDate() {
        return this.birthDate.toString();
    }

    public void setBirthDate(LocalDate birthDate) {
        this.birthDate = birthDate;
    }

    public String getAge() {
        return this.age;
    }
}

java의 class를 위와 같이 작성하고 kotlin의 경우 다음과 같이 작성하면 된다.

fun main() {
    val person = Person()
    person.setName("junku")
    person.setBirthDate(LocalDate.of(2022, 10, 22))

    println(person.getName()) // junku
    println(person.getBirthDate()) // 2022-10-22

    // 사실 이러한 접근 보다는 kotlin에서는 property로 접근하는 것을 권장함.

    println(person.name) // junku
    println(person.birthDate) // 2022-10-22
}

그리고 무엇보다. 다음과 같은 method를 java class에 추가했다고 해보자.

import java.time.LocalDate;
import java.util.UUID;

public class Person {

    ...

    public String getUUID() {
        return UUID.randomUUID().toString();
    }
}

코드에 있는 그대로 UUID라는 property는 없다. 하지만, kotlin은 이 메소드의 name을 통해 property에 접근할 수 있다.

왜냐하면 앞의 get이라는 keyword를 보고 알아서 만들어 두기 때문이다, 하지만 method의 name 앞에 get이 없다면, 만들지 않아서 property로 접근이 불가능하다는 점을 기억하자.

즉 현재는 아래의 코드가 가능하다.

fun main() {

    val student = Student()
    println(student.uuid) // 9e778488-b671-4c40-a0f8-8b05f751b2e4

}

Kotlin식 문법: Scope 함수

코틀린의 scope 함수는 객체 조작을 훨씬 더 쉽게 하기 위해서 Kotlin에서 지원하는 함수의 일종임

대표적으로

let , run , with , apply , also이렇게 5개의 Scope 함수가 있음

1. let

null이 아닌 경우에 사용하고 그에 따른 새로운 결과를 반환하고 싶을 때 사용함. 또한 lambda함수처럼 마지막줄의 값이 return됨. let을 중첩해서 사용하면 가독성이 별로 좋지 않아서 중첩할 일이 있으면, if else구문을 사용하는 것을 추천한다. it으로 객체에 접근하게 됨.

val str: String? = "null"

val result: Int? = str?.let {
    println(it)
    val abc: String? = "abc"
    val def: String? = "def"
    if (!abc.isNullOrEmpty() && !def.isNullOrEmpty()) {
        println("abcdef가 null이 아님")
    }
    1234
}
println(result) // 1234

val str: String? = "null"
val abc: String? = "abc"
val def: String? = "def"

val result2: Int? =  str?.let {
        println(it)
        abc?.let {
                println(it)
                def?.let {
                        println(it)
                        }
                }
        1234
        }
println(result2) // 1234

2. run

일반적으로 class를 사용할 때 다음과 같이 짜게 됨.

fun main() {
    val config = DatabaseClient()
    config.url = "localhost:3306"
    config.username = "mysql"
    config.password = "1234"
    val contected = config.connect()
    println(contected)
    // DB 접속 중...
    // DB 접속 완료
}

class DatabaseClient {

    var url: String? = null
    var username: String? = null
    var password: String? = null

    // DB에 접속하고 Boolean 결과를 반환
    fun connect(): Boolean {
        println("DB 접속 중...")
        Thread.sleep(1000)
        println("DB 접속 완료")
        return true
    }
}

위 코드를 run을 활용하여 바꾸면 아래와 같음. 중복되는 코드 없이 바로바로 사용할 수 있는 것임. 아래 코드 역시 let을 통해서 코드를 작성할 수 있으나 it이 중복되므로, let보다는 run을 이용하여 만드는 것이 훨씬 좋다. this를 통해 객체 property에 접근하게 됨.

fun main() {
    val connected: Boolean = DatabaseClient().run {
    url = "localhost:3306"
    username = "mysql"
    password = "1234"
    connect()
    }
    println(connected)
    // DB 접속 중...
    // DB 접속 완료
}

3. with

with는 결과 반환없이 내부에서 수신객체를 이용할 때 사용함. 이 역시 lambda함수 이기 때문에 마지막 줄이 return값.

fun main() {
    val withEx = "안녕하세요"
    val length = with(withEx) {
        length
    }
    println(length) // 5

    val connectedUsingWith = with(DatabaseClient()) {
        url = "localhost:3306"
        username = "mysql"
        password = "1234"
        connect()
    }
    println(connectedUsingWith) // DatabaseClient@372f7a8d

}

4. apply

apply는 수신객체의 property를 구성하고 그 수신객체를 그대로 반환하고 싶을 때 사용한다. this로 사용

val connectedUsingApply: DatabaseClient = DatabaseClient().apply {
        url = "localhost:3306"
        username = "mysql"
        password = "1234"
        connect()
    }
println(connectedUsingApply)

5. also

also는 객체 그 자체의 동작을 제어하고 싶을 때 사용할 수 있음

class User(val name: String, val password: String) {
    fun validate() {
        if (name.isNotEmpty() && password.isNotEmpty()) {
            println("검증성공")
        } else {
            println("검증실패")
        }
    }
    fun printName() = println(name)
}

fun main() {

    val user: User = User(name = "tony", password = "1234")
    user.validate()

    User(name = "tony", password = "1234").also {
        it.validate() // "검증성공"
        it.printName() // "검증실패"
    }
}

개발을 본격적으로 학습하기 시작한지 어어언~ 1년 하고도 6개월이 흘러갔다. 그동안 나름 성실히 알고리즘 문제를 풀기도 했다. 특히 취준을 진심으로 시작한 근 6개월 동안 매일 매일 풀었던 것 같다. 주말에는 좀 쉰다고 해도.. 주중에는 나름 열심히 풀었다. 그렇게 풀었던 백준 문제는 350여개 정도.. 생각보다 그렇게 많지는 않았다.

물론 programmers나 swea까지 포함한다면 거의 700문제 가량 풀었지만 백준만 놓고 본다면,

플래가 과연 달성하기 어려운 티어인가?

라는 생각을 하게 된다.

그 누구나 꾸준히 문제를 푼다면 플래에 갈 수 있지만, 그 꾸준함을 증명하기 어렵다고 생각했기에 플래를 달성한 오늘 기분이 매우 좋다ㅋㅋㅋㅋ

앞으로도 알고리즘은 꾸준히 하겠지만, 몇가지 바램이 생겼다.

1. C++을 배우자.

• Python 한정 약간의 한계를 맛본거 같다. (개인적으로 다이아 전까지는 충분히 파이썬으로도 많은 문제를 풀 수 있지만 미래를 위해 C++ 문법을 배울만 하다.)

2. 최대한 다양한 언어로 풀자.

• kotlin, Python으로 대부분의 문제를 풀었으나, C++, Java로도 푸는 연습을 해야겠다.

3. 플래는 시작일뿐 다이아가 있다.

• 멈추지 말고 다이아에 도전에보자. 갈 수 있을지는 모르겠지만,, 진짜 랭커는 어떨지 궁금하다.

오늘은 편히 잘듯?ㅋㅋ

일단 전 이거 틀린게 맞는거 같습니다. 맞았습니다! 라고 떴지만, 문제에서 유도한 제약사항을 간신히 통과했고 문제에서 요구한 코드를 작성하지 않았기 때문에 틀린게 맞는거 같습니다.

ㅠㅠ

여튼 제가 풀이한 코드는 다음과 같습니다. 원래라면 틀려야되기 때문에

코드 설명은 안하겠습니다 ㅜㅜ

내 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
price = [list(input().strip()) for _ in range(n)]
state = 1
answer = 1
is_buy = [[[1 for _ in range(n)] for _ in range(n)] for _ in range(1 << (n+1))]


def bfs(state, p, now):
    global answer

    q = deque([(state, p, now, 1)])

    while q:
        state, p, now, cnt = q.popleft()

        if answer < cnt: answer = max(answer, cnt)

        for nxt in range(n):
            if state & (1 << nxt): continue
            if p > int(price[now][nxt]): continue
            if is_buy[state][now][nxt] >= cnt+1:
                continue

            is_buy[state][now][nxt] = cnt+1
            q.append((state | (1 << nxt), int(price[now][nxt]), nxt, cnt + 1))

bfs(1, 0, 0)
print(answer)

단순하게 그냥 bfs 돌렸는데.. 음.. 시간이 너무 오래걸렸습니다..ㅋㅋㅋㅋㅋ 아직도 많이 부족하네요 ㅜㅜ

몇몇분들은 bfs로 돌린것을 알고 있으나, 제 bfs는 너무 비효율적이네요..ㅋㅋ

이 문제 처음 읽고 일반환된 코드를 생각하지 못해 틀렸습니다.

중요한 것은 문제에서 이야기한 말 이동의 횟수에 따라 이동할 수 있는 것이 달라진다는 것. 그리고 이걸 방문 배열에서 어떻게 체크할 것인가? 입니다. 만약에 자꾸 틀리신다면, 아래 TEST CASE를 분석해보시면, 느낌이 오실겁니다.. 일반적인 2차원 방문 배열로는 이 문제를 풀 수 없구나..

1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0

즉, 낚시 문제였던 것 같습니다. 다행이 k값을 고려하여 방문 배열을 3차원으로 늘려줬더니 풀리게되었습니다. 물론 Python은 6600ms, PyPy는 600ms로 통과되었는데, Python은 참.. 정말 느린 언어네요.. 조금씩 Kotlin과 C++로 언어를 옮겨야할 것 같습니다..

문제풀이

일단 문제의 조건을 준수합시다.

원숭이는 말처럼 이동 할수도 있고 그냥 상 하 좌 우 격자 이동만 할 수 있습니다. 그리고 말처럼 이동하는 것은 제약 사항이 있습니다. 바로 k번만 이동할 수 있다는 것이죠. 따라서 이 모두를 고려 해야 합니다.

그러면 어떤 이동이 우선이 되어야 할까요?

제 생각이지만 상 하 좌 우 격자 이동이 우선시 되어야 할 것 같습니다. 그 이유는 위에서 제시된 Test Case에서는 상 하 좌 우로만 이동하다가 마지막에 말 점프를 합니다. 말 점프를 먼저하게 되면, 방금 말씀드린 경로를 찾을 수 없게 됩니다. 따라서 격자 이동을 먼저 하고 말 이동을 하는 것이 모든 경로를 고려할 수 있다고 생각했습니다.

그러면 방문 배열

1 차원: 말이동을 몇번 했는지 2 차원: 행 3 차원: 열

로 구성하여 BFS 탐색을 시도한다면 도착 지점까지의 가장 빠른 경로를 탐색할 수 있습니다.

따라서 전체 코드는 아래와 같이 구성됩니다.

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

k = int(input())
w, h = map(int, input().split())

INF = int(1e9)

arr = [list(map(int, input().split())) for _ in range(h)]
visited = [[[INF for _ in range(w)] for _ in range(h)] for _ in range(k+1)]
delta = [(0, 1), (1, 0), (0, -1), (-1, 0)]
horse_delta = [
    (-1, -2),
    (-2, -1),
    (-1, 2),
    (-2, 1),
    (1, 2),
    (2, 1),
    (2, -1),
    (1, -2)
]

sx, sy = 0, 0
ex, ey = h-1, w-1
def bfs(sx, sy):

    q = deque([(sx, sy, 0, 0)])

    while q:
        x, y, cnt, c = q.popleft()

        if x == ex and y == ey:
            return cnt

        for i in range(4):
            nx, ny = x + delta[i][0], y + delta[i][1]

            if not (0 <= nx < h and 0 <= ny < w): continue
            if arr[nx][ny] == 1: continue
            if visited[c][nx][ny] != INF : continue

            visited[c][nx][ny] = cnt + 1
            q.append((nx, ny, cnt + 1, c))

        if c >= k: continue

        for i in range(8):
            nx, ny = x + horse_delta[i][0], y + horse_delta[i][1]

            if not (0 <= nx < h and 0 <= ny < w): continue
            if arr[nx][ny] == 1: continue
            if visited[c+1][nx][ny] != INF: continue

            visited[c+1][nx][ny] = cnt + 1
            q.append((nx, ny, cnt + 1, c + 1))

    return -1

print(bfs(sx, sy))

질문과 오타 수정 언제나 환영입니다.

문제의 조건을 준수하면서 그래도 코드에 입히면 끝나는 문제였으나, 그게 쉬웠으면 Gold1에 랭크되어 있진 않겠지요..

요점은 문제의 조건을 어떻게 코드에 입힐 것인가? 입니다. 이때는 비트 마스크를 활용합니다.

비트마스크를 사용한 다는 것은 결국 어떤 상태를 기록하겠다는 의미거든요.

문제에는 어떤 상태가 존재할까요?

바로 민식이가 바로 어떤 키를 갖고 있는가? 입니다.

민식이가 갖고 있는 키값에 따라 갈 수 있는 경로가 달라지기 때문에 어떤 키를 갖고 있는지 여부를 bit로 구분하면 됩니다.

예를 들어서 문제에서 등장한 6개 키인 af를 16으로 대칭시켜보죠.

각각에 해당되는 key를 갖고 있다고 가정하면 다음과 같습니다.

이걸 6개의 모든 비트(2의 6제곱)에 대해 모든 방문 배열을 만듭니다. 이 방문 배열로 탐색할겁니다.

그리고 위의 근거로 인해 방문 배열은 3차원입니다.

1차원 → 갖고 있는 키 (state) 2차원 → 행 3차원 → 열

그러면 이제 이걸 코드로 반영해주어야되기 때문에 다음과 같은 코드로 미리 세팅해줍시다.

get_key = {
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
    "e": 4,
    "f": 5
}

use_key = {
    "A": 0,
    "B": 1,
    "C": 2,
    "D": 3,
    "E": 4,
    "F": 5
}

key = ["a", "b", "c", "d", "e", "f"]
set_key = set()
set_use_key = set()


for k in key:
    set_key.add(k)
    set_use_key.add(k.upper())

미로를 순회하다가 키값을 얻으면 바로 접근할 수 있도록 하기 위해서 get_key로 그리고 key를 사용할때는 대문자이기 때문에 use_key로 해당 dictionary를 사전에 세팅해주었습니다.

또한 6개의 key를 배열로 두지 않고 set으로 만들었습니다. 시간복잡도를 최대한 줄이기 위해서입니다. set으로 하면 제가 알기로 시간복잡도를 더 줄일 수 있는 것으로 알고 있습니다. 왜요? 라고 말씀하신다면.. 그냥 제가 문제를 풀어보면서 set으로 했을 때 시간 복잡도가 많이 줄어든 경험이 있어서 그런거 같습니다. 사실 여기서 더 설명하면 참조 지역성을 설명해야 되는데, 저 set은 아마 cpu에서 참조 지역성이 좁은 곳에 저장하지 않을까 생각드네요.

여튼 이제 키값을 갖는 state에 따라서 방문 여부를 체크할 visited 배열을 만들어줍시다.

# 델타이동
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

# 데이터 받기
n, m = map(int, input().split())
maze = [list(input().strip()) for _ in range(n)]

# 시작점 찾기
sx, sy = -1, -1
for i in range(n):
    for j in range(m):
        if maze[i][j] == "0":
            sx, sy = i, j
            break
    if sx != -1 and sy != -1:
        break

# 방문 배열 만들기
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range((1 << 6) + 1)]

그리고 탐색을 시도합시다

def find_exit(state, x, y, cnt):

    answer = int(10e9)
    q = deque([])
    q.append((state, x, y, cnt))

    while q:

        state, x, y, cnt = q.popleft()

        # 여기서 문제의 답을 도출할 것임
        if maze[x][y] == "1":
            answer = min(answer, cnt)

        for i in range(4):
            # 다음 좌표
            nx, ny = x + dx[i], y + dy[i]

            # 범위에 벗어나거나 이미 해당 상태에서 방문 또는 벽이면 볼 필요없음
            if not (0 <= nx < n and 0 <= ny < m): continue
            if visited[state][nx][ny] or maze[nx][ny] == "#": continue

            # 민식이가 갈 수 있는 좌표임 열쇠를 얻은 것은 아니기 때문에 state가 바뀌지는 않음
            if (maze[nx][ny] == "." or maze[nx][ny] == "0" or maze[nx][ny] == "1") and not visited[state][nx][ny]:
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))

            # 민식이가 key를 얻었으므로 state를 변경해주어 q에 넣어줌
            elif maze[nx][ny] in set_key and not visited[state | (1 << get_key[maze[nx][ny]])][nx][ny]:
                visited[state | (1 << get_key[maze[nx][ny]])][nx][ny] = True
                q.append((state | (1 << get_key[maze[nx][ny]]), nx, ny, cnt+1))

            # 민식이가 갖고 있는 키의 상태로 갈 수 있음 주의할 것은 key의 상태는 바뀌지 않음. 만약에 키가 한 번쓰고 끝나는 문제라면 해당 부분을 0으로 바꿔주면 됨. 어떻게? xor 연산으로..
            elif maze[nx][ny] in set_use_key and state & (1 << use_key[maze[nx][ny]]):
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))

    return answer

ans = find_exit(0, sx, sy, 0)

처음에는 아무런 key도 갖고 있지 않기 때문에 state는 0입니다. cnt는 이동한 경로를 세어줄겁니다.

이제 답을 도출합니다.

if ans == int(10e9):
    print(-1)
else:
    print(ans)

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

get_key = {
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
    "e": 4,
    "f": 5
}

use_key = {
    "A": 0,
    "B": 1,
    "C": 2,
    "D": 3,
    "E": 4,
    "F": 5
}

key = ["a", "b", "c", "d", "e", "f"]
set_key = set()
set_use_key = set()


for k in key:
    set_key.add(k)
    set_use_key.add(k.upper())

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

n, m = map(int, input().split())
maze = [list(input().strip()) for _ in range(n)]

sx, sy = -1, -1
for i in range(n):
    for j in range(m):
        if maze[i][j] == "0":
            sx, sy = i, j
            break
    if sx != -1 and sy != -1:
        break

visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range((1 << 6) + 1)]


def find_exit(state, x, y, cnt):
    answer = int(10e9)
    q = deque([])

    q.append((state, x, y, cnt))
    while q:
        state, x, y, cnt = q.popleft()
        if maze[x][y] == "1":
            answer = min(answer, cnt)

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if not (0 <= nx < n and 0 <= ny < m): continue
            if visited[state][nx][ny] or maze[nx][ny] == "#": continue

            if (maze[nx][ny] == "." or maze[nx][ny] == "0" or maze[nx][ny] == "1") and not visited[state][nx][ny]:
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))

            elif maze[nx][ny] in set_key and not visited[state | (1 << get_key[maze[nx][ny]])][nx][ny]:
                visited[state | (1 << get_key[maze[nx][ny]])][nx][ny] = True
                q.append((state | (1 << get_key[maze[nx][ny]]), nx, ny, cnt+1))

            elif maze[nx][ny] in set_use_key and state & (1 << use_key[maze[nx][ny]]):
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))

    return answer

ans = find_exit(0, sx, sy, 0)

if ans == int(10e9):
    print(-1)
else:
    print(ans)

문제를 읽다보면, 가장 위쪽 방향부터 찾으면 되겠다고 생각드는 문제였다.(이부분이 Greedy다)

사실 내 풀이는 최악의 시간복잡도가 1초 1억이 넘는다. Python이기 때문에..... 핸디캡이 붙은 듯 하다.

여튼 가장 위쪽 부터 탐색을 시도하면 그 다음 파이프라인은 이전에 만들어 놓은 파이프 라인 때문에 그 선으로 절대 갈 수 없으므로 이를 이용해서 DFS 탐색을 진행하면 된다. 이때 문제에서 요구한 c번째 열에 도착하면 파이프가 이어진 것이므로 이를 통해 파이프의 개수를 세면 되겠다.

DFS 알고리즘을 어떻게 짤 수 있나 생각이 들 수 있겠지만, toggle로 True False로 만든 뒤에 이를 계속 그 전 깊이로 넘기면 되겠다.

전체 코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(input().strip()) for _ in range(r)]
visited = [[False for _ in range(c)] for _ in range(r)]

dx = [-1, 0, 1]
dy = [1, 1, 1]

def dfs(x, y):

    if y == c-1:
        return True

    toggle = False
    for i in range(3):
        nx, ny = x + dx[i], y + dy[i]
        if not (0 <= nx < r and 0 <= ny < c): continue
        if visited[nx][ny]: continue
        if board[nx][ny] == "." and not toggle:
            visited[nx][ny] = True
            toggle = dfs(nx, ny)

    return toggle

answer = 0
for i in range(r):
    visited[i][0] = True
    if dfs(i, 0):
        answer += 1

print(answer)

난이도: G5 사용한 알고리즘: Bitmask, 완전 탐색

G5에 랭크되어 있어 어느 정도 어렵겠지 했지만, 그렇지 않았습니다. 1일 알고리즘.. 이거로 힐링하고 있는데, 만족스럽지 않네요ㅜ

점점 골드가 골드가 아닌거 같은 이 느낌....

그래도 겸손하게 꾸준히 풀어야겠습니다.

문제 설명

그냥 문제를 선택하는 것을 bitmask로 결정하면 됩니다.

하지만 문제의 조건 상 문제를 2개 이상을 고르는 것이 약간 마음에 걸리네요.

물론 그러한 조건을 코드에 추가하지 않아도 통과가 되었으나, 좀 더 정확한 코드이기 위해서는 앞서 말한 조건을 추가시키는 것이 좋겠네요.

여튼 1이면 문제를 선택! 그렇지 않으면 선택하지 않는 것으로 생각했고 이를 순회하면서 문제의 조건에 충족되는 것만 count 해주면 끝납니다.

그러면 bitmask를 할 수 있는 이유는 n이 15로 값이 생각보다 크지 않기 때문입니다.

최대 15 * 2^15로 50만번 순회 끝에 문제를 풀 수 있습니다.

코드

import sys
input = sys.stdin.readline

n, l, r, x = map(int, input().split())
level = list(map(int, input().split()))

cnt = 0
for i in range(1 << n):

    c = 0
    for j in range(n):
        if i & (1 << j):
            c += 1

    if c < 2: continue

    l_s = 0
    min_l = int(10e9)
    max_l = 0
    diff = 0
    for j in range(n):
        if i & (1 << j):
            l_s += level[j]
            min_l = min(min_l, level[j])
            max_l = max(max_l, level[j])
            diff = max_l - min_l

    if not (l <= l_s <= r):
        continue

    if not x <= diff:
        continue

    cnt += 1

print(cnt)

compose ui를 이용해서 실습하다가

Error running 'Preview': "There is no @Composable named

라는 에러가 발생했다.

뭐지했다. 왜냐하면 나는 @preview를 지웠기 때문이다.

한참을 찾다가 안드로이드 스튜디오 상단에 있는 버튼을 보았다.

바로 이렇게 생긴..

⁇⁇⁇⁇⁇⁇⁇⁇⁇⁇⁇⁇

⁇⁇⁇⁇⁇⁇⁇⁇⁇⁇⁇⁇

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그렇다.. 내 잘못이었다.. 저거 잘봐야겠다.. preview를 사용안하고 그냥 바로 App을 build하고 싶으면 저 위부터 찾아보자...

예전에 풀어본 문제지만, 그때는 안풀려서 다른 분 답을 참고했다. bitmask를 활용한 알고리즘 문제를 꼭 내 힘으로 풀어보겠다는 다짐을 한체 꾸준히 bitmask를 풀었고 어느 정도 감이 잡혔던 상태로 다시 한 번 이 문제에 도전했다. 문제는 그렇게 어렵지 않다. 하지만 이것을 어떻게 bitmask로 옮길 것인가? 는 좀 다른 질문인것 같다.

여튼 문제를 꼼꼼히 읽고 어떻게 해야 할지 설계를 했다.

문제의 노드의 개수는 10개로 입력값이 많지 않다. 따라서 bitmask를 활용한 완전 탐색을 진행하는 것이 효율적이다.

1. 일단 각각의 노드가 존재한다는 점
2. 각각의 노드로 2개의 집단을 나눴을 때 꼭 집단 안에서 모든 노드를 방문할 수 있어야 한다는 점
3. 모든 노드는 집단에 있어야 한다는 점
4. 각 집단의 state를 bitmask로 나눌 수 있다는 점
5. 문제에서 주어진 데이터는 graph 형식으로 다룰 수 있다는 점

그래서 일단 데이터를 받고 각각의 상태를 구분했다.

이를 위해 모든 노드를 방문하는 상태를 만들고 특정 상태를 만들고 이에 반대되는 상태를 만들었다. 그게 아래의 코드다.

# 모든 노드를 방문하는 상태
total_state = 1
for i in range(n):
    total_state = total_state | (1 << i)

# group1의 상태와 group2의 상태
for i in range(1 << n):
    state1 = i
    state2 = i^total_state

위 코드를 통해 각각의 상태를 구분했으며, 이 상태들을 통해 방문 여부를 체크해야 한다.

나는 DFS를 이용해서 방문했고, BFS로 방문해도 상관없다. 본인이 편한 탐색 알고리즘을 사용하면 된다.

DFS

def dfs(start, state):
    for nxt in graph[start]:
        if not visited[nxt] and (1 << nxt-1) & state:
            visited[nxt] = True
            dfs(nxt, state)

참고로 다음 노드를 의미하는 nxt에 -1을 한 이유는 1번 노드는 1 << 0 이고 2번 노드는 1 << 1을 의미하기 때문이다.

여튼 위 dfs를 이용하여 다음과 같이 group1, 2의 상태에 방문 여부를 체크한다.

방문 로직

    for j in range(n):
        if state1 & (1 << j) and not visited[j]:
            visited[j+1] = True
            dfs(j+1, state1)
            break

    for j in range(n):
        if state2 & (1 << j) and not visited[j]:
            visited[j+1] = True
            dfs(j+1, state2)
            break

솔직히 같은 코드를 작성해서 별로 마음에 들진 않지만, 2개의 집단 밖에 없기 때문에 충분히 문제에 알맞은 코드로 판단했다.

group의 상태를 와 각 비트를 체크하면서 1 << j가 state에 속하면서 방문하지 않은 노드라면 dfs 순회를 시도하되, 한 번 순회하면 끝내라는 의미이다. 문제의 조건에서 모든 그룹의 노드는 단 한 번의 순회로 모두 방문할 수 있기 때문에 이렇게 진행했다.

그리고 이렇게 순회했을 때 visited는 모두 방문체크가 되어 있어야 한다.

방문 체크

    for j in range(1, n+1):
        if not visited[j]:
            break

만약 위 code에서 break 문제 걸리지 않았다면, 문제에서 주어진 조건을 만족하는 state이기 때문에 다음과 같은 연산을 시도한다.

답 도출

    p1 = 0
    p2 = 0

    for k in range(n):
        if (1 << k) & state1:
            p1 += populations[k]
        else:
            p2 += populations[k]

        answer = min(answer, abs(p1-p2))

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
populations = list(map(int, input().split()))

graph = [[] for _ in range(n+1)]
for i in range(1, n+1):
    data = list(map(int, input().split()))
    for j in range(data[0]):
        graph[i].append(data[j+1])

def dfs(start, state):
    for nxt in graph[start]:
        if not visited[nxt] and (1 << nxt-1) & state:
            visited[nxt] = True
            dfs(nxt, state)

total_state = 1
for i in range(n):
    total_state = total_state | (1 << i)

answer = 1001
for i in range(1 << n):

    state1 = i
    state2 = i^total_state

    visited = [False for _ in range(n+1)]

    for j in range(n):
        if state1 & (1 << j) and not visited[j]:
            visited[j+1] = True
            dfs(j+1, state1)
            break

    for j in range(n):
        if state2 & (1 << j) and not visited[j]:
            visited[j+1] = True
            dfs(j+1, state2)
            break

    for j in range(1, n+1):
        if not visited[j]:
            break
    else:
        p1 = 0
        p2 = 0

        for k in range(n):
            if (1 << k) & state1:
                p1 += populations[k]
            else:
                p2 += populations[k]

        answer = min(answer, abs(p1-p2))

if answer == 1001:
    print(-1)
else:
    print(answer)

느낀점

처음은 아니지만, 못풀었던 문제를 bitmask로 풀어서 너무 기분이 좋았다. 뭔가 더 성장했다는 느낌을 받았다. 앞으로도 쭈욱 계속 진행해보자!

문제 분석 단순한 DFS 문제로 판단했습니다. 다른 방식은 아직 생각나지 않았습니다.

어차피 문제의 자료구조가 트리구조이기 때문에(순환x) 최하단 자식 노드까지 내려갔다가 부모로 다시 올리면서 문제의 조건을 대입해주면 됩니다.

주의할 점은 문제의 조건상 123,456개의 노드가 존재할 수 있습니다. 그러므로 최대 재귀 깊이를 123,456이상으로 설정해주셔야 합니다. Python은 그렇습니다.

그러면 이제 순회를 돌아야겠죠?

어떻게 순회를 돌 수 있을까요?

문제의 조건대로 순회를 돌기 위한 데이터 부터 갖춰놓는게 좋겠죠. 단방향에 알맞은 부모와 자식간 연결을 나타내는 graph를 먼저 만들어야 합니다. 그리고 sheep과 wolf 정보를 알아야겠죠. (몇 번 노드에 존재하는지 알아야 합니다.) 문제 설명을 읽어보면, 두 번째 줄부터 N-1개에 줄에 2번 섬부터 N번 섬까지 섬의 정보를 나타내는라고 적혀있습니다. 따라서 각 줄이 2번부터 n번 노드까지의 정보를 갖고 있는 데이터임을 알 수 있습니다. 이를 통해 sheep과 wolf를 따로 저장하면, 더할 값과 뺄 값을 따로 관리할 수 있습니다.

결국 알고리즘을 사용하기 전 사전에 준비할 코드는 다음과 같습니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())

graph = [[] for _ in range(n+1)] # tree
s = [0 for _ in range(n+1)] # Sheep
w = [0 for _ in range(n+1)] # Wolf
for i in range(2, n+1): # 나머지 데이터 받기
    sw, number, to = map(str, input().split())

    # 문제의 조건에 따라 sw가 S일 때와 W일 때를 구분해서 따로 값을 저장합니다!
    if sw == "S": s[i] = int(number)
    else: w[i] = int(number)
    # graph의 경우 단방향으로만 저장합니다.
    # 이때 밑으로 내려가는 과정을 먼저 진행하기 때문에
    # index는 parent, value는 child로 생각하고 저장해주어야 합니다.
    graph[int(to)].append(i)

이를 통해 DFS를 돌리면 되겠죠.

💻 DFS 코드 짜기

가장 먼저 할 것이 최하단 노드까지 내려가 주어야 합니다.

조건 1. 1번 노드(최상단 노드)에서 graph를 순회하면서 연결된 노드로 쭉쭉 내려가 줍시다!

조건 2. 최하단 노드까지 내려왔으면, 더 이상 아래로 내려갈 노드가 존재하지 않으므로 DFS를 돌지 않습니다. 그러면 이제 문제에서 주어진 상황을 대입하면서 연산을 수행하여 부모노드로 올려주면 됩니다.

조건 3. 부모 노드로 올려주다가 최상단 노드로 돌아오면(무조건 sheep, wolf 둘 다 0인 노드) 이를 answer에 더해줍시다.

이러한 방식을 코드로 옮기면 다음과 같습니다.

answer = 0
def dfs(start):
    global answer

    # 살아 남은 양을 기록할 number 생성
    number = 0
    # 조건 1. DFS를 돌 때마다 살아 남은 양을 더해주어야 함, 최하단 노드까지 내려가야 함.
    for nxt in graph[start]:
        number += dfs(nxt)

    # 조건 2.
    # 자식에서 부모로 올라올 때 해당 노드가 늑대를 갖고 있으면 늑대의 수만큼 빼주되, 0보다 작거나 같으면 0을 return 함
    if w[start] != 0:
        return number - w[start] if number - w[start] > 0 else 0

    # 자식에서 부모로 올라올 때 해당 노드가 양을 갖고 있으면, number에서 양의 수만큼만 더해서 return 함
    if s[start] != 0:
        return number + s[start]

    # 조건 3.
    # 최상단 노드로 올라왔으면, answer에 number를 더해줌
    if start == 1:
        answer += number
        return

마지막으로 위 문제를 풀기 위한 최종 코드입니다.(python으로 돌리시길 바랍니다. pypy는 메모리 초과가 납니다.)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())

graph = [[] for _ in range(n+1)]
s = [0 for _ in range(n+1)]
w = [0 for _ in range(n+1)]
for i in range(2, n+1):
    sw, number, to = map(str, input().split())

    if sw == "S": s[i] = int(number)
    else: w[i] = int(number)

    graph[int(to)].append(i)

answer = 0
def dfs(start):
    global answer

    number = 0
    for nxt in graph[start]:
        number += dfs(nxt)

    if w[start] != 0:
        return number - w[start] if number - w[start] > 0 else 0

    if s[start] != 0:
        return number + s[start]

    if start == 1:
        answer += number
        return

dfs(1)
print(answer)

전형적인 PS 풀이를 이용한 문제입니다. G1에 랭크되어 있는 만큼 알고리즘 짜기 힘들기도 하고 생각하기도 힘들다는 생각이 드네요.

그래도 괜찮습니다. 차근차큰 생각하다보면, 답이 나올 것입니다.

문제에서 설명하기를 1번은 인터넷이 무조건 연결되어 있고 N번째를 연결하고 싶다고 합니다. 각각의 번호는 모두 노드이고, 노드를 잇기 위한 cost도 존재하고 있습니다.

그리고 사장님이 k개 이상 연결된 간선에 대해서 돈을 지출해야 되는데, 이때 지출할 돈의 최소값을 찾는 문제입니다.

시간 복잡도 생각하기

돈의 최소값을 찾아야 하며, 주어진 데이터가 생각보다 많기 때문에(간선 개수만 10,000개, 가중치의 최대값 1,000,000) 이분 탐색을 시도해야 합니다. 그리고 한번 순회를 할 때 최대 10,000개를 모두 돌아다닐 수 있으며 어떤 값이 가장 최적인지 찾기 위해서는 최악으로 1,000,000 * 10,000의 시간복잡도가 나올 수 있습니다. 그러면, 이걸 어떻게 줄일 수 있을까요?

바로 dijkstra입니다. dijkstra로 순회하면 (노드의 개수)*log(간선의 개수) * log(n) → 1000 𝗑 log(10,000) 𝗑 log(1,000,000) 입니다.

즉, 약 1800만 정도의 순회 끝에 모든 순회를 마칠 수 있습니다.

사장이 지출할 값들의 최대값 중 최소값을 찾아야 하므로 이 지출 상한을 이분 탐색으로 찾습니다. 이때 dijkstra로 지출할 값이 target한 값보다 큰 녀석들을 count합니다. 그리고 count한 값이 k(무료 개수)보다 크다면, 지출 상한을 높여주고 그렇지 않다면 지출 상한을 낮춰줍니다. 그리고 이렇게 찾은 지출 상한이 바로 답이 됩니다.

주의: 못찾으면 -1을 출력해야함.

코드 💻

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n, p, k = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(p):
    s, e, c = map(int, input().split())
    graph[s].append((e, c))
    graph[e].append((s, c))


def dijkstra(start):

    INF = 10001
    dist = [INF] * (n+1)
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))

    while pq:
        cost, now = heappop(pq)

        if cost > dist[now]: continue

        for nxt, c in graph[now]:
            if c > mid:
                if dist[nxt] > 1 + cost:
                    dist[nxt] = 1 + cost
                    heappush(pq, (1 + cost, nxt))
            else:
                if dist[nxt] > cost:
                    dist[nxt] = cost
                    heappush(pq, (cost, nxt))

    return dist

start = 0
end = 100000001
answer = 100000001
while start <= end:

    mid = (start + end) // 2
    result = dijkstra(1)

    if result[n] > k:
        start = mid + 1
    elif result[n] <= k:
        answer = mid
        end = mid - 1

if answer == 100000001:
    print(-1)
else:
    print(answer)