Sad Puppy 3 개발자 아지트 :: 개발자 아지트

코딩테스트 준비를 하기 위해서 연습 문제를 풀때, 제한 시간을 한번쯤 볼 수 있었을 것이다. 

여기서 말하는 제한 시간은 알고리즘이 실행되고 종료될 때 걸리는 시간의 제한 시간을 말하는 것이다. 

 

컴퓨터에서 1초당 처리되는 연산 횟수가 대략적으로 정해져있다.

 

(코딩테스트를 치는 환경(연습으로 문제푸는 환경도 마찬가지)에는 모든 컴퓨터의 성능이 동일하다고 가정한다. )

(1초당 1억개의 연산 가능)

 

그런데 문제에 대해 알고리즘을 어떻게 짜냐에 따라서 1초당 처리되는 연산 횟수가 줄어들 수도 있고 유지될 수도 있다. 

더 많아질 수는 없다. (컴퓨터가 자가 발전하지 않는 이상(?))

 

코드를 작성하고 나서 이 알고리즘이 어떻게 짜여졌냐? 어떻게 짜여졌길래 1초당 처리되는 연산 횟수가 이런가?

 

작성한 알고리즘이 1초당 처리되는 연산 횟수가 이정도면 대략 이정도의 복잡도를 가진 알고리즘일 것이다. 

(단, 입력 크기를 N으로 일반화 해야함. 왜냐하면 입력 크기가 1인 경우 알고리즘을 작성해야 하는 경우로 예를 들자면, 입력크기가 1일때만  연산 횟수가 1인 성능을 가지는 것이기 때문 == 해당 상황에 한정된것, 입력 크기가 다른 값으로 바뀔경우 연산 횟수 성능도 바뀔 것)

 

이런 맥락에서의 복잡도를 가지고,

==> 우리는 이것을 알고리즘의 시간복잡도라고 하기로 했다. 

 


 

입력 크기에 따른 연산 횟수 추이를 활용해 시간 복잡도를 표현하는 방법을 점근적 표기법이라 한다. 

 

[시간 복잡도(time complexity)]

: 알고리즘의 성능을 나타내는 지표. 입력 크기(알고리즘이 처리해야 할 데이터의 양)에 대한 연산 횟수의 상한을 의미한다. 

시간 복잡도는 낮으면 낮을 수록 좋다. 

 

시간 복잡도는 최선, 보통, 최악의 경우로 나눌 수 있지만, 코딩테스트에서는 작성한 알고리즘의 최악의 경우를 고려하여 시간 복잡도를 계산해야한다. 왜냐하면, 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하기 때문이다. 

 

* 빅오 표기법

: 빅오 표기법은 최악의 경우일 때의 시간 복잡도를 표현하는 방법이다. 

빅오 표기법은 특정 알고리즘의 연산 횟수가 f(x)일 때, 함수의 최고차항만을 남기고 남은 자수를 지워 O(최고차항)와 같이 표현하면 된다. 

 

 

* 빅오 표기법을 쉽게 쓸 때 최고차항만 남기고 차수를 지우는 이유

: 시간복잡도 식에서 최고차항 이외의 값들을 2차원 그래프에서 표현해보면 최고차항 이외의 값들은 무시할 수 있을 정도로 작으므로 무시한다. 

 

컴퓨터는 1초에 최대 1억번 연산할 수 있다. 

 

코딩 테스트의 문제는 출제자의 의도대로 로직을 구현했을 경우 대부분 코드를 정답처리 할 수 있게끔 채점시간을 정한다. 

 

 

시간 복잡도 N의 가용 범위
O(N!) 10
O(2^N) 20~25
O(N^3) 200~300
O(N^2) 3,000~5,000
O(NlogN) 100만
O(N) 1,000~2,000만
O(logN) 10억

 

 

이때, 언어별로 다른 성능의 차이는 고려하지 않는다. 

 

 

[시간 복잡도 계산해보기]

: 과정

1. 문제 정의

2. 연산 횟수 측정

3. 시간 복잡도 분석

 

* 고려할 점

출력 자체도 연산이다. 

비교도 연산이다. 

 

 

 

 

 

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

의문
:git branch -r 하면 나오는 브랜치 리스트 중에 일부를 내 로컬 브랜치로 가지고 오고싶은데 git fetch 로는 안되는건가?
 

git fetch 명령어는 원격 저장소의 모든 브랜치와 관련된 최신 변경 사항을 로컬 저장소에 가져온다. 그러나 이 명령어만으로는 원격 브랜치를 로컬 브랜치로 바로 생성하지 않는다. 원격 브랜치를 로컬 브랜치로 가져오려면 다음의 과정을 진행해야한다. 

 

  1. 원격 브랜치 목록 확인:이 명령어로 원격 브랜치의 목록을 확인할 수 있습니다.
    =>git branch -r
  2. 원하는 원격 브랜치를 로컬 브랜치로 체크아웃
    =>git checkout -b feature-branch origin/feature-branch

예시

: feature-branch라는 원격 브랜치를 로컬에 feature-branch라는 이름으로 가져오고 싶다면 다음과 같이 입력한다. 

 
git checkout -b <로컬_브랜치명> origin/<원격_브랜치명>
 
 

 

'형상관리 > Git' 카테고리의 다른 글

[Git] 원본 저장소 원격 추가하기  (0) 2024.07.29
[Git]브랜치 관리  (1) 2024.01.31
[Git] Detached Head의 발생 이유 및 해결 방법  (0) 2024.01.09

LCS란?

:"가장 긴 공통 부분 수열"이다. 알고리즘 LCS에서는 가장 긴 공통 부분 문자열이다. 두 개의 문자열이 있을 때, 그 문자열에서 순서를 유지하면서 공통으로 나타나는 글자들을 이어서 만들 수 있는 가장 긴 문자열을 찾는 것을 의미한다.

 

*부분 문자열이란?

:부분 문자열에는 연속된 부분 문자열인 Substring과 연속되지 않은 부분 문자열인 Subsequence라는 개념이 있다. 

 

Subsequence라는 개념을 예시를 들어 설명하자면, "ABCDEF"와 "AEBDF"라는 두 문자열이 있다면, 이 두 문자열에서 공통으로 나타나며 글자들이 두 문자열에서 같은 순서로 나타나는 문자열 중 가장 긴 부분 수열은  "ABDF"이다. 

 

 

