git push 후 rebase를 해야 한다거나, commit 내용을 수정해야한다거나, 여러 이유로 다시 되돌리고 싶을 때가 있을 때 사용하는 방법 💥주의!!! 협업 시 사용 안하는 것이 좋음. 개인 프로젝트 때만 사용하는 것이 안전하다..

1. push한 commit들을 합치고 싶을 때

1. 합치는 범위 정하기

# 위에서부터 3번째까지 조회
git rebase -i HEAD~3

2. pick을 squash로 수정

1번의 명령어를 치면 위에서부터 세번째까지 보여준다. 가장 위에 있는 commit이 가장 과거이다. 가장 상단의 것만 제외하고 명령어 i를 눌러 pick을 squash로 변경한다. 그리고 esc를 누른 후 명령어 :wq를 입력하여 저장한다. 그렇게 되면 뭐 commit message 수정하는 내용이 나오거나 할텐데 나는 그냥 :wq 입력했다. 그러면 새로운 commit분이 생긴다. 그리고 아래의 명령어를 입력하면 rebase 했던 것들이 덮어씌워지면서 합쳐진 commit이 대체된다.

git push origin 브랜치 --force
#또는
git push origin +브랜치

2. push한 commit의 message를 수정하고 싶을 때

1. 수정하고 싶은 commit 찾기

# 위에서부터 3번째까지 조회
git rebase -i HEAD~3

2. pick을 reword로 수정

1번의 명령어를 치면 위에서부터 세번째까지 보여준다. 가장 위에 있는 commit이 가장 과거이다. message를 변경하고 싶은 commit을 찾고 명령어 i를 눌러 pick을 squash로 변경한다. 그리고 esc를 누른 후 명령어 :wq를 입력하여 저장한다. 그러면 메시지를 수정하라는 내용이 뜰텐데 명령어 i를 입력 후 수정하고 :wq로 저장한다. 그러면 새로운 commit분이 생긴다. 그리고 아래의 명령어를 입력하면 변경한 commit message가 덮어씌워지면서 push 된다.

git push origin 브랜치 --force
#또는
git push origin +브랜치

3. push한 commit의 사용자를 수정하고 싶을 때

1. 수정하고 싶은 commit 찾기

# 위에서부터 3번째까지 조회
git rebase -i HEAD~2

2. pick을 edit으로 수정

1번의 명령어를 치면 위에서부터 두번째까지 보여준다. 가장 위에 있는 commit이 가장 과거이다. 사용자를 변경하려고 하는 commit을 명령어 i를 눌러 pick을 edit으로 변경한다. 그리고 esc를 누른 후 명령어 :wq를 입력하여 저장한다.

3. 변경하고자 하는 사용자 정보 입력

2번을 실행하고 나면 아래의 내용이 나온다.

git commit --amend --author="이름 <이메일>"

위 명령어로 사용자 정보를 입력한다. 그러면 아래의 내용이 보이는데 잔디만 심을 것이기 때문에 esc를 누른 후 명령어 :q로 나가준다.

4. 반복 및 마무리

다음 파일 처리를 위해 명령어를 입력한다.

git rebase --continue

3번을 실행한다. 모두 완료했다면 아래의 명령어로 강제 push 한다.

git push origin 브랜치 --force
#또는
git push origin +브랜치

💥 편집기에서 무언가 잘못되었을 때

esc를 누르고 :q!를 눌러 나간다. 해당 명령어는 저장하지 않고 해당 편집기를 나가겠다는 뜻이다.

💥 rebase가 잘못되었을 때

git rebase --abort

여러 개의 Docker 컨테이너를 한꺼번에 정의하고 실행하는 도구.

🖋 사용 이유

1. 간소화된 제어
   • 단일 YAML 파일에서 여러 컨테이너 애플리케이션을 정의하고 관리 가능.
2. 효율적인 협업
   • 파일 공유가 간편하여 개발자, 운영팀, 기타 이해관계자 간의 협업을 촉진.
3. 신속한 애플리케이션 개발
   • 컨테이너 생성에 사용된 구성을 캐시함. (변경되지 않은 서비스를 다시 시작하면 기존 컨테이너 재사용)
4. 다양한 환경 간 이식성 : 변수를 지원하여 다양한 환경이나 사용자에 맞게 구성을 사용자 지정 가능.

🖋 주요 구성 요소

• version : Compose 파일 형식 버전 (compose V2는 필요 없음)
• service : 여러 개의 컨테이너를 정의하는 부분
• image : Docker Hub에서 다운받을 이미지
• build : Dockerfile을 직접 빌드해서 이미지 생성
• ports : 호스트포트:컨테이너포트 포트 매핑
• restart : 컨테이너가 예기치 않게 꺼졌을 때 설정
• volumes : 데이터 지속 저장을 위한 디렉토리 매핑
• environment : 환경변수 설정 (DB 패스워드 등)
• depends_on : 의존성 설정 (실행 순서 조절)
• container_name : 컨테이너 이름 지정
• networks : Docker 컨테이너들 끼리 서로 통신할 수 있도록 네트워크를 묶어주는 설정

🖋 하나의 파일에 모두 작성 VS 각각 파일 작성

• 하나의 파일에 모두 작성

  • 모든 서비스는 자동으로 동일한 default 네트워크에 연결
  • depends_on, links 등을 사용해 실행 순서 및 의존성도 표현 가능

• 각각 파일 작성

  • 서비스는 완전히 독립적

  • 서로 다른 네트워크를 사용하여 직접 연결이 안됨.

  • 수동으로 연결해줘야 함

    # 각 파일에 동일한 외부 네트워크 정의
    networks:
        shared-network:
      external: true
    
    # 네트워크 생성 명령어
    docker network create shared-network

Dockerfile

• Dockerfile : 이미지를 만들기 위한 명령어 모음.
• Image : "환경 + 코드 + 설정" 이 포장된 파일.
• Container : 이미지를 실행한 실제 인스턴스.

Dockerfile 과 docker-compose.yml 차이

🖋 Dockerfile

• 이미지를 어떻게 만들지 정의 (환경 설정 포함)
• 새로운 이미지를 만들고 싶을 때 사용
• 단일 이미지 중심 (ex. 나만의 java 서버)
• docker build, docker run 으로 실행

  🖋 docker-compose.yml

• 이미지들을 어떻게 실행할지 정의 (컨테이너 조합)
• 여러 컨테이너는 한 번에 실행할 때 사용
• 여러 서비스 조합 (ex. 웹 + DB + 캐시)
• docker-compose up 으로 실행

Go 언어로 작성된 리눅스 기반의 애플리케이션을 컨테이너 단위로 실행할 수 있게 해주는 도구. 애플리케이션 개발, 배포 및 실행을 위한 개방형 플랫폼.

🖋 Docker 사용 이유

1. 환경 차이로 인한 문제 해결
2. 배포를 자동화 및 안정적
3. 협업과 운영에 효율적

🖋 Docker 사용하기 전 후

과거에는 서버에 프로그램을 설치할 때 아래의 문제들이 있었음. 운영체제에 따라 설치 방법 다름. 다른 사람 PC나 서버에 올리면 잘 되던 것이 안되는 문제가 생김. 개발환경과 운영 환경이 달라서 배포 후에 오류가 나는 일이 잦음.

• 예전 방식
  • 직접 서버에 설치
  • 환경 세팅 복잡 및 오류
  • 운영 환경과 개발 환경의 차이
• Docker 방식
  • 컨테이너 안에 설치
  • 파일 하나로 모든 환경 정의
  • 어디서든 동일한 환경 제공
  • 같은 Docker 이미지 사용하므로 환경 동일

나는 SpringBoot로 API 개발을 하고있었다. 게시글 등록을 구현 후 Swagger로 테스트 했는데 아래와 같은 상태코드가 반환되었다. status : 415 error : Unsupported Media Type

2. 왜 이런..?

나는 Controller 에서 consumes = MediaType.MULTIPART_FORM_DATA_VALUE로 지정하여 요청을 multipart/form-data 형식으로 보내겠다고 지정했다. 그리고 데이터를 받아올 때 @RequestBody 로 받아오라고 지정했다. 결론부터 말하면 @RequestBody 로 받아온 것이 문제였다. @RequestBody 는 multipart/form-data 형식을 처리할 수 없기 때문에 415 에러가 발생했다.

✒️ @RequestBody와 @ModelAttribute의 차이점

@RequestBody 와 @ModelAttribute 는 서로 다른 방식으로 요청 데이터를 처리한다. @RequestBody 는 HTTP 요청의 본문(body) 데이터를 바인딩하고, @ModelAttribute 는 폼 데이터와 같은 요청 파라미터를 객체에 바인딩하는 데 사용된다.

@RequestBody

• JSON, XML, 텍스트 등 요청 본문에 포함된 데이터를 객체로 변환하는 데 사용
• application/json이나 application/xml 같은 Content-Type과 함께 사용

  @ModelAttribute

• 폼 데이터를 객체에 바인딩하는 데 사용
• multipart/form-data로 전송된 데이터를 객체의 필드에 매핑가능
• 폼 데이터 내에서 파일뿐만 아니라 일반 텍스트 값도 함께 받을 수 있음

3. 해결

@RequestBody 대신 @ModelAttribute 를 사용했더니 정상적으로 실행되었다.

1. 직접 접근 제한 (Access Restriction)

WEB-INF 폴더는 클라이언트(브라우저)에서 직접 접근할 수 없는 보호된 경로. http://localhost:8080/WEB-INF/index.jsp 로 접근해도 404 발생. jsp 파일을 WEB-INF 폴더 안에 두면 클라이언트가 직접 접근하지 못하도록 보호 가능. 즉, servlet을 거쳐야만 접근이 가능

2. 보안 강화 (Security)

jsp 파일을 WEB-INF 폴더 밖에 두면 클라이언트가 직접 접근 가능해서 jsp 내부에서 처리하는 로직이 노출될 가능성 있음. 민감한 페이지(관리자페이지 같은..)는 WEB-INF 폴더 안에 두는 것이 안전.

1. 나의 코드

servlet --> service --> dao 요청이 들어오면 JDBC 드라이버 로드 후 해당 쿼리 수행

// 예시 - BoardDAO.java
    /**
     * 게시물 총 개수
     * @return
     * @throws SQLException
     */
    public int selectCnt() throws SQLException {
        int cnt = 0;
        JdbcUtil jdbcUtil = new JdbcUtil();

        try(Connection conn = jdbcUtil.getConnection();
            Statement stmt = conn.createStatement();) {
            String sql = "SELECT COUNT(*) FROM BOARD";

            try(ResultSet rs = stmt.executeQuery(sql)) {
                if (rs.next()) {
                    cnt = rs.getInt(1);
                }
            }
        }
        return cnt;
    }

// 예시 - JdbcUtil.java
/**
 * JDBC 공통화
 */
public class JdbcUtil {
    private final String DB_URL = "jdbc:mysql://localhost:3306/ebrainsoft_study";
    private final String USER = "ebsoft";
    private final String PASS = "ebsoft";

    private static JdbcUtil jdbcUtil;

    public static JdbcUtil getJdbcUtil() throws ClassNotFoundException {
        if (jdbcUtil == null) {
            Class.forName("com.mysql.cj.jdbc.Driver");
            jdbcUtil = new JdbcUtil();
        }
        return jdbcUtil;
    }

    public Connection getConnection() throws SQLException {
        return DriverManager.getConnection(DB_URL, USER, PASS);
    }
}

2. 나의 문제

Class.forName() 호출의 부적절성

Class.forName("com.mysql.cj.jdbc.Driver")는 JDBC 드라이버를 메모리에 로드하는 역할을 한다. 이 코드가 각 DAO의 메서드에서 매번 호출하면 매번 데이터 베이스 연결을 시도할 때마다 드라이버를 로드한다. 이는 불필요한 리소스 낭비이며 성능을 저하시킬 수 있다. 일반적으로 JDBC 드라이버 로딩은 애플리케이션 시작 시 한번만 수행해야한다.

3. 해결방안

1) web.xml 에서 <load-on-startup> 설정 추가

servlet이 시작될 때 JDBC 드라이버를 미리 로드하도록 설정해야한다.

<!-- web.xml에 아래 코드 추가 -->
<servlet>
    <servlet-name>DBInitServlet</servlet-name>
    <servlet-class>com.study.connection.DBInitServlet</servlet-class>
    <load-on-startup>1</load-on-startup>
</servlet>

• <servlet> : 서블릿을 정의하는 부분. 서블릿은 클라이언트의 요청을 처리하는 java 클래스
• <servlet-name> : 서블릿의 이름을 정의. 서블릿을 식별하는 데 사용.
• <servlet-class> : 서블릿 클래스의 전체 경로를 지정. 이 클래스는 서블릿 인터페이스를 구현하여 요청을 처리하는 로직을 담고있음.
• <load-on-startup> : 서블릿이 언제 로드될지 지정. 값이 1이면 웹 애플리케이션이 시작될 때 서블릿을 초기화하도록 지정. 즉, 서버가 시작할 때 자동으로 이 서블릿을 로드하고 초기화. 값이 0이면 서블릿은 클라이언트 요청이 있을 때 로드.

2) JDBC 드라이버 설정

서블릿이 서버 시작 시 실행되면서 JDBC 드라이버가 미리 로드됨. "No suitable driver" 에러 해결.

package com.example;

import javax.servlet.ServletException;
import javax.servlet.http.HttpServlet;

public class DBInitServlet extends HttpServlet {
    @Override
    public void init() throws ServletException {
        try {
            Class.forName("com.mysql.cj.jdbc.Driver");
            System.out.println("MySQL JDBC Driver Loaded Successfully!");
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
    }
}

결론 : DAO 파일에서 JDBC driver load 하면 안된다.

찾게 되었다기 보다는 발견했다고 말하는 것이 맞겠다. 코딩테스트 공부를 해야겠다고 마음 먹고 백준 문제를 풀던 중.. 백준 메인 화면 광고에 이 스터디가 나와서 알게되었다. 1일 1코테 습관을 들일 수 있도록 도와주고, 주제별 문제를 내주고, 매 주 특강까지?! 참가비가 3만원이면 치킨 한 마리 안먹으면 되니까 가격도 괜찮겠다 싶어 참여하게 되었다.

2. 99클럽 참여 경험

• 기간 : 5주
• 레벨 : 비기너
• 문제 : 문자열 / 스택 / 큐 / 해시 / 힙 / 정렬
• 인증
  • 코딩테스트 문제풀이 인증 (월-금)
  • TIL 작성 인증 (월-금)
  • 특강 수업 인증 (월)

일정 목표에 도달했을 때 각각의 상품이 있었다. 나는 아래의 상품을 얻었다!

문제의 난이도 및 구성

해당 주제에 대한 공부 몇시간 정도 한다면 어렵지 않았다. 하지만 가.끔 난이도 있는 문제가 주어져 지루하지 않았다. 일주일에 한 주제에 대해 문제가 주어진다. 꼭 필요한 개념을 확인할 수 있는 문제, 좀 더 나아가 생각을 더 해야하는 문제가 차례로 주어졌다. 문제에 집중하다 보면 점점 성장해지고 있는 나를 발견하게 된다.

좋았던 점

하루 문제가 주어지면 문제와 함께 권장시간이 주어진다. 이 권장시간 안에 풀어야지! 라는 승부욕과 시간 안에 풀었을 때의 성취감은 두배가 된다. 더해서 각 부분의 보상! 각 보상을 최대로 받을 때 참가비 3만원을 네이버페이로 그대로 돌려받을 수 있다. 난 비록 실패했지만.. 받으신분들 대단해요.. 또한 빠른 운영진들의 대응이 좋았다. 오픈카톡이 있는데 스터디를 시작하는 날에 레벨을 바꿔달라는 요청이 적지 않았다. 스터디 시작하는 날에는 변경이 어렵다고 공지 했음에도 바꿔주신걸로 기억한다. 특강 때도 문제는 없는지 각 레벨방에 들어가서 모니터링을 해주신다. 특강을 녹화하여 녹화본을 제공해주고 오픈카톡에서 문제 제공해주실 때 응원의 한마디까지 쏘 스윗 쏘 친절 그 잡채다.

아쉬웠던 점

먼저 특강 시간에 여유가 없다. 매주 월요일에 특강 30분, 보너스 문제 풀기 30분, 보너스 문제 풀이 30분, TIL 발표 30분 이렇게 2시간이 채워진다. 특강 때 시간 맞춰 끝나는 경우도 있지만, 네트워크 문제나 강의할 내용이 많을 때 시간이 부족한 경우가 있었다. 나는 더 이해하고 끝나고 싶은데.. 보너스 문제는 다른 날에 줘도 괜찮으니 특강 시간을 더 늘려줬으면 하는 바램이 있다. 그리고 발표를 하면 결석 면제권이 주어지는데 이 결석 면제권이 문제풀이 면제권인지, TIL 면제권인지, 특강 면제권인지, 하루 면제권인지 사전에 공지해준 기억이 없다. 다 끝나고 문제풀이에만 적용된다고 하니 당황스러운 사람이 없지 않아 있을 것 같다. 물론 내가 공지 못 본걸 수도 있음..

3. 개인 성장 및 결과

가장 큰 성장은 내가 백준 티어 실버에 갔다는 것이다!!
다른 사람들은 별거 아니겠지만
갈색에서 파란색 보았을 때의 짜릿함이란.. 엄청 기분 좋았다.
그리고 문제를 볼 때 이렇게 풀면 되는군 이런 감이 조금 늘었다. 기분 쵝오><
중간부터 다른 일정이 있어서 문제 풀 여유가 없어 많이 못하긴 했다..
하지만 이 후기를 작성하고 나서 시간이 되면 받았던 문제들을 풀어볼 것이다.
코딩테스트 문제 풀기에 도움을 준 항해99에게 감사드리며 다른 사람들에게도 적극 추천한다.

99클럽 소개 페이지

web.xml은 서버가 시작할 때 웹서버가 사용하는 환경설정 파일. 웹 애플리케이션 서비스 실행에 관한 전반적인 내용을 정의하는 환경설정 파일.

✒️ Servlet 버전별 정의

Servlet 2.X 이하

web.xml에 서블릿을 정의해야 했음.

<servlet>
    <servlet-name>hi</servlet-name>
    <servlet-class>com.study.Nana</servlet-class>
<servlet>
<servlet-mapping>
    <servlet-name>hi</servlet-name>
    <url-pattern>/hello</url-pattern>
</servlet-mapping>

Servlet 3.0 이상

web.xml 대신 클래스에 어노테이션을 사용하여 서블릿을 정의할 수 있음.

@WebServlet("/hello")
public class Nana extends HttpServlet {
    ...
}

web.xml의 web-app에 metadata-complete="false" 설정을 추가해야함. + metadata-complete="false" 설정 안해도 됨 참고 : https://www.oracle.com/technical-resources/articles/java/javaee6overview-part2.html?utm_source=chatgpt.com

#Heap #PriorityQueue 백준 실버3) 크리스마스 선물

문제풀이

우선순위 큐를 사용하여 문제를 해결했다. 우선순위 큐는 기본적으로 우선순위가 큰 것(작은 값)을 먼저 반환하는데 -> 오름차순 Collections.reverseOrder()를 생성자 인자로 주어 그 반대로 정렬되도록 했다. -> 내림차순 ez했다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();