예시

accykp와 ccap사이의 lcs를 구할 경우 만들어서 활용해야하는 배열

 

 

* 위 배열 활용법 *

배열의 초기 상태

 

조회하는 문자열이 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야한다. 

조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값을 교체한다. 

 

맨 첫번째 행의 모든 열을 0으로 하고 다음 모든 행의 첫번째 열에 0은 왜 넣는걸까?

=> 조회하는 문자열이 같을때, 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야하는데, 

앞에 0을 넣지 않으면 첫번째 문자열의 맨첫번째 값과 두번째 문자열의 맨 첫번째 값에 어떤 값을 넣어줘야 할지 모르기 때문이다. 

 

왜 바로 앞의값(왼쪽)의 값에서 +1을 하지 않을까? 

=> 바로 앞의값에서 +1을 하면 lcs의 값에 +1을 하는 꼴이 된다.

(하지만 두번째 단어의 조회할 자리는 여전히 같은 자리임=> 두번째 단어의 조회할 자리를 +1 하면 할수록 lcs의 값이 중복으로 +1되는 꼴)

 

왜 조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값으로 교체할까? 

왜 하필 현재 자리에서 왼쪽, 위의 값을 비교할까? 

 => 현재 자리의 왼쪽은 현재 자리의(같은행, 다른열==현재열-1) lcs값은 고려하지 않고 이전 문자까지의 lcs값만을 가지고 있는 것이고,

현재 자리의 위쪽은 현재 자리의 lcs값을 고려하지만, 새로 조회하는 문자와의 비교는 하지 않은 값이다. (다른행==현재행-1, 같은열)

 

왼쪽, 위의 값은 각각 자신이 할 수 있는 최적의 lcs를 구한 상태이다.

따라서 둘 중에 큰 값을 골라 현재의 자리의 값을 교체해줌으로써 최적의 값을 유지할 수 있게된다. 

 

 

https://www.acmicpc.net/problem/9252

 

 

 

문제 해결 방법

1. dp배열을 만들어서 lcs를 구함

2. lcs를 구한 dp배열을 역추적하여 문자열을 구함 

 

코드 구현

정답 코드 

 

s1 = input()
s2 = input()

m=len(s1)
n=len(s2)

dp = [[0] * (n+1) for _ in range(m+1)]

for i in range(1, m+1):
    for j in range(1, n+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1], dp[i-1][j])

result =''
startm = m
startn = n

print(max(dp[-1]))
if max(dp[-1])!=0:
    while 1:
            if dp[startm][startn]==0:
                break
            # 위에것이 더 큰지
            if dp[startm][startn] == dp[startm-1][startn]:
                startm-=1
            # 왼쪽 것이 더 큰지
            elif dp[startm][startn] == dp[startm][startn-1]:
                startn-=1
            # 둘다 안크면 대각선 이동 
            # 값도 넣어줌 
            elif ((dp[startm][startn]-1) == dp[startm-1][startn-1]):
                
                startm-=1
                startn-=1

                result+=s2[startn]


            
            

    print(result[::-1])

 

시간/공간 복잡도

0.1초로 시간제한이 있었는데, 해당 시간에 1000만 번의 연산을 해야하는거고, 최대로 입력할 수 있는 문자열의 길이가 1000이기 때문에 

O(n)으로 푸는것이 맞다. 

 

최적화 및 개선

따로 하지 않음 

 

어려웠던 점

lcs의 개념, lcs의 역추적의 개념을 잘 몰라서 접근하기 어려웠다. 

역추적 부분은 아직도 어렵게 느껴진다. 비슷한 문제를 여러번 풀어봐야 할 것 같다. 

 

 

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준1012] 유기농 배추  (0) 2024.09.09
[백준1926] 그림  (0) 2024.08.26
[백준17829] 222-풀링  (0) 2024.08.14
[백준2504] 괄호의 값  (0) 2024.08.12
[백준10799] 쇠막대기  (0) 2024.08.09

https://www.acmicpc.net/problem/17829

 

 

문제 해결 방법

1. 맵은 행과 열이 항상 2의 배수일 수 밖에 없다는 것을 인지한다. 

2. 따라서 0행0열 0행 2열 0행 4열... 2행 0열 2행 2열.... 이렇게 맵의 크기만큼 조회한다. 

2-1. 출발지 기준 이때 오른쪽으로 한칸, 아래로 한칸, 아래 오른쪽으로 한칸 을 리스트에 넣는다. 

2-2. 리스트에서 두번재로 큰 수만 모아서 또다른 리스트를 만든다. 

 

2번을 맵의 원소가 1개 남을때 까지 반복하다보면 결과 값이 나온다. 

 

 

코드 구현

정답 코드 

import sys

n = int(input())
block=[]
for i in range(n):
    tmp = list(map(int, sys.stdin.readline().strip().split()))
    block.append(tmp)

while 1:
    if len(block[0])==1:
        print(block[0][0])
        break

    makeBlock = [item[:] for item in block]

    block = []
    for i in range(0, len(makeBlock),2):
        tmp=[]
        for j in range(0, len(makeBlock[0]),2):
            realT=[makeBlock[i][j], makeBlock[i][j+1], makeBlock[i+1][j], makeBlock[i+1][j+1]]
            realT.sort(reverse=True)
            tmp.append(realT[1])

        block.append(tmp)

 

시간/공간 복잡도

해당 문제는 구현문제이기 때문에 시간/공간 복잡도를 따지지 않는다. 

 

최적화 및 개선

따로 하지 않음

 

어려웠던 점

쉬운 구문을 까먹어서 검색해서 찾아봤다 아예 그 구문은 외워야겠다. 

리스트 복사하는 구문과 sort함수 사용법.

 

 

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준1926] 그림  (0) 2024.08.26
[백준9252] LCS 2  (0) 2024.08.14
[백준2504] 괄호의 값  (0) 2024.08.12
[백준10799] 쇠막대기  (0) 2024.08.09
[백준2110] 공유기 설치  (0) 2024.08.06

[Java-based Configuration]

: Java 코드와 스프링이 제공하는 어노테이션을 통해 스프링 컨테이너를 정의하는 방법 학습

 

[Declaring a Bean]