        // 아이들과 거점지를 방문한 횟수 n
        int n = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 거점지에서 a개의 선물을 충전
            int a = Integer.parseInt(st.nextToken());
            if (a == 0) { // 아이들을 만남
                if (q.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(q.poll()).append("\n");
                }
            } else { // 선물 충전
                for(int j=0; j<a; j++) {
                    q.add(Integer.parseInt(st.nextToken()));
                }
            }
        }

        System.out.print(sb);
        br.close();
    }
}

#Heap #Array #PriorityQueue LeetCode 506. Relative Ranks 크기가 n인 정수 배열 score가 주어지며, 여기서 score[i]는 경기에서 i번째 선수의 점수입니다. 모든 점수는 고유합니다.

선수들은 점수에 따라 순위가 정해지는데, 1위 선수가 가장 높은 점수를 받은 사람, 2위 선수가 두 번째로 높은 점수를 받은 사람 등이 이에 해당합니다. 각 선수의 순위는 다음과 같이 결정됩니다.

• 1위 선수의 등급은 "Gold Medal"입니다.
• 2위 선수의 등급은 "Silver Medal"입니다.
• 3위 선수의 등급은 "Bronze Medal"입니다.
• 4위부터 n위까지의 선수의 경우, 순위는 배치 번호입니다. (즉, x위 선수의 순위는 "x"입니다.)

answer[i]가 i번째 선수의 순위인 n 크기의 배열 answer를 반환합니다.

[예시1] Input: score = [5,4,3,2,1] Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"] Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

[예시2] Input: score = [10,3,8,9,4] Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"] Explanation: The placements are [1st, 5th, 3rd, 2nd, 4th].

문제풀이

영어 울렁증이.. 어찌저찌 해석하여 풀어냈다..

import java.util.*;

class Solution {
    public String[] findRelativeRanks(int[] score) {
        Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        String[] answer = new String[score.length];

        // score를 q에 담기
        for(int i : score) {
            q.add(i);
        }

        // q가 비어있을 때 까지 반복.
        // 그 안에 score 반복문을 통해 q의 top값과 score의 요소가 같으면 answer에 String으로 변환하여 순위 저장
        int th = 1;
        while(!q.isEmpty()) {
            int e = q.poll();
            for(int i=0; i<score.length; i++) {
                if (e == score[i]) {
                    answer[i] = String.valueOf(th);
                    th++;
                }
            }
        }

        // 1, 2, 3위 설정
        for(int i=0; i<answer.length; i++) {
            boolean first = false;
            boolean second = false;
            boolean third = false;

            if (answer[i].equals("1")) {
                answer[i] = "Gold Medal";
            } else if (answer[i].equals("2")) {
                answer[i] = "Silver Medal";
            } else if (answer[i].equals("3")) {
                answer[i] = "Bronze Medal";
            } else if (first && second && third) {
                break;
            }
        }

        return answer;
    }
}

이 문제를 풀었긴 했지만 내 코드의 성능은 그다지 좋은 것 같지 않다..

다른방법

문제의 Editorial을 참고하여 코드를 작성했다.

import java.util.*;

class Solution {
    public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        int[] sCopy = new int[n];

        // score의 요소들을 sCopy배열에 복사
        System.arraycopy(score, 0, sCopy, 0, n);

        // 각 요소에 대한 인덱스를 map으로 저장
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<n; i++) {
            map.put(sCopy[i], i);
        }

        // sCopy 변수 오름차순 정렬
        Arrays.sort(sCopy);

        // 순위 매기기
        String[] answer = new String[n];
        for(int i=0; i<n; i++) {
            if (i == 0) {
                answer[map.get(sCopy[n-i-1])] = "Gold Medal";
            } else if (i == 1) {
                answer[map.get(sCopy[n-i-1])] = "Silver Medal";
            } else if (i == 2) {
                answer[map.get(sCopy[n-i-1])] = "Bronze Medal";
            } else {
                answer[map.get(sCopy[n-i-1])] = Integer.toString(i+1);
            }
        }

        return answer;
    }
}

공부한 내용정리

• System.arraycopy(src, srcPos, dest, destPos, length) : 더 빠름
  • 배열을 복사하여 다른 배열변수에 저장
  • Object src : 복사할 객체, 원본 배열
  • int srcPos : 복사 시작할 index
  • Object dest : 복사된 배열
  • int destPos : 원본으로부터 가져온 데이터를 복사된 배열의 몇번째 index부터 추가
  • int length : 카피되는 배열 요소 개수
• Arrays.copyOf(원본배열, 복사할길이) / Arrays.copyOfRange(A, from_index, to_index) : 더 느림
  • int[] A : 복사할 배열
  • int from_index : 복사할 배열의 시작 index
  • int to_index : 복사할 배열의 끝 index (복사할 끝 index값은 포함 안됨)
  • 새로운 배열을 return

#힙 #Heap #PriorityQueue 프로그래머스 2단계) 더 맵게

문제풀이

Heap 자료구조 문제를 풀 때 사용할 수 있는 클래스로 PriorityQueue가 있다는 것을 알고있었다. 큐 문제 공부할 때 알았지 후후 PriorityQueue 클래스는 값을 저장하면 안에서 자동으로 우선순위별 정렬을 해주는데, 값을 꺼낼 때 작은 값 부터 나온다는 특징이 이 문제를 풀기에 적합하다고 생각했다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        Queue<Integer> q = new PriorityQueue<>();
        int answer = 0;

        // scoville요소를 q에 담기
        for(int i : scoville) {
            q.add(i);
        }

        // q에서 첫번째 요소가 K보다 작을 때 까지
        // 만약, 첫번째 요소가 K보다 작지만 size가 1이면 break
        while(q.peek() < K) {
            if (q.size() == 1) {
                answer = -1;
                break;
            } else {
                int firstMin = q.poll();
                int secondMin = q.poll();
                q.add(firstMin + (secondMin*2));
                answer++;
            }
        }
        return answer;
    }
}

공부한 내용정리

• 자바에는 Heap 자료구조 기반으로 동작하는 PriorityQueue 클래스가 있다.
• PriorityQueue는 우선순위 큐라서 우선순위가 큰 값 (작은 값) 먼저 나온다.
• 내림차순으로 정렬하려면 생성자로 Collections.reverseOrder()를 사용해야 한다.
• 문자열과 문자는 유니코드(ASCII)값 기준으로 정렬한다. A, B, C, ..., a, b, c, ..., z

try-with-resouces의 resources는 외부 데이터 자원을 말한다. (DB, Network, File, ...) 이 외부 데이터에 접근 하려고 할 때, 외부 데이터를 처리하려고 할 때 예외가 발생할 수 있다.

그렇다면, 왜 try-catch-finally가 있는데 try-with-resources를 만들었을까? 이유는 아래의 코드 예시를 보면 알 수 있다.

이 코드는 dummy.txt 파일을 읽으려 하고 있다. 하지만 실제로 해당 파일은 존재하지 않으며 예외 처리를 하게 될 것이다.

import java.io.FileReader;
import java.io.IOException;

public class FileParsing {
    public static void main(String[] args) throws IOException {
        FileReader file = null;
        try {
            file = new FileReader("./dummy.txt");
        } catch (IOException e) {
            throw new IOException();
        } finally {
            file.close();
            // 해당 파일이 없어 예외 처리 후 finally문을 실행하려 함
            // file이 존재하지 않으므로 NullpointerException 발생
        }
    }
}

이 상황에서는 file이 null인지 확인하는 조건문을 넣어주면 해결할 수 있다. 하지만 그 밖에 다른 상황들이 finally에서 예외를 발생시킬 수 있다. 그래서 자동으로 자원을 닫아주기 위해 try-with-resources가 생겨난 것이다. (정확하게 예시를 못들겠네..)

✒️ file을 열고 꼭 close를 해야하는가?

파일을 닫지 않아고 당장은 큰 문제가 없긴 하다. 하지만 만약 소스 내 다른 곳에서 같은 파일에 접근하려고 한다면? 해당 파일은 열려있기 때문에 Lock이 걸려있다. 그러므로 다른 곳에서 사용하려고 해도 사용하지 못한다. 이러한 이유로 반드시 close를 해주어야 한다.

✒️ try-with-resources 사용방법?

try-with-resource는 try에 자원 객체를 전달하면 try의 코드블록이 끝났을 때 자동으로 자원을 종료해준다. 이때 try에 전달할 수 있는 자원은 AutoCloseable 인터페이스 구현체만 가능하다.

import java.io.FileReader;
import java.io.IOException;

public class FileParsing {
    public static void main(String[] args) throws IOException {
        // 복수의 자원 작성 가능
        // try가 끝나면 자원 자동 종료
        try (FileReader fileReader = new FileReader("./dummy.txt");
            FileReader fileReader2 = new FileReader("./dummy2.txt")) {
            // 파일 처리 내용
        }
    }
}

✒️ try-with-resource를 사용하는데 왜 또 throws IOException을 사용하는가?

try-with-resources는 예외 처리를 위한 것이라기 보다 예외가 발생하더라도 자원을 안전하게 종료하도록 하는 기능이라고 말하는 것이 맞다. 즉 try-with-resources는 자원 자동 종료만 수행하는 것이다. 그러므로 파일을 읽으려고 할 때 같은 처리를 하기 위해서는 따로 예외 처리를 해야만 한다.

#스택 #Stack #ArrayDeque 백준 실버4) 균형잡힌 세상

문제풀이

처음에 문제를 잘못 이해해서 애를 먹었다.. ( [ ) ] => no 이어야 하는데 yes 인줄.. ( ( ) ) ( [ ] ) ( ( ) ) [ [ ] ] => 이런 케이스들이 yes~

위의 기준과 예제를 참고하면서 열심히 코드를 작성했더니?! "틀렸습니다"

// )() 이 가정일 때 막힘. no 인데 yes 반환
// 위 가정일 때를 대비하여 짝이 맞지 않을 때 처리를 해줘야 함.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 소괄호, 대괄호 골라내어 저장 및 균형 체크
        while(true) {
            String s = br.readLine();
            ArrayDeque<Character> stack = new ArrayDeque<>();

            if (s.equals(".")) { // . 입력 시 종료
                break;
            } else {
                for(char c : s.toCharArray()) {
                    switch(c) {
                        case ']':
                        case ')':
                            if (!stack.isEmpty() && 
                                   ((c == ']' && stack.peek() == '[') || (c == ')' && stack.peek() == '('))) {
                                stack.pop();
                            }
                            break;
                        case '[':
                        case '(':
                            stack.push(c);
                            break;
                    }
                }
                sb.append(stack.size() > 0 ? "no" : "yes").append("\n");
            }
        }
        System.out.println(sb);
        br.close();
    }
}

그렇다. 내가 작성한 코드는 처음에 닫는 괄호가 나오는 케이스를 생각하지 못한 것이다. 스택이 비어있거나, 짝이 맞지 않는 경우에는 boolean 변수를 추가하여 구분할 수 있도록 했다.

// 19136KB    184ms
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 소괄호, 대괄호 골라내어 저장 및 균형 체크
        while(true) {
            String s = br.readLine();

            if (s.equals(".")) { // . 입력 시 종료
                break;
            } else {
                ArrayDeque<Character> stack = new ArrayDeque<>();
                boolean isBalanced = true;
                for(char c : s.toCharArray()) {

                    switch(c) {
                        case ']':
                        case ')':
                            if (!stack.isEmpty() && 
                                   ((c == ']' && stack.peek() == '[') || (c == ')' && stack.peek() == '('))) {
                                stack.pop();
                            } else {
                                isBalanced = false; // 짝이 맞지 않으면 불균형
                            }
                            break;
                        case '[':
                        case '(':
                            stack.push(c);
                            break;
                    }
                }
                if (isBalanced && stack.isEmpty()) {
                    sb.append("yes\n"); // 균형이 맞다면 yes
                } else {
                    sb.append("no\n"); // 불균형이면 no
                }
            }
        }
        System.out.println(sb);
        br.close();
    }
}

첫번째로 작성한 코드에서 도저히 모르겠어서 GPT의 도움을 받았다.. 답을 보고 나니 좀 더 생각해볼걸 그랬나 싶다.

공부한 내용정리

• 맞는지, 아닌지 확인할 때 boolean 변수를 활용하자.

#큐 #Queue #ArrayDeque 백준 실버4) 식당 메뉴

문제풀이

이 문제.. 나로서는 풀기가 상당히 어려웠다.. 문제를 맞췄을 때 실행 시간 보고 한번 놀랐고 다른 사람들과 비교했을 때 내 시간이 꽤나 오래걸려서 두번 놀랐다. 그래도 결국 맞춰서 기분은 좋다><

문제에서는 문자열 유형을 1 a b (a: 학생번호, b: 식사메뉴) => 학생 대기 2 b (b: 식사메뉴) => 배식 이렇게 나누고 있었다.

나는 학생이 원하는 식사 메뉴를 큐에 담고 메뉴가 나오면 원하는 메뉴인지, 원하지 않는 메뉴인지에 따라 나누면 되겠구나 생각했다. 그런데 학생이 원하는 식사 메뉴를 큐에 담으면 학생 번호는 어떻게 해야하는거지..? 라는 생각에 Map이 바로 떠올랐다. 그러면서 Key가 중복되어도 상관이 없고, 순서가 있도록 하는 방법이 없나 생각하다가 List<Map.Entry<Integer,Integer>>로 풀어야겠다고 생각했다. [시간초과]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());

        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            if (st.nextToken().equals("1")) {
                // 학생번호, 음식번호 저장
                int key = Integer.parseInt(st.nextToken());
                int value = Integer.parseInt(st.nextToken());
                list.add(new AbstractMap.SimpleEntry<>(key, value));
            } else {
                // 음식 비교 및 그룹 나누기기
                if (list.size() > 0) {
                    Map.Entry<Integer, Integer> map = list.get(0);
                    if (map.getValue() == Integer.parseInt(st.nextToken())) {
                        A.add(map.getKey());
                    } else {
                        B.add(map.getKey());
                    }
                    list.remove(0);
                }
            }
        }

        // 출력
        // A
        if (A.size() > 0) {
            A.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
            for (Integer a : A) {
                sb.append(a).append(" ");
            }
        } else {
            sb.append("None");
        }

        sb.append("\n");

        // B
        if (B.size() > 0) {
            B.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
            for (Integer b : B) {
                sb.append(b).append(" ");
            }
        } else {
            sb.append("None");
        }

        sb.append("\n");

        // C
        if (list.size() > 0) {
            Collections.sort(list, Map.Entry.comparingByKey()); // 오름차순 정렬
            for (Map.Entry<Integer, Integer> m : list) {
                sb.append(m.getKey()).append(" ");
            }
        } else {
            sb.append("None");
        }

        System.out.println(sb);
        br.close();
    }
}