:@Configuration  어노테이션이 달린 클래스와 @Bean 어노테이션이 달린 메서드를 통해 Java 코드에서 스프링 빈을 등록할 수 있다. 

 

빈으로 등록하고자 하는 함수의 리턴값에서 실제 구현체가 없으면 빈이 등록되지 않는다. 

 

 

 

[Bean Dependencies]

:@Configuration 어노테이션이 있는 클래스 내의 메서드는 같은 클래스 내의 다른 @Bean 메서드를 호출해 빈 간의 의존성을 정의할 수 있다. 

 

@Configuration
@ComponentScan(basePackages = "cholog.scan")
public class AppConfig {

    @Bean
    public AuthService authService() {
        // 실제 구현체가 없으면 빈이 등록되지 않는다.
        return new AuthService();
    }
    
    @Bean
    public AuthenticationPrincipalArgumentResolver authenticationPrincipalArgumentResolver(AuthService authService) {

        return new AuthenticationPrincipalArgumentResolver(authService);
    }

}

 


[Property]

: 이는 애플리케이션의 구성값을 key-value 쌍으로 저장한다. 데이터베이스 연결 정보나 API 키 값을 예를 들 수 있다. 

스프링의 Environment 인터페이스는 이와 같은 프로퍼티 소스들을 통합해 관리하고, 필요한 프로퍼티 값을 조회하는 기능을 제공한다. 

 

[Using @PropertySource and Environment]

: @PropertySource 어노테이션을 사용해 프로퍼티 파일을 로드하고, Environment를 사용해 프로퍼티 값을 읽어올 수 있다. 

 

 

// TODO: Java-based Configuration을 하기 위한 클래스로 지정하기
// TODO: ext-api.properties 파일을 활용하기 위한 설정 추가하기
@Configuration
@PropertySource("classpath:ext-api.properties")
public class PropertySourceConfig {

    private final Environment env;

    public PropertySourceConfig(Environment env) {
        this.env = env;
    }

    // TODO: ext-api.properties의 google.api.endpoint 값을 Environment를 사용해서 가져오기
    // TODO: 위 endpoint 값을 사용하여 GoogleMapsRestClient를 빈으로 등록하기
    @Bean
    public GoogleMapsRestClient googleMapsRestClient() {
        String endpoint = env.getProperty("google.api.endpoint");
        return new GoogleMapsRestClient(endpoint);
    }

    // TODO: ext-api.properties의 google.api.endpoint 값을 어노테이션을 사용해서 가져오기
    // TODO: 위 endpoint 값을 사용하여 GoogleMapsRestClient를 빈으로 등록하기
    public GoogleDriveRestClient googleDriveRestClient() {
        return new GoogleDriveRestClient("");
    }
}

 

이해가 잘 안된다..

 

[Using @PropertySource and @Value]

: @PropertySource를 사용해 로드한 프로퍼티 파일의 값을 @Value 어노테이션을 통해 주입할 수 있다. 

스프링에서 @Value 어노테이션을 사용하면 ext-api.properties 파일에 있는 값을 필드나 메서드 파라미터에 주입할 수 있다. 

 

 

package cholog.property.config;

import cholog.property.GoogleDriveRestClient;
import cholog.property.GoogleMapsRestClient;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.context.annotation.PropertySource;
import org.springframework.core.env.Environment;

@Configuration
@PropertySource("classpath:ext-api.properties")
public class PropertySourceConfig {

    private final Environment env;

    public PropertySourceConfig(Environment env) {
        this.env = env;
    }

    @Bean
    public GoogleMapsRestClient googleMapsRestClient() {
        String endpoint = env.getProperty("google.api.endpoint");
        return new GoogleMapsRestClient(endpoint);
    }
    
    @Value("${google.api.endpoint}")
    private String googleApiEndpoint;

    @Bean
    public GoogleDriveRestClient googleDriveRestClient() {
        return new GoogleDriveRestClient(googleApiEndpoint);
    }
}

 

[Externalized Configuration (Spring Boot)]

: 프로퍼티 값을 설정하는 방법은 @PropertySource 외에도 다양하다. 특히 Spring Boot 를 사용한다면 application.properties(혹은 application.yaml) 파일을 사용해 프로퍼티 값을 편하게 설정할 수 있다. 

 

package cholog.property.config;

import cholog.property.JwtTokenKeyProvider;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

// TODO: Java-based Configuration을 하기 위한 클래스로 지정하기
@Configuration
public class AuthConfig {
    // TODO: application.properties의 security.jwt.token.secret-key 값을 활용하여 JwtTokenKeyProvider를 빈으로 등록하기

    @Value("${security.jwt.token.secret-key}")
    private String secretKey;

    @Bean
    public JwtTokenKeyProvider jwtTokenKeyProvider() {
        return new JwtTokenKeyProvider(secretKey);
    }
}

 


[Profile]

: 프로파일은 애플리케이션 설정의 논리적인 그룹이다. 예를 들어, 개발(development), 테스트(testing), 운영(production)과 같이 다른 환경에 적합한 설정을 분리할 수 있다.

프로파일을 사용하면 같은 애플리케이션이지만 환경에 따라 다른 구성을 적용할 수 있다.

스프링이 제공하는 Environment 인터페이스는 현재 활성화되어 있는 프로파일과 기본 프로파일을 관리한다. 

 

[@Profile]

: @Profile 어노테이션을 이용하여 특정 프로파일에 따라 빈을 등록할 수 있다. @Profile 어노테이션은 클래스 레벨, 메서드 레벨에 모두 적용 가능하다. 

 

@Configuration 클래스에 적용하는 경우

 

클래스 내에서 정의된 Bean들은 development profile일 때만 등록된다. 

 

@Bean 메서드에 적용하는 경우

 

profile에 따라 등록되는 Datasource Bean이 달라집니다.

 

@Configuration
public class ProfileConfig {

    @Bean("dataSource")
    @Profile("dev")
    public MessageRepository inMemoryMessageRepository() {
        return new InmemoryMessageRepository();
    }

    @Bean("dataSource")
    @Profile("prod")
    public MessageRepository jdbcMessageRepository() {
        return new JdbcMessageRepository();
    }

}

 

 

 