이 코드로 작성하면서도 이게 맞나.. 싶었지만 그래도 끝까지 해보는 것도 중요하다고 생각하여 끝까지 작성해봤다. 이 방법이 아니라면 어떻게 학생번호를 저장하면서 학생이 원하는 메뉴도 저장하지..? 생각하던 중 내 코드에서 List<Map.Entry<Integer,Integer>>를 학생 목록 C로 출력한 것이 보여서

아! List<Map.Entry<Integer,Integer>> 대신 A,B와 똑같이 학생 목록 담을 곳을 List로 만들면 되겠군! 학생은 C에 넣고 학생이 원하는 메뉴는 ArrayDeque에 넣어서 메뉴가 나오면 ArrayDeque의 값을 빼서 비교하여 A와 B에 알맞게 넣어주고 C에 있는 값은 제거하면 될 것 같았다. [결과] 189952KB 2916ms ++ 다른 날 같은 코드를 다시 제출했더니 시간초과 뜸.. 통과는 운이 좋았던건가..

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Deque<Integer> queue = new ArrayDeque<>();
        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            if(st.nextToken().equals("1")) {
                int student = Integer.parseInt(st.nextToken());
                int menu = Integer.parseInt(st.nextToken());

                C.add(student);
                queue.add(menu);
            } else {
                int menu = Integer.parseInt(st.nextToken());

                if (C.size() > 0 && !queue.isEmpty()) {
                    if(menu == queue.remove()) {
                        A.add(C.get(0));
                    } else {
                        B.add(C.get(0));
                    }
                    C.remove(0);
                }
            }
        }

        // 출력
        if (A.size() > 0) {
            A.sort((a,b) -> a.compareTo(b));
            for(Integer a : A) {
                sb.append(a).append(" ");
            }
        } else {
            sb.append("None");
        }
        sb.append("\n");
        if (B.size() > 0) {
            B.sort((a,b) -> a.compareTo(b));
            for(Integer b : B) {
                sb.append(b).append(" ");
            }
        } else {
            sb.append("None");
        }
        sb.append("\n");
        if (C.size() > 0) {
            C.sort((a,b) -> a.compareTo(b));
            for(Integer c : C) {
                sb.append(c).append(" ");
            }
        } else {
            sb.append("None");
        }
        System.out.println(sb);
        br.close();
    }
}

다른방법

이 문제를 풀었긴 했지만 내 코드는 메모리 사용량도 많고 시간도 오래걸리는 편이었다.. 다른 사람의 코드를 참고하여 다시 풀어보았다. [기존방법] 189952KB 2916ms [다른방법] 203364KB 1376ms

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        Deque<int[]> queue = new ArrayDeque<>();

        int n = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            if(st.nextToken().equals("1")) {
                int student = Integer.parseInt(st.nextToken());
                int menu = Integer.parseInt(st.nextToken());

                queue.add(new int[]{student, menu});
            } else {
                int menu = Integer.parseInt(st.nextToken());

                if (!queue.isEmpty()) {
                    if(menu == queue.peek()[1]) {
                        A.add(queue.poll()[0]);
                    } else {
                        B.add(queue.poll()[0]);
                    }
                }
            }
        }

        // 출력
        // A
        if (A.size() > 0) {
            A.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
            for(Integer a : A) {
                sb.append(a).append(" ");
            }
        } else {
            sb.append("None");
        }
        sb.append("\n");
        // B
        if (B.size() > 0) {
            B.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
            for(Integer b : B) {
                sb.append(b).append(" ");
            }
        } else {
            sb.append("None");
        }
        sb.append("\n");
        // C
        if (queue.size() > 0) {
            List<Integer> C = new ArrayList<>();
            for(int[] i : queue) {
                C.add(i[0]);
            }
            C.sort((a,b) -> a.compareTo(b)); // 오름차순 정렬
            for(Integer c : C) {
                sb.append(c).append(" ");
            }
        } else {
            sb.append("None");
        }
        System.out.println(sb);
        br.close();
    }
}

시간은 줄었지만 메모리 사용량은 더 많아진 아이러니한.. 확실하진 않지만 원인을 적어보았다.

메모리 사용량 증가 원인?

1. 배열을 사용하여 큐에 저장? 기존 방법으로는 Deque<Integer>를 사용하여 단일 값만 저장했지만 다른 방법으로는 Deque<int[]>을 사용하여 다중 값을 저장

   속도 증가 원인?

2. C 변수의 원소 제거 (ArrayList의 remove) ArrayList의 첫번째 요소를 제거하면, 뒤의 모든 요소를 한 칸씩 앞으로 이동해야 함으로 O(n)의 시간복잡도를 가짐 ArrayDeque의 poll()을 사용하여 O(1)로 제거하여 속도 빠름

공부한 내용정리

• ArrayList의 정렬방법
  • Collection.sort(list) - 오름차순
  • list.sort((a,b) -> a.compareTo(b)) - 오름차순
  • list.sort((a,b) -> b.compareTo(a)) - 내림차순

#큐 #Queue #ArrayDeque #LinkedList #PriorityQueue 백준 실버4) 큐

문제풀이

큐 클래스에 있는 메서드 기능들을 알면 그리 어려운 문제는 아니었다. 스택 문제와 비슷하게 풀어냈다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        int n = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            switch(st.nextToken()) {
                case "push":
                    queue.offer(Integer.parseInt(st.nextToken()));
                    break;
                case "pop": 
                    sb.append(queue.isEmpty() ? -1 : queue.poll()).append("\n");
                    break;
                case "size":
                    sb.append(queue.size()).append("\n");
                    break;
                case "empty":
                    sb.append(queue.isEmpty() ? 1 : 0).append("\n");
                    break;
                case "front":
                    sb.append(queue.isEmpty() ? -1 : queue.getFirst()).append("\n");
                    break;
                case "back":
                    sb.append(queue.isEmpty() ? -1 : queue.getLast()).append("\n");
                    break;
                default:
                    break;
            }
        }
        System.out.println(sb);
        br.close();
    }
}

Queue

✒️ add() 와 offer() 의 차이

add() 와 offer() 는 값을 추가하는 기능을 가지고 있다. 그런데 같은 기능을 두 개 가지고 있을 필요가 있을까? 둘의 차이를 알아보기로 했다.

두 메서드는 새로운 요소를 추가하는 역할을 하지만 동작 방식이 다르다. 가장 큰 차이점은 예외(Exception) 발생 여부에 있다.

• add(E e)
  • 성공하면 true 반환
  • Queue가 가득 차면 예외 발생 (IllegalStateException)
  • Queue가 가득 찰 일이 없을 때 적절
  • 예외 발생을 원할 때 적절
• offer(E e)
  • 성공하면 true 반환, 실패하면 false 반환
  • 큐가 가득 차도 예외 발생 안함
  • Queue가 가득 찰 가능성이 있을 때 적절
  • 실패를 예상하고 대비할 때 적절

✒️ ArrayDeque , LinkedList , PriorityQueue 차이

세 클래스 모두 Queue 인터페이스를 구현한 클래스들이지만 내부 동작 방식과 사용 목적이 다르다.

ArrayDeque

• 배열을 기반으로 하는 Deque(Double-Ended-Queue) 구현체
• FIFO(Queue)와 LIFO(Stack) 모두 가능
• 중간 삽입/삭제가 비효율적
• 앞뒤 삽입/삭제는 빠름
• 내부적으로 Resizable Array(크기가 자동 조절되는 배열) 사용
• LinkedList 보다 메모리 사용량이 적음 (노드 객체 따로 만들 필요 없음)
• 앞/뒤 삽입/삭제 O(1)
• 중간 삽입/삭제 O(N) (배열을 이동하기 때문)
• 빠른 앞/뒤 삽입 및 삭제가 필요할 때 적절 (ex. Deque를 이용한 BFS)

  LinkedList

• 이중 연결 리스트(Dobly Linked List) 기반 Queue
• 중간 삽입/삭제가 필요할 때 유리
• 메모리 사용량이 상대적으로 많음
• 노드 기반으로 동작 (배열이 아니라 객체들이 연결된 형태)
• ArrayDeque 보다 메모리를 더 많이 사용함 (각 노드가 추가적인 포인터를 가짐)
• Deque 인터페이스를 구현해서 ArrayDeque와 비슷하게 사용 가능
• 앞/뒤 삽입/삭제 O(1)
• 중간 삽입/삭제 O(1)~O(N) (리스트를 순회해서 위치를 찾아야 함)
• 중간 삽입/삭제가 빈번한 경우 적절
• 데이터 크기가 변동이 심하고 크기 예측이 어려운 경우 적절 (배열보다 유연)

  PriorityQueue

• 우선순위가 높은 요소가 먼저 나오는 Queue
• Heap(힙) 자료구조 기반
• FIFO가 아닌 우선순위 순서대로 정렬됨
• 내부적으로 Min Heap(기본 : 작은 값) 나옴
• 요소가 들어올 때마다 자동으로 정렬됨
• 앞/뒤 삽입/삭제 O(log N) (힙 정렬 때문)
• 중간 삽입/삭제 불가능 (힙 구조는 중간 삽입 개념이 없음)
• 항상 최댓값 또는 최솟값을 따르게 찾아야 할 때 적절
• 우선순위가 중요한 작업 스케줄링, 경로 탐색이 필요할 때 적절

#스택 #Stack #ArrayDeque 백준 브론즈2) 막대기

문제풀이

처음에 입력받은 m을 push 하기 전, 비어있는지 확인하고 비어있다면 push 비어있지 않다면 현재 stack의 size 반복문으로 top과 m을 비교하여 남은 stack의 수를 출력하려고 했다. top <= m 이면 pop(), push(m), break top > m 이면 push(m), break 그런데 해당 풀이 방식은 아래의 테스트 케이스에는 어긋난다. (아래) 9 4 3 6 5 (위) => (아래) 9 4 6 5 (위) 9 : push 4 : push 3 : push 6 : 3 pop, 6 push 5 : push

그런데 계속 보다보니.. stack은 top의 값과 top 아래의 값을 1:1로 비교하는 횟수가 n-1번이라는 것을 찾아냈다❗ 예) (아래) 6 4 6 7 9 6 (위)

1. 6 과 9 비교 => pop()
2. 9 와 7 비교 => pop()
3. 7 과 6 비교 => pop()
4. 6 과 4 비교 => pop()
5. 4 와 6 비교 => pop()

그렇다면 값들을 모두 stack에 push한 후 n-1번 반복하여 가장 큰 값과 비교를 하면 되겠구나 생각했다. 여기서 가장 큰 값은 비교한 값들 중 가장 높은 값을 의미한다. 예) (아래) 9 4 3 6 5 (위) 가장 오른쪽(top) 값을 꺼내어 해당 값을 pop이라고 하자. pop과 stack의 top을 비교했을 때, pop < stack.peek() 라면 +1, stack.peek()가 pop이 된다. pop >= stack.peek() 라면 그냥 stack을 pop한다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for(int i=0; i<n; i++) {
            int m = Integer.parseInt(br.readLine());
            stack.push(m);
        }

        int pop = stack.pop();
        int cnt = 0;
        for(int i=0; i<n-1; i++) {
            if (pop < stack.peek()) {
                cnt++;
                pop = stack.pop();
            } else if (pop >= stack.peek()) {
                stack.pop();
            }
        }
        // 맨 오른쪽 막대기 포함 (+1)
        System.out.println(cnt+1);
        br.close();
    }
}

다른방법

1. pop 할 때 while 반복문 사용 위에서 처음에 시도했던 방법이 특정 테스트 케이스에서 원하는 값이 나오지 않아 다른 방법으로 풀었었다. 하지만 while 반복문을 사용하여 구현할 수 있었다. (아래) 9 4 3 6 5 (위) => (아래) 9 6 5 (위) 9 : push 4 : push 3 : push 6 : while 조건 해당, 3 pop, 4 pop, 6 push 5 : push

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i=0; i<n; i++) {
            int height = Integer.parseInt(br.readLine());

            // 스택이 비어있지 않고 현재 막대기의 높이가 스택의 맨 위 막대기보다 크다면
            while (!stack.isEmpty() && height >= stack.peek()) {
                stack.pop(); // 스택에서 맨 위의 막대기 제거
            }
            stack.push(height); // 현재 막대기를 스택에 추가
        }

        System.out.println(stack.size()); // 스택에 남아있는 막대기는 보이는 막대기들
        br.close();
    }
}

공부한 내용정리

• stack은 top의 값과 top 아래의 값을 1:1로 비교하는 횟수가 n-1번이다.
• while 반복문으로 pop하면 top의 값이 계속 변한다.

#스택 #Stack #ArrayDeque 백준 실버4) 스택

문제풀이

문제에서 거의 다 알려주었다. Stack에 대하여 알고있다면 어렵지 않은 문제이다.

1. 명령의 수 n 입력받음
2. 입력받은 명령어를 switch로 처리 2-1. StringTokenizer를 사용하여 첫번째 입력 문자열을 switch문과 비교 2-2. push, pop, size, ... 에 알맞게 처리

❗java.util.EmptyStackException

첫번째 시도 후 해당 에러가 발생했다. 찾아보니 pop과 top을 처리할 때는 항상 stack의 내용이 비어있는지 확인해야 된다고 한다. (나는 top을 처리할 때 empty 여부를 안했음..) 수정하고 다시 제출하니 정상적으로 실행되었다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "push":
                    stack.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    System.out.println(stack.empty() ? -1 : stack.pop());
                    break;
                case "size":
                    System.out.println(stack.size());
                    break;
                case "empty":
                    System.out.println(stack.empty() ? 1 : 0);
                    break;
                case "top":
                    System.out.println(stack.empty() ? -1 : stack.peek());
                    break;
                default:
                    break;
            }
        }
        br.close();
    }
}

다른방법

1. Stack 대신 ArrayDeque 사용

ArrayDeque는 Stack이기도 하고 Queue이기도 하다. ArrayDeque가 더 빠르다고 했지만 해당 문제에서 큰 차이를 보이진 못함. [기존방법] 18876KB 288ms [다른방법] 19356KB 284ms

• Stack

  • 동기화됨 (Thread-Safe)
  • Vector<E> 상속받음 (동기화도 해당 클래스 덕분)
  • 상대적으로 느림 (동기화 때문)
  • Stack 전용 (LIFO)

• ArrayDeque

  • 동기화되지 않음 (Not Thread-Safe)
  • AbstractCollection<E> 상속받음
  • 더 빠름 (비동기)
  • Stack + Queue (LIFO & FIFO)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "push":
                    stack.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    System.out.println(stack.isEmpty() ? -1 : stack.pop());
                    break;
                case "size":
                    System.out.println(stack.size());
                    break;
                case "empty":
                    System.out.println(stack.isEmpty() ? 1 : 0);
                    break;
                case "top":
                    System.out.println(stack.isEmpty() ? -1 : stack.peek());
                    break;
                default:
                    break;
            }
        }
        br.close();
    }
}

2. 출력 방식에 따라 속도가 이렇게나?

다른 사람들과 메모리, 시간을 비교했더니 시간이 나보다 훨씬 빠른 사람들이 있었다. 코드를 확인해보니 출력하는 방식에 차이가 있었다. 나는 StringBuilder로 바꿔서 다시 해보니 속도가 빨라진 것을 확인할 수 있었다. [기존방법] 18876KB 288ms [다른방법] 18820KB 152ms

참고) 백준 - 출력 속도 비교

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "push":
                    stack.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    sb.append(stack.isEmpty() ? -1 : stack.pop()).append('\n');
                    break;
                case "size":
                    sb.append(stack.size()).append('\n');
                    break;
                case "empty":
                    sb.append(stack.isEmpty() ? 1 : 0).append('\n');
                    break;
                case "top":
                    sb.append(stack.isEmpty() ? -1 : stack.peek()).append('\n');
                    break;
                default:
                    break;
            }
        }
        System.out.println(sb);
        br.close();
    }
}

공부한 내용정리

• Stack에서 pop과 peek를 사용할 때는 항상 데이터가 없는지 확인해야 한다. 확인하지 않으면 java.util.EmptyStackException 발생
• Stack과 비슷한 ArrayDeque클래스가 있다. 이 클래스는 스레드에 안전하지 않지만 Stack보다 더 빠르고 Stack처럼 사용 할 수도 Queue처럼 사용 할 수도 있다.

정렬에 대하여 이론만 아는 것 같아서 하나씩 구현해보기로 했다.

2750) 수 정렬하기 _브론즈2

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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

✒️ 내가 푼 과정

버블 정렬은 첫번째 요소부터 끝 요소까지 옆의 요소를 비교하여 정렬한다. n개의 정수가 있을 때 이 과정은 최대 n번 반복한다.

최대반복 예시 입력

5 5 4 3 2 1

해당 예시 버블정렬 과정

5 4 3 2 1