스프링 컨테이너를 정의하는 방법은 다양합니다.@Component, @Autowired 어노테이션을 사용하는 방법과 비교하여 Java 코드로 빈을 관리할 때의 장단점에 대해 생각해보고, 어떤 상황에서 어떤 방식을 택할지 고민해보세요.이 외에도 XML을 사용해 스프링 컨테이너를 정의할 수도 있습니다. XML을 사용하는 방법에 대해 알아보고, Java 코드와 XML을 사용하는 방법을 비교해보세요.Spring Boot는 프로퍼티 파일 컨벤션(application-{profile})을 사용해 활성 프로파일에 대한 프로퍼티 파일을 로드합니다. 예를 들어, 활성 프로파일이 prod 라면 application.properties, application-prod.properties 파일을 로드합니다. 이러한 특성을 사용해 어떤 값을 프로퍼티 파일에서 관리할지 생각해 보세요.

 

[Spring Bean]

: 스프링은 애플리케이션의 복잡성을 줄이고, 유지보수를 용이하게 하기 위해서 객체의 생성, 설정 및 생명주기를 관리하는 스프링 컨테이너를 제공한다. 해당 컨테이너가 관리하는 객체를 스프링 빈이라고하고, 이를 통해서 의존성 주입이나 객체 관리가 자동화된다. 

 

[Bean Registration]

: 스프링에서 빈을 등록하는 방법은 다양한다. (= 빈을 만드는 방법)

 

어노테이션을 사용해 클래스에 추가하는 방법이 있다. 

 

@Component

: 스프링아, 이 클래스를 빈으로 만들어서 관리해줘! 

 

@Component
public class SpringBean {
    public String hello() {
        return "Hello";
    }
}

 

이제 스프링이 SpringBean 클래스를 관리하게 된다. 

 

 

[Bean Autowiring]

: 스프링 컨테이너에 등록된 객체는 매번 새로 생성할 필요 없이 컨테이너에서 가져와서 사용할 수 있다. (빈 자동 연결)

@Autowired
private SpringBean springBean;

 


[Dependency Injection]

:스프링 컨테이너에 등록된 스프링 빈 간의 의존성을 관리하는 방법은 다양하다. 그 중 어노테이션을 이용한 방법으로 생성자, 세터, 필드에 해당 @Autowired 어노테이션을 추가하는 방법이 있다. 

 

*참고로

: InjectionBean은 혼자 움직일 수 없고, ConstructorInjection이라는 것 안에서 움직일 수 있다. 

 

[Constructor Injection]

:스프링 컨테이너에 등록된 스프링 빈 간의 의존성을 생성자를 통해 주입하는 방법이다. 

 

private InjectionBean injectionBean;

public ConstructorInjection(InjectionBean injectionBean) {
    this.injectionBean = injectionBean;
}

 

여기서 'ConstructorInjection을 만들 때, InjectionBean이라는 객체를 미리 넣어줌으로써 의존성을 주입한다. 

 

[Setter Injection]

:스프링 컨테이너에 등록된 스프링 빈 간의 의존성을 세터를 통해 주입하는 방법이다. 

 

private InjectionBean injectionBean;

    @Autowired
    public void setInjectionBean(InjectionBean injectionBean){
        this.injectionBean = injectionBean;
    }

 

[Field Injection]

: 스프링 컨테이너에 등록된 스프링 빈 간의 의존성을 필드를 통해 주입하는 방법이다. 

 

@Autowired
private InjectionBean injectionBean;

 


[Component Scan]

: 스프링에서 특정 패키지를 스캔해, 그 패키지 안에 있는 @Component, @Service, @Repository, @Controller 등의 어노테이션이 붙은 클래스를 == 컨테이너에 등록된 스프링 빈을 자동으로 찾아 등록하는 역할을 한다.

 

[@ComponentScan]

: @ComponentScan 어노테이션을 이용해 스캔할 패키지를 지정할 수 있다. 앞에서 해당 어노테이션을 사용하지 않고도 정상동작했던 이유는 @SpringBootApplication이 @ComponentScan을 포함하고 있기 때문이다. 


@ComponentScan 이 덕분에 @Component로 표시된 클래스들이 자동으로 스프링 빈으로 등록되었던 것이다. 

@ComponentScan 이 어노테이션이스프링 빈을 관리하고, 자동으로 설정해주기 때문에 @Autowired가 정상적으로 작동할 수있다. 

 

 

@Configuration
@ComponentScan(basePackages = "cholog.scan")
public class ContextConfiguration {
}

 ComponenetScanBean을 Bean으로 등록하기

 

상위 패키지를 스캔하도록 함으로써 

상위패키지 아래에 등록된 빈을 사용하도록 만듦

[JdbcTemplate]

: 스프링은 데이터베이스와의 연동을 쉽게 도와주는 여러 도구와 방식을 제공한다. 

JDBC는 Java Database Connectivity의 약어로, 자바에서 데이터베이스에 접속하도록 해주는 API이다. 

JdbcTemplate은 이 API를 잘 사용할 수 있도록 스프링에서 제공하는 템플릿 클래스이다. 

이는 스프링 JDBC의 핵심이고, 다른 고수준의 기능들도 결국 내부에서는 이를 활용한다. 

 

jdbcTemplate은 핵심 JDBC 작업 흐름에 기본적인 업무를 수행하고, 애플리케이션 코드는 SQL을 제공하고 결과를 추출하는 역할을 한다. 

 

사용 효과 

: 데이터베이스 연동 코드를 보다 간결하고 안정적으로 작성할 수 있다. 

 

JdbcTemplate 클래스의 제공 기능

:

1. SQL 쿼리 실행

2. statements 및 저장된 procedure all 업데이트

3. ResultSet 인스턴스를 반복하고 반환된 매개 변수 값 추출을 수행

4. JDBC 예외를 캡처하고, org.springframework.dao 패키지에 정의된 일반적이고 더 유용한 에외 계층으로 변환함

 


[Querying (SELECT)]

 

스프링에서 JdbcTemplate을 이용해 SELECT 쿼리를 실행할 수 있는 여러 방법을 제공한다. 

queryForObject, query, queryForList, queryForRowSet, queryForMap 등의 메서드를 통해 쿼리를 실행할 수 있다. 

 


[Querying for a Single Object]

 

JdbcTemplate의 queryForObject 메서드를 이용해 단일 객체를 조회할 수 있다. 

 

[Object with Count]