• 5와 4를 비교 : 5 > 4 이므로 교환 => 4 5 3 2 1
• 5와 3을 비교 : 5 > 3 이므로 교환 => 4 3 5 2 1
• 5와 2를 비교 : 5 > 2 이므로 교환 => 4 3 2 5 1
• 5와 1을 비교 : 5 > 1 이므로 교환 => 4 3 2 1 5

4 3 2 1 5

• 4와 3을 비교 : 4 > 3 이므로 교환 => 3 4 2 1 5
• 4와 2를 비교 : 4 > 2 이므로 교환 => 3 2 4 1 5
• 4와 1을 비교 : 4 > 1 이므로 교환 => 3 2 1 4 5
• 4와 5를 비교 : 4 < 5 이므로 교환X => 3 2 1 4 5

3 2 1 4 5

• 3과 2를 비교 : 3 > 2 이므로 교환 => 2 3 1 4 5
• 3과 1을 비교 : 3 > 1 이므로 교환 => 2 1 3 4 5
• 3과 4를 비교 : 3 < 4 이므로 교환X => 2 1 3 4 5
• 4과 5를 비교 : 4 < 5 이므로 교환X => 2 1 3 4 5

2 1 3 4 5

• 2와 1을 비교 : 2 > 1 이므로 교환 => 1 2 3 4 5
• 2와 3을 비교 : 2 < 3 이므로 교환X => 1 2 3 4 5
• 3과 4를 비교 : 3 < 4 이므로 교환X => 1 2 3 4 5
• 4와 5를 비교 : 4 < 5 이므로 교환X => 1 2 3 4 5

1 2 3 4 5

• 정렬 완료

일반반복 예시 입력

5 5 4 1 3 2

해당 예시 버블정렬 과정

5 4 1 3 2

• 5와 4를 비교 : 5 > 4 이므로 교환 => 4 5 1 3 2
• 5와 1을 비교 : 5 > 1 이므로 교환 => 4 1 5 3 2
• 5와 3을 비교 : 5 > 3 이므로 교환 => 4 1 3 5 2
• 5와 2를 비교 : 5 > 2 이므로 교환 => 4 1 3 2 5

4 1 3 2 5

• 4와 1을 비교 : 4 > 1 이므로 교환 => 1 4 3 2 5
• 4와 3을 비교 : 4 > 3 이므로 교환 => 1 3 4 2 5
• 4와 2를 비교 : 4 > 2 이므로 교환 => 1 3 2 4 5
• 4와 5을 비교 : 4 < 5 이므로 교환X => 1 3 2 4 5

1 3 2 4 5

• 1과 3을 비교 : 1 < 3 이므로 교환X => 1 3 2 4 5
• 3과 2를 비교 : 3 > 2 이므로 교환 => 1 2 3 4 5
• 3과 4를 비교 : 3 < 4 이므로 교환X => 1 2 3 4 5
• 4와 5를 비교 : 4 < 5 이므로 교환X => 1 2 3 4 5

1 2 3 4 5

• 정렬 완료

  코드 작성

  n개의 수가 있을 때, 옆 요소와 n-1번 비교 하는 과정을 최대 n번 반복한다. 이것을 2중 반복문으로 풀어냈다. 지금 생각해보면 왜 n번 반복한다고 생각했는지 의문,,

  import java.io.*;
  

public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 수 입력 받기 int n = Integer.parseInt(br.readLine()); int[] arr = new int[n];

    for(int i=0; i<n; i++) {
        arr[i] = Integer.parseInt(br.readLine());
    }

    // 버블정렬 (Bubble Sort)
    for(int i=0; i<n; i++) {
        for(int j=0; j<n-1; j++) {
            // 오른쪽 요소의 값이 더 크다면 교환
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

    // 출력
    for(int i=0; i<n; i++) {
        System.out.println(arr[i]);
    }
    br.close();
}

}

## ✒️ 피드백 (chatGPT)
문제와 내 코드를 올려주니 아래와 같은 피드백을 받았다.
그런데 성능차이는 별로 없었음..
#### 1. 불필요한 연산
i는 n-1까지 반복되는 것임. (나는 i가 n까지 반복되게함)
ex) 5개의 수는 4번의 과정을 거치면 버블정렬 결과가 나옴.
j는 n-1-i까지 반복되는 것임. (나는 j가 n-1까지 반복되게함)
ex) 5개의 수는 최악의 상황일 때 거듭할 수록 비교를 1번씩 적게 하기 때문에 -i를 추가해야함.
#### 2. 정렬이 이미 완료된 이후에도 계속 실행
i의 반복문은 n-1까지 반복되지만 이는 최악의 상황이고 그 전에 정렬이 끝날 수도 있음.
그렇다면 이미 정렬이 된 상태에서 불필요한 비교가 발생.
```java
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 버블정렬 (Bubble Sort) 최적화
        for(int i=0; i<n-1; i++) {
            boolean swapped = false; // 교환 발생 여부 확인

            for(int j=0; j<n-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    swapped = true; // 교환 발생 시
                }
            }

            if (!swapped) break; // 교환 없을 시 반복문 조기 종료
        }

        for(int i=0; i<n; i++) {
            System.out.println(arr[i]);
        }
        br.close();
    }
}

의존성 충돌? 소프트웨어 프로젝트에서 특정 라이브러리나 패키지가 서로 다른 버전의 동일한 라이브러리를 요구할 때 발생하는 문제. 이로 인해 빌드 실패, 런타임 오류 등 예기치 않은 동작이 발생할 수 있음.

✒️ 왜 의존성 충돌이 발생할까?

1. 라이브러리 간 호환성 문제

ex) A라이브러리는 v1.0의 Library X를 요구하고 B라이브러리는 v2.0의 Library X를 요구하는 경우

2. 트랜스티브 의존성(Transitive Dependency)

• 프로젝트에서 직접 명시하지 않았지만 의존하는 라이브러리A가 다른 라이브러리B를 의존할 때 B가 자동으로 포함되는 의존성
• 프로젝트에서 직접 참조하지 않는 라이브러리(간접 의존성)가 서로 다른 버전을 요구할 때 발생하는 경우

ex) Spring Boot 프로젝트에서 spring-boot-starter-web을 추가하면 내부적으로 spring-web과 spring-core 같은 라이브러리가 포함됨. spring-boot-starter-web을 추가했더니 spring-web 5.3.0을 필요로 하고 spring-core 5.3.0도 함께 필요함. 그런데 추가적으로 다른 라이브러리를 사용했는데 spring-core 5.2.0을 필요로 한다면 어떤 버전을 쓸 것인지 충돌 발생

✒️ 의존성 충돌의 증상은?

1. 빌드 오류

"Dependency conflict" 또는 "Duplicate class" 같은 메시지

2. 런타임 오류

ClassNotFoundException, NoSuchMethodError 등

3. 예기치 않은 동작

잘못된 버전의 라이브러리가 로드되어 기능이 올바르게 동작하지 않음

✒️ Gradle의 의존성 충돌 해결 방식

1. Gradle의 충돌 해결 원칙

• 최신 버전 우선 정책 (Conflict Resolution)
  • Gradle은 의존성 충돌이 발생하면 기본적으로 최신 버전을 선택
• 의존성 트리 시각화
  • Gradle은 ./gradlew dependencies 명령을 통해 의존성 트리를 시각적으로 보여줌
  • 이를 통해 충돌 원인을 쉽게 파악 가능

    2. Gradle의 해결 방법

• 강제 버전 지정
  • 특정 라이브러리의 버전을 강제로 지정하여 충돌을 해결

    configurations.all {
    resolutionStrategy {
      force 'com.example:library:1.2.3'
    }
    }
    

- Exclusion
    - 트랜스티브 의존성을 제외하여 충돌 방지
```gradle
implementation('com.example:library') {
    exclude group: 'com.other', module: 'conflicting-library'
}

• Version Alignment
  • BOM(Bill of Materials) 또는 platform 기능을 사용하여 버전을 통일
  • 여러 라이브러리 버전을 한번에 설정

    implementation platform('org.springframework.boot:spring-boot-dependencies:2.5.0')

• Component Metadata Rules
  • Gradle은 특정 라이브러리의 버전 충돌을 해결하는 사용자 정의 규칙을 설정 가능

✒️ Maven의 의존성 충돌 해결 방식

1. Maven의 충돌 해결 원칙

• 선행 선언 우선 정책 (Nearest Definition Wins)
  • Gradle은 의존성 충돌이 발생하면 POM 파일에서 먼저 선언된 의존성을 우선으로 선택
  • 의존성이 여러 경로로 포함된 경우, 루트에서 가장 가까운 의존성을 선택