queryForObject의 첫 매개변수는 쿼리문이고, 두 번째 매개변수는 조회 결과를 매핑할 클래스 타입이다. 

 

public int count() {
        int rowCount = jdbcTemplate.queryForObject("select count(*) from customers", Integer.class);
        return rowCount;
    }

사용예시

 

queryForObject는 Spring Framework의 JdbcTemplate 클래스에서 제공하는 메서드로, SQL 쿼리를 실행하여 단일 결과 값을 반환할 때 사용된다. 이 메서드는 데이터베이스 쿼리를 수행하고, 쿼리 결과의 첫 번째 행을 특정 타입의 객체로 매핑하여 반환한다. 주로 다음과 같은 상황에서 사용된다. 

 

 

단일 값 반환: 쿼리 결과가 단일 값(예: COUNT, SUM 등)인 경우, 이를 적합한 자바 기본형 또는 객체로 반환한다.

String sql = "SELECT COUNT(*) FROM users WHERE active = ?"; int count = jdbcTemplate.queryForObject(sql, Integer.class, true);

 

 

 

객체 반환: 쿼리 결과를 자바 객체로 매핑하여 반환한다. 이 경우, RowMapper 또는 해당 클래스의 타입을 지정해야 한다. 여기서는 User라는 클래스의 객체를 반환한다. BeanPropertyRowMapper는 결과셋의 컬럼 이름과 User 클래스의 필드 이름을 자동으로 매핑해준다.

String sql = "SELECT id, name, email FROM users WHERE id = ?"; User user = jdbcTemplate.queryForObject(sql, new Object[]{1}, new BeanPropertyRowMapper<>(User.class));

 

효과

:

예외 처리: 쿼리 결과가 없거나 두 개 이상의 결과가 반환될 경우 EmptyResultDataAccessException 또는 IncorrectResultSizeDataAccessException이 발생한다. 

 

단순성과 편리함: 간단한 쿼리를 사용하여 단일 결과를 처리할 때 매우 유용하다. 

queryForObject는 복잡한 SQL 쿼리 결과를 간단하게 자바 객체로 매핑할 수 있게 해준다. 

 

[Object with Parameter]

 

queryForObject의 세 번째 매개변수를 이용해, 쿼리문에 바인딩할 파라미터를 전달할 수 있다. 

public String getLastName(Long id) {
        //TODO : 주어진 Id에 해당하는 customers의 lastName을 반환
        String lastName = jdbcTemplate.queryForObject("select last_name from customers where id = ?", String.class, id);

        return null;
    }

 

첫번째 인자는 쿼리문

두번째 인자는 SQL  쿼리문의 결과값의 반환값

세번째 인자는 쿼리문 속에 ?에 들어갈 값 

 

*반환 타입을 명시하는 이유는?

:queryForObject 메서드에서 반환 타입을 명시하는 이유는 SQL 쿼리의 결과를 자바 객체로 매핑하기 위해서이다. 데이터베이스에서 가져온 데이터를 자바 객체로 변환할 때, 어떤 타입으로 변환할지를 명확히 지정해줘야한다.

 

예를 들어, last_name이 VARCHAR 타입이라면 이를 자바의 String 타입으로 반환해야 한다. 이를 위해 String.class를 한다

 

반환 타입을 명시함으로써 컴파일 시점에 타입 체크를 할 수 있어, 타입 안전성을 보장할 수 있다.

반환 타입을 명시함으로써 코드를 읽는 사람이 쿼리 결과가 어떤 타입인지 명확하게 이해할 수 있다. 코드의 가독성을 높이고, 유지보수를 쉽게 만들어주는 효과를 받을 수 있다. 

 

 

[Object with RowMapper]

 

queryForObject의 두 번째 매개변수에 RowMapper을 전달해 조회 결과를 매핑할 수 있다. 

 

*RowMapper란?

 

:Spring Framework에서 제공하는 인터페이스로, 데이터베이스 쿼리의 결과인 ResultSet을 자바 객체로 매핑해준다.  

RowMapper를 통해 ResultSet의 각 행(row)을 원하는 자바 객체로 변환할 수 있다. 데이터베이스의 테이블에서 데이터를 조회한 후, 해당 데이터를 특정 클래스의 객체로 매핑할 수 있다.

 

 public Customer findCustomerById(Long id) {
        String sql = "select id, first_name, last_name from customers where id = ?";

        Customer customer = jdbcTemplate.queryForObject(
                sql,
                (resultSet, rowNum) -> {
                    Customer customer1 = new Customer(
                            resultSet.getLong("id"),
                            resultSet.getString("fist_name"),
                            resultSet.getString("last_name")
                    );
                    return customer1;
                }, id);

        return null;
    }

RowMapper의 기능을 직접 람다식으로 구현한 것

 

resultSet에서 데이터베이스 쿼리의 결과를 담고 있다.

rowNum은 결과셋에서 몇 번째 행인지를 나타내는 숫자이다. 해당 코드에서는 사용되지 않았다. (작성은 했으나, 쓰이지 않았음)

 

getLong(), getString()등을 통해 각 열의 값을 가져온다. 

 

RowMapper는 데이터베이스에서 가져온 결과(ResultSet)를 자바 객체로 변환하는 인터페이스이다. 

이를 통해, 데이터베이스의 한 행을 자바 객체로 매핑하는 방법을 정의할 수 있다. 

 

queryForObject함수의 두번째 인자 값이 RowMapper의 mapRow메서드를 람다식으로 구현한 것이다. 

 

*mapRow()란?

: ResultSet의 각 행을 읽어들이고, 그 데이터를 사용해 자바 객체를 생성한다. 

 

결과적으로, queryForObject의 두번째 인자 값이 객체로 표현함으로써 저런식의 반환 타입을 명시하는것이다. 


[Querying for a List]

 

[List with RowMapper]

: jdbcTemplate의 query 메서드를 이용해 여러 객체를 조회할 수 있다. 두 번째 매개변수에 RowMapper을 전달해 조회 결과를 매핑할 수 있다. 

public List<Customer> findAllCustomers() {
        String sql = "select id, first_name, last_name from customers";

        List<Customer> customers = jdbcTemplate.query(
                sql,
                (resultSet, rowNum) -> {
                    Customer customer = new Customer(
                        resultSet.getLong("id"),
                        resultSet.getString("first_name"),
                        resultSet.getString("last_name")
                    );
                    return customer;
                });

        return customers;
    }

 

queryForObject의 세 번째 매개변수를 이용해 쿼리문에 바인딩할 파라미터를 전달할 수 있다. RowMapper의 경우, 별도 선언해 사용할 수 있다. 

 

public List<Customer> findAllCustomers() {
        String sql = "select id, first_name, last_name from customers";

        List<Customer> customers = jdbcTemplate.query(
                sql,
                (resultSet, rowNum) -> {
                    Customer customer = new Customer(
                        resultSet.getLong("id"),
                        resultSet.getString("first_name"),
                        resultSet.getString("last_name")
                    );
                    return customer;
                });

        return customers;
    }

 

이렇게 쓰면 쿼리로 불러와서 만든 customer이 customers에 들어간다. 


(추가적으로 공부하기)


[Updating (INSERT, UPDATE, and DELETE)]

: jdbcTemplate을 이용해, INSERT, UPDATE, DELETE 쿼리를 실행할 수 있다. 

 

쿼리문을 통해 insert를 할 때는 update함수를 이용한다. 

 

[Update (INSERT)]

 

 public void insert(Customer customer) {
        String sql = "insert into customers (first_name, last_name) values (?, ?)";
        jdbcTemplate.update(sql, customer.getFirstName(), customer.getLastName());
    }

 

insert into customers (first_name, last_name) values (?, ?) 
 
위 구문에 대한 설명
: 해당 SQL 구문은 customers 데이터베이스 테이블에 새로운 데이터를 삽입하는 INSERT 문이다. 
데이터베이스의 first_name과 last_name이라는 두 개의 열에 값을 삽입하겠다는 구문이다. 
 
values (?, ?)에 삽입할 값을 지정한다. (?는 플레이스 홀더 라고 하고, 나중에 코드에서 구체적인 값으로 대체된다)
 
 

[Update (DELETE)]

 

    public int delete(Long id) {
        //todo: id에 해당하는 customer를 지우고, 해당 쿼리에 영향받는 row 수반환하기
        String sql = "delete into customers where id = ?";
        Integer affectedRow = jdbcTemplate.update(sql, Long.valueOf(id));

        return affectedRow;
    }

 

jdbcTemplate.update() 메서드는 해당 쿼리에 의해 영향을 받은 행의 수를 반환한다. 

 

Long.valueOf()란?

:  Java에서 타입 변환을 수행하는 메서드 중 하나로, 주로 원시 타입 long 또는 int 값을 객체 타입 Long으로 변환하는 데 사용된다. (형변환 및 성능 최적화에 도움됨)

 

Long.valueOf(id)를 사용하는 이유는

: jdbcTemplate.update 메서드는 SQL 쿼리의 파라미터로 객체 타입을 받기 때문에 id 값이 long 또는 int 타입일 경우, 이를 명시적으로 Long 타입으로 변환하기 위해이다. 

 

 

[KeyHolder]

: 이는 Spring Framework에서 제공하는 인터페이스로, JdbcTemplate을 통해 데이터베이스에 새로운 행을 삽입하고 하고 자동으로 생성된 primary key를 가져올 수 있다. 

 

사용방법

: update(PreparedStatementCreator psc, KeyHolder generatedKeyHolder) 메서드를 통해 사용 

 

public Long insertWithKeyHolder(Customer customer) {
        String sql = "insert into customers (first_name, last_name) values (?, ?)";
        KeyHolder keyHolder = new GeneratedKeyHolder();

        jdbcTemplate.update(connection -> {
            PreparedStatement ps = connection.prepareStatement(
                    sql,
                    new String[]{"id"});
            ps.setString(1, customer.getFirstName());
            ps.setString(2, customer.getLastName());
            return ps;
        }, keyHolder);

        Long id = keyHolder.getKey().longValue();

        return keyHolder.getKey().longValue();
    }

 

connection은 객체이고, jdbc api에서 제공하는 데이터베이스와 상호작용 하기 위한 클래스이다. 

이는 자바 애플리케이션과 데이터베이스 간의 연결을 관리하는 객체이다. 

sql 쿼리 실행을 위해 Statement나 PreparedStatement 객체를 생성한다. 

 

prepareStatement 객체는  jdbc api에서 제공하는 데이터베이스와 상호작용 하기 위한 클래스이며, SQL문을 미리 준비해두기 위해 사용함. ? 를 사용하여 바인딩 한다. 

 

connection.prepareStatement(sql, new String[] {"id"});

 

해당 구문의 첫번째 인자는 sql문, 두번째 인자는 반환값으로 받을 값의 타입 설정 및, 어떤 값을 받을지에 대한 설정을 하는 자리이다. 위 구문은 id열을 String 배열로 받겠다는 의미이다. 

 

 

ps.setString(1, customer.getFirstName()); 

 

해당 구문의 첫번째 인자는 sql문에 있는 ?의 위치를 의미한다. 만약 1이라면, 첫번째 ?를 의미한다. 

두번째 인자는 삽입할 값을 의미한다. 

 

ps가 리턴된 후, keyHolder에는 해당 ps를 처리하고 난 후 발생한 key값을 저장하게된다. 

 

 

 

 

'프레임워크 > Spring' 카테고리의 다른 글

Spring Core 2  (0) 2024.08.14
Spring Core 1  (0) 2024.08.14
Spring mvc 4 (MVC Configuration, View Controller, Interceptor, Argument Resolver)  (0) 2024.08.06
Spring mvc 3 (예외처리)  (0) 2024.08.05
Spring mvc 2 (CRUD API)  (0) 2024.08.05

https://www.acmicpc.net/problem/2504

문제 해결 방법

1. 괄호가 정상적인지 확인한다. 

2. 스택을 만들고, 괄호열의 값을 계산하기 위한 변수를 선언한다. (변수의 초깃값은 1)

3. 여는 괄호일 경우, 변수에  괄호의 종류에 따라 2혹은 3을 곱한다. 

4. 닫는 괄호가 나올경우, 그 이후 또다른 여는 괄호가 나올 때까지 닫는 괄호가 나올 수 있다.
(여는 괄호가 나오지 않는다면 결국 모든 괄호열의 순회를 완료하게 됨)