• 의존성 트리 확인
  • mvn dependency:tree 명령으로 트리를 확인하고 충돌 원인을 파악

    2. Maven의 해결 방법

• Dependency Management (BOM)
  • <dependencyManagement> 태그를 사용하여 버전을 명시적으로 고정

    <dependencyManagement>
    <dependencies>
      <dependency>
          <groupId>org.springframework.boot</groupId>
          <artifactId>spring-boot-dependencies</artifactId>
          <version>2.7.0</version>
          <type>pom</type>
          <scope>import</scope>
      </dependency>
    </dependencies>
    </dependencyManagement>
    

두 요소를 비교하여 정렬 순서를 결정하는 알고리즘

✒️ 버블 정렬 (Bubble Sort)

서로 인접한 두 개의 값을 비교하는 방식으로 큰 값이 계속 뒤로 이동 구현이 간단하지만 매우 비효율적, 작은 데이터에만 적합 추가적인 메모리 공간을 사용 O(1) 안정 정렬 (Stable Sort)

1. 배열의 인접한 두 요소를 비교하여 순서가 잘못된 경우 교환
2. 한 바퀴 순회하면 가장 큰 값이 맨 뒤로 이동
3. 이 과정을 배열 길이만큼 반복

시간 복잡도

• 최선 : O(n) (거의 정렬된 경우)
• 평균 : O(n^2)
• 최악 : O(n^2)

✒️ 선택 정렬 (Selection Sort)

배열에서 가장 작은(큰) 값을 찾아 맨 앞 요소와 교환하는 방식 실행 속도가 일정하지만 비효율적 교환 횟수가 적어서 메모리 사용이 적음 추가적인 메모리 공간을 사용 O(1) 불안정 정렬(Unstable Sort)

1. 배열에서 최소값(최대값)을 찾기
2. 해당 값을 맨 앞 요소와 교환
3. 두 번째 요소부터 다시 위의 과정을 반복

시간 복잡도

• 최선 : O(n^2)
• 평균 : O(n^2)
• 최악 : O(n^2)

✒️ 삽입 정렬 (Insertion Sort)

배열을 앞부분 부터 정렬된 상태로 유지하면서 새로운 값을 적절한 위치에 삽입 데이터가 거의 정렬된 경우 매우 효율적 추가적인 메모리 공간을 사용 O(1) 안정 정렬 (Stable Sort)

1. 두 번째 요소부터 시작하여 이전 요소들과 비교
2. 적절한 위치를 찾아 삽입
3. 이 과정을 마지막 요소까지 반복

시간 복잡도

• 최선 : O(n) (거의 정렬된 경우)
• 평균 : O(n^2)
• 최악 : O(n^2)

✒️ 병합 정렬 (Merge Sort)

분할 정복 (Divide and Conquer) 방식을 이용하여 배열을 반으로 나눈 후 각각 정렬하고 병합하는 방식 추가적인 메모리 공간을 사용 O(n) 안정 정렬 (Stable Sort)

1. 배열을 더 이상 나눌 수 없을 때까지 2등분
2. 분할된 배열을 정렬하면서 병합

시간 복잡도

• 최선 : O(nlog n)
• 평균 : O(nlog n)
• 최악 : O(nlog n)

✒️ 퀵 정렬 (Quick Sort)

분할 정복 기법을 사용하여 피벗(pivot)을 기준으로 작은 값과 큰 값으로 나누어 정렬하는 방식 평균적으로 매우 빠름 추가적인 메모리 공간을 사용 O(log n) 불안정 정렬(Unstable Sort)

1. 배열에서 한 개의 요소를 피벗으로 선택
2. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
3. 분할된 배열을 재귀적으로 정렬

시간 복잡도

• 최선 : O(nlog n)
• 평균 : O(nlog n)
• 최악 : O(n^2) (피벗이 한쪽으로 치우친 경우)

✒️ 힙 정렬 (Heap Sort)

힙(Heap) 자료구조를 이용하여 최대/최소 값을 꺼내며 정렬하는 방식 추가적인 메모리 공간을 사용 O(1) 불안정 정렬(Unstable Sort)

1. 주어진 배열을 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 변환
2. 힙에서 하나씩 요소를 꺼내 정렬

시간 복잡도

• 최선 : O(nlog n)
• 평균 : O(nlog n)
• 최악 : O(n^2) (피벗이 한쪽으로 치우친 경우)

2. 비교를 사용하지 않는 정렬 (Non-Comparison Sort)

데이터의 값을 직접 활용하여 정렬하는 알고리즘

✒️ 계수 정렬 (Counting Sort)

데이터의 빈도 수를 카운팅 하여 정렬하는 방식 매우 빠르지만 데이터 범위가 제한적일 때만 가능 추가적인 메모리 공간을 사용 O(k) 안정 정렬 (Stable Sort)

1. 데이터 범위의 크기만큼 카운트 배열을 생성
2. 각 데이터의 등장 횟수를 기록
3. 카운트 배열을 기반으로 정렬된 데이터를 생성

시간 복잡도

• 최선 : O(n+k) (k: 데이터 값의 범위)
• 평균 : O(n+k)
• 최악 : O(n+k)

✒️ 기수 정렬 (Radix Sort)

각 자리수를 기준으로 정렬을 수행하는 방식 매우 빠름, 숫자 정렬에 강함 추가적인 메모리 필요

1. 1의 자리부터 정렬 (기수 정렬의 보조 정렬로 계수 정렬을 사용)
2. 10의 자리 -> 100의 자리 순서로 정렬
3. 모든 자리수를 정렬하면 완료

시간 복잡도

• 최선 : O(nk) (k: 자리수 개수)
• 평균 : O(nk)
• 최악 : O(nk)

✒️ 버킷 정렬 (Bucket Sort)

데이터를 여러 개의 버킷에 나누어 담고 각 버킷을 정렬한 후 합치는 방식 데이터가 고르게 분포되어 있을 때 매우 효율적 추가적인 메모리 필요

1. 최대값과 최소값을 확인하여 범위를 결정
2. 적절한 개수의 버킷을 생성
3. 각 데이터를 해당하는 버킷에 분배
4. 각 버킷 내부를 정렬 (삽입정렬, 병합정렬 등을 사용)
5. 정렬된 버킷을 하나로 합침

시간 복잡도

• 최선 : O(n+k) (k: 버킷 개수)
• 평균 : O(n+k)
• 최악 : O(n+k)

• 가능한 모든 경우의 수를 탐색하여 정답을 찾는 방법
• 특별한 최적화 기법이나 자료구조 없이 모든 경우를 하나씩 시도해 보는 것

✒️ 동작 원리

1. 문제의 모든 가능한 조합이나 경우를 나열
2. 각 경우를 차례대로 확인하며 조건을 만족하는지 검사
3. 정답을 발견하면 반환하거나 모든 조건을 검사한 후 답을 도출

✒️ 장단점

장점

특별한 알고리즘을 배우지 않아도 바로 사용 가능 최적화된 알고리즘이 없더라도 정답을 보장

단점

탐색 공간이 커지면 시간복잡도가 증가해 일정 시간 내에 문제를 풀기 어려움

✒️ 사용 시기

문제의 입력 크기가 작을 때

✒️ 입력 크기의 기준은?

1. 순열

• 입력 크기 : n <= 10
• n개의 원소로 순열을 만드는 경우, 경우의 수는 n!로 증가
  • n=10, 10!=3,628,800 (가능)
  • n=11, 11!=39,916,800 (탐색 기간 급격하게 길어짐)

2. 조합

• 입력 크기 : n <= 20
• n개의 원소에서 k개를 고르는 조합의 경우의 수
  • n=20, k=10 => 184,756 (가능)

3. 부분 집합 구하기

• 입력 크기 : n <= 20
• 부분 집합의 개수는 2^n
  • n=20, 2^20=1,048,576 (조금 느려질 수 있음)

3중 루프 탐색

• 입력 크기 : n <= 100
• n개의 원소를 3중 루프로 탐색하는 경우 시간 복잡도는 O(n^3)
  • n=100, 100^3=1,000,000 (한계)

문자열 매칭

• 입력 크기 : n <= 1,000
• n개의 문자를 갖는 문자열에서 패턴 매칭 시 O(n*m)
  • n=10,000, m=50 => 500,000 (조금 느림)

배열 내 합 계산

• 입력 크기 : n <= 1,000
• n개의 원소에서 부분 합을 계산하는 경우, 시간 복잡도는 O(n^2)
  • n=1,000, 1,000^2 = 1,000,000 (조금 느림)