단, 괄호를 연만큼 닫는 괄호가 나오지만, 괄호가 닫히지 않은 경우는 계속 나머지 값들에 영향을 줘야만 한다. 

따라서, 괄호가 닫히는 경우 나머지 값들에 영향을 주지 않기 위해 괄호의 종류에 따라 2 혹은 3으로 나눈다. 

5. 3-4를 괄호열 순회를 마칠 때 까지 수행한다. 

6. 결과값을 출력한다. 

 

 

코드 구현

정답 코드 

s = input()
stack=[]
check = 0
for i in s:
    if i =='(':
        stack.append('(')
    elif i == '[':
        stack.append('[')
    elif i == ')':
        if stack:
            if stack[-1]=='(':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check = 1
            print(0)
            break
    elif i == ']':
        if stack:
            if stack[-1]=='[':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check =1
            print(0)
            break
if check == 0:
    if stack:
        print(0)
    else:
        checkingStack = []
        result=0
        tmpV=1
        for index, j in enumerate(s):
            if j=='(':
                tmpV*=2
                check =1
                checkingStack.append('(')
            elif j=='[':
                tmpV*=3
                check =1
                checkingStack.append('[')

            elif j==')':
                if check ==1: # 최초로 닫는괄호 
                    result+=tmpV
                    tmpV=tmpV//2
                    check=0
                    checkingStack.pop()
                else:
                    tmpV=tmpV//2
                    checkingStack.pop()

            elif j==']':
                if check ==1: # 최초로 닫는괄호 
                    result+=tmpV
                    tmpV=tmpV//3
                    check=0
                    checkingStack.pop()
                else:
                    tmpV=tmpV//3
                    checkingStack.pop()

            #print('checkingStack', checkingStack, ' result: ', result, 'index: ', index, ' tmpV: ', tmpV)
        print(result)

 

시간/공간 복잡도

해당 문제는 구현문제이기 때문에 시간/공간 복잡도를 따지지 않는다. 

 

최적화 및 개선

따로 하지 않음

 

어려웠던 점

문제를 풀다보면 결국 관건은 괄호를 닫을때 지금까지 계산한 값을 곱셈( (X) 혹은 [X] )을 할 것이냐 덧셈(결합)을 할 것이냐를 구분하는 것이 어렵다. 그런데 어떤식으로 하든 해결할 방법이 생각나지 않았다. 

(후위 계산인가 싶어서 별거 다해봄)

 

결과적으로는 분배법칙의 아이디어를 통해 해당 문제를 해결했다. 

 

( ( ) [ [ ] ] ) 해당 괄호의 경우, 분배법칙을 적용하면 ...

 

( ( ) ) ( [ [ ] ] )  이렇게 풀 수 있다. 

 

두 괄호는 계산해보면 결과 값이 같다. 

 

이를 잘 고려하여, 계산을 위한 변수 값을 잘 다루어 문제를 해결할 수 있었다. 

 

 

흔적 (보지마세요)

더보기
# 괄호열이 뭔지? 

# 올바른 괄호열인지 체크 = 쌍을 이루는지 체크

# 닫기를 시작했을때, 계산시작 
# () = 2, [] = 3

# 다 닫고(if stack:) 새로 열때 +

s = input()
stack=[]
check = 0
for i in s:
    if i =='(':
        stack.append('(')
    elif i == '[':
        stack.append('[')
    elif i == ')':
        if stack:
            if stack[-1]=='(':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check = 1
            print(0)
            break
    elif i == ']':
        if stack:
            if stack[-1]=='[':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check =1
            print(0)
            break
if check == 0:
    if stack:
        print(0)
    else:
        print('좋다  시작하자 ')
        checkingStack = []
        cal=''
        result = 0
        for index, j in enumerate(s):
            if j=='(':
                if not checkingStack:
                    cal+='(2*'
                    checkingStack.append(j)
                else:
                    if checkingStack[-1]=='(':
                        cal+='((2+'
                        checkingStack.append(j)
                    elif checkingStack[-1]=='[':
                        cal+='(2#'
                        checkingStack.append(j)
                    elif checkingStack[-1]==')' or checkingStack[-1]==']':
                        cal+='+(2$'
                        checkingStack.append(j)
            elif j=='[':
                if not checkingStack:
                    cal+='(3'
                    checkingStack.append(j)
                else:
                    if checkingStack[-1]=='[':
                        cal+='*3'
                        checkingStack.append(j)
                    elif checkingStack[-1]=='(':
                        cal+='(3'
                        checkingStack.append(j)
                    elif checkingStack[-1]==']' or checkingStack[-1]==')':
                        cal+='+(3'
                        checkingStack.append(j)

            elif j==')':
                if checkingStack[-1]=='(':
                    cal+=')'
                    result= result+(result*2)
                    checkingStack.pop()
                

            elif j==']':
                if checkingStack[-1]=='[':
                    cal+=')'
                    result*=3
                    checkingStack.pop()
                    
            print('')
            print('j: ', j)
            print('checkingStack', checkingStack, ' result: ', result)
            print('cal',cal)
        check = 0

        # # + 추가 작업 // replace, find 다시 공부하기 
        # while 1:
        #     check = 0

        #     result1 = s.find(")(")
        #     result2 = s.find("][")
        #     result3 = s.find(")[")
        #     result4 = s.find("](")

        #     if result1!=-1:
        #         s=s.replace(")(", ")+(")
        #         check =1
        #     elif result2!=-1:
        #         s=s.replace("][", "]+[")
        #         check =1
        #     elif result3!=-1:
        #         s=s.replace(")[", ")+[")
        #         check =1
        #     elif result4!=-1:
        #         s=s.replace("](", "]+(")
        #         check =1

        #     if check == 0:
        #         break
        # print('result:', s)
        
        # # 2, 3 교체 작업 

        # while 1:
        #     check = 0
        #     result1 = s.find("()")
        #     result2 = s.find("[]")

        #     if result1!=-1:
        #         s=s.replace("()", "2")
        #         check =1
        #     elif result2!=-1:
        #         s=s.replace("[]", "3")
        #         check =1
            
        #     if check == 0:
        #         break

        # print('result?:', s)
        # tmpStack=[]
        # for i in s:
        #     tmpStack.append(i)
        
        # print('tmpStack', tmpStack)
        # p=[]
        # result = 0
# 괄호열이 뭔지? 

# 올바른 괄호열인지 체크 = 쌍을 이루는지 체크

# 닫기를 시작했을때, 계산시작 
# () = 2, [] = 3

# 다 닫고(if stack:) 새로 열때 +

from collections import deque

s = input()
stack=[]
check = 0
for i in s:
    if i =='(':
        stack.append('(')
    elif i == '[':
        stack.append('[')
    elif i == ')':
        if stack:
            if stack[-1]=='(':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check = 1
            print(0)
            break
    elif i == ']':
        if stack:
            if stack[-1]=='[':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check =1
            print(0)
            break
if check == 0:
    if stack:
        print(0)
    else:
        #print('좋다  시작하자 ')
        calStack=deque([])
        checkingStack = []
        cal=''
        result = 0
        
        for index, j in enumerate(s):
            if j=='(' or j=='[': 
                if index==0:
                    calStack.append(0)
                    checkingStack.append(j)
                else:
                    if s[index-1]==')' or s[index-1]==']':
                        checkingStack.append(j)
                        # print('된건가?')
                    elif s[index-1]=='(' or s[index-1]=='[':
                        checkingStack.append(j)
                    else:
                        checkingStack.append(j)
                        if calStack:
                            result = calStack[-1]
                            calStack.clear()
            if j==')':
                if s[index-1]=='(':
                    if checkingStack[-1]=='(':
                        print("들어오긴해?", index)
                        if index-2>=0:
                            if s[index-2]==')'or s[index-2]==']':
                                calStack[-1]+=2
                                print("나왔어?")
                            else:
                                if calStack[-1]==0:
                                    calStack[-1]+=2
                                    checkingStack.pop()
                                    print("!")
                                else:
                                    calStack[-1]*=2
                                    checkingStack.pop()
                                    print("!!")
                        elif index-1>=0:
                            calStack[-1]+=2
                            print("*")

                    else:
                        calStack.append(2)
                        result+=calStack[-1]
                        calStack.clear()
                        checkingStack.pop()
                        print("@")
                elif s[index-1]==')':
                    if calStack:
                        if len(checkingStack)==1:
                            v=sum(calStack)*2
                            calStack.clear()
                            calStack.append(v)
                        else:
                            calStack[-1]=calStack[-1]*2
                            checkingStack.pop()
                            print("??????????")
                    else:
                        result=result*2
                        checkingStack.pop()
                        print("#")
                elif s[index-1]==']':
                    if checkingStack[-1]=='(':
                        calStack[-1]=calStack[-1]*2
                        # result += sum(calStack)*2
                        # calStack.clear()
                        # checkingStack.pop()
                    print('?뭘까???')

                
            if j==']':
                if s[index-1]=='[':
                    if checkingStack[-1]=='[':
                        if index-2>=0:
                            if s[index-2]==')'or s[index-2]==']':
                                calStack[-1]+=3
                                # print("나왔어?")
                            else:
                                if calStack[-1]==0:
                                    calStack[-1]+=3
                                    checkingStack.pop()
                                else:
                                    calStack[-1]*=3
                                    checkingStack.pop()
                        elif index-1>=0:
                            calStack[-1]+=3
                        # print("!")
                    else:
                        calStack.append(3)
                        result+=calStack[-1]
                        calStack.clear()
                        checkingStack.pop()
                elif s[index-1]==']':
                    if calStack:
                        if len(checkingStack)==1:
                            v=sum(calStack)*3
                            calStack.clear()
                            calStack.append(v)
                        else:
                            calStack[-1]=calStack[-1]*3
                            checkingStack.pop()
                            # print("?")
                    else:
                        result=result*3
                        checkingStack.pop()
                    
                    #print('?뭘까')
                elif s[index-1]==')':
                    if checkingStack[-1]=='[':
                        # result += sum(calStack)*3
                        # calStack.clear()
                        # checkingStack.pop()
                        calStack[-1]=calStack[-1]*3

            print('checkingStack', checkingStack, ' result: ', result, ' calStack: ', calStack, 'index: ', index, ' j: ', j)

        for i in calStack:
            result+=i

        print(result)

 

알게된 것

 

해당 문제에 대한 접근법

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준9252] LCS 2  (0) 2024.08.14
[백준17829] 222-풀링  (0) 2024.08.14
[백준10799] 쇠막대기  (0) 2024.08.09
[백준2110] 공유기 설치  (0) 2024.08.06
[백준16918] 봄버맨  (0) 2024.08.05

https://www.acmicpc.net/problem/10799

 

 

 

문제 해결 방법

0. 카운트 변수를 만든다. 초기화는 0으로 한다. 

1. 받은 문장을 한글자씩 순회하며  현재 열려있는 괄호를 스택에 넣는다. (flag 표시를 해준다 flag = 1)

2. 문장을 순회하다가 닫는 괄호가 나오면 바로 직전에 본 글자가 열려있는 괄호인지 확인한다. (확인은 flag를 통해서 한다. )

 2-1. flag가 1이면 레이저로 확인되었으므로 그동안 열려있는 괄호의 수만큼 카운트 변수에 +1을 해준다. 

 2-2. flag가 0이면 단순 닫는 flag이니 괄호를 닫아주되(들어가있는 값중 -1 인덱스의 값이 열린괄호가 있으면 pop), 하나의 종이를 레이저가 한번 자르면 종이가 n개면 +1이 된다는 것을 고려하여 카운트값에 +1을 해준다.  

 

3. 순회가 끝날 때 까지 2번을 반복한다. 

 

 

 

코드 구현

정답 코드 

# ()는 레이저다 

s = input()
stack=[]
cnt = 0
flag=0
for i in s:
    if i =='(':
        stack.append('(')
        flag=1
    elif i==')':
        if stack[-1] =='(':
            stack.pop()
            if stack and flag==1:
                if flag ==1:
                    cnt+=len(stack)
            if flag ==0:
                cnt+=1
            flag=0


    # print('난 ',i,'에요', stack, 'cnt: ', cnt)
print(cnt)

 

시간/공간 복잡도

괄호 문자는 최대 100,000 이므로, O(NlogN)으로 풀어야한다. 

최적화 및 개선

따로 하지 않음 

어려웠던 점

없음

 

알게된 것

따로 없음 

+ Recent posts