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

💻문제

🌏문제풀이

처음엔 2차원배열로 구현하여 값을 구하려 했지만, 1부터 W-1까지 단건의 값을 구하여 더하는 것이 더욱 효율적이라 아래와 같은 방법으로 풀었다.

맨 오른쪽과 왼쪽은 빗물이 쌓일 수 없는 구조기 때문에 1~W-1까지를 기준으로 잡았다.

i를 기준으로 for(int j=0; j<i; j++), for(int t=i+1; t<W; t++)를 순환하며 각각의 max값을 구하고, 이 둘 중 min값을 찾는다. 이는 앙 옆으로 가장 높은 값들 중 작은값을 기준으로 빗물이 쌓일 수 있기 때문이다.

최종적으로 찾은 빗물이 쌓이는 높이에 자기 자신의 높이값을 빼주면 단 건별 빗물이 쌓이는 높이를 구할 수 있다.

👩‍💻코드

package javaTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_14719_빗물 {

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int block[] = new int[M];
        int sum = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            block[i] = Integer.parseInt(st.nextToken());

        }

        //맨 오른쪽과 왼쪽은 벽으로 생각해야하기 때문에 반복문에서 제외
        for(int i=1; i<M-1; i++) {
            int left = 0;
            int right = 0;

            //기준점으로부터 왼쪽 기둥 중 가장 큰 값
            for(int j=0; j<i; j++) {
                left = Math.max(left, block[j]);
            }
            //기준점으로부터 오른쪽 기둥 중 가장 큰 값
            for(int t=i+1; t<M; t++) {
                right = Math.max(right, block[t]);
            }
            //왼쪽,오른쪽 가장 큰 값이 자기자신보다 작으면 빗물을 담지 못함으로 if처리로 거름
            if(left > block[i] && right > block[i]) {
                //왼쪽, 오른쪽 기둥 중 더 작은 기둥 높이 기준 - 자신의 높이
                sum += Math.min(left, right) - block[i];
            }
        }

        System.out.print(sum);


    }


}

HTTP는 HTML 문서와 같은 리소스들을 가져올 수 있도록 해주는 프로토콜이다. HTTP는 웹에서 이루어지는 모든 데이터 교환의 기초이며, 클라이언트-서버 기반 프로토콜이다. 클라이언트-서버 프로토콜이란 수신자(보통 웹 프라우저) 측에 의해 요청이 초기화 되는 프로토콜을 의미한다. 하나의 완전한 문서는 텍스트, 레이아웃 설명, 이미지, 비디오, 스크립트 등 불러온 하위 문서들로 재구성된다.

1. REST 아키텍쳐 모델에서 대표적으로 사용되는 프로토콜이다.
2. 웹상에서 클라이언트와 서버 간 정보를 주고받을 수 있는 애플리케이션 계층 프로토콜이다.
3. 클라이언트와 서버 사이에 요청/응답 기반 데이터 교환 방식을 갖는다.

MQTT(Message Queue for Telemetry Transport)

Facebook은 수많은 사용자가 동시에 메세지를 전송하더라도 짧은 시간 내에 서로 간의 메시지를 전송하기 위해 MQTT 프로토콜 방식을 도입했다. MQTT 방식의 도입을 통해 수 초 걸리던 폰 간(Phone-to-Phone) 전송 속도를 수 백밀리 초로 단축할 수 있고, 배터리 및 패킷 소모량이 적다는 장점이 있다.

그로스해킹

그로스해커는 제품의 성장을 이끌 수 있는 수많은 방안들을 고민하고, 실험하며, 이를 통해 제품의 성장을 반드시 이뤄내야 하며, 제품의 성장으로 성과를 평가받는 사람을 의미한다. 그로스해킹은 제품이나 서비스의 핵심 지표를 파악하고 분석하며 사용자의 흐름에 따라 개선하면서 시장을 확장시키는 마케팅 기법을 의미한다. 사용자의 피드백을 수집한 데이터를 바탕으로 제품을 끊임없이 개선하는 작업을 해야 하며, 대표적인 사례로 아마존이 있다.

디지털뉴딜

D.N.A(데이터, 네트워크, 인공지능) 생태계 강화, 교육 인프라 디지털 전환, 비대면 산업 육성, 사회간접자본(SOC) 디지털화 등 4개 분야에 걸쳐 12개 추진과제로 구성된 정책

Git(소프트웨어 버전 관리 도구)

1. Git의 작업 폴더는 전체 기록과 각 기록을 추적할 수 있는 정보를 포함하는 완전한 형태의 저장소이다.
2. Git의 commit 동작은 로컬 저장소에서 이루어지고 push라는 동작으로 원격 저장소에 반영된다.
3. Git은 로컬 저장소에서 대부분의 작업이 이루어져 매우 빠른 응답을 받을 수 있다.
4. Git은 분산형 버전 관리 시스템으로 때형 프로젝트에서 효과적이고 유용하다.

객체지향 기법

1. 다형성 메시지에 의해 객체가 연산을 수행하게 될 때 하나의 메시지에 대해 각 개체가 가지고 있는 고유한 방법으로 응답할 수 있는 능력
2. 캡슐화 서로 관련성이 많은 데이터와 이에 관련된 함수 등을 한 묶음으로 처리하는 기법
3. 추상화 공통 성질을 추출하여 클래스를 설정함
4. 상속성 상위 클래스 속성과 메소드를 하위 클래스에서 재정의 없이 물려받아 사용함

테스트케이스 작성 순서

1. 테스트 계획 검토 및 자료 확보
2. 위험 평가 및 우선순위 결정
3. 테스트 요구사항 정의
4. 테스트 구조 설계 및 테스트 방법 결정
5. 테스트 케이스 정의
6. 테스트 케이스 타당성 확인 및 유지보수

JSON(JavaScript Object Notation)

1. 속성-값 쌍으로 이루어진 데이터 오브젝트를 전달하기 위해 사용하는 개방형 표준 포맷이다.
2. AJAX(Asynchronous Javascript And XML)에서 많이 사용된다.
3. 비동기 브라우저/서버 통신을 위해, 넓게는 XML을 대체하는 주요 데이터 포맷이다.
4. JSON은 문자열을 전송 받은 후에 해당 문자열을 바로 파싱하므로 XML보다 빠른 처리속도를 보여준다.

XML

다른 특수한 목적을 갖는 마크업 언어를 만드는 데 사용하도록 권장하는 다목적 마크업 언어

OSI 7계층

1. FTP, SMTP, HTTP, Telnet 등 프로토콜이 속하는 계층은 application 계층이다.
2. 계층을 지날 때 마다 헤더(header)가 붙는데, 이것은 해당 계층의 기능과 관련된 제어 정보가 포함되어 있다.
3. 통신 중 연결이 끊어지지 않도록 유지시키는 역할을 수행하는 계층은 session 계층이다.
4. 각 계층은 서로 독립적으로 구성되어 있고, 각 계층은 하위 계층의 기능을 이용하여 상위 계층에 기능을 제공한다.

데이터링크 계층 데이터링크 계층은 시스템 간에 신뢰성 있는 정보를 전송하는 기능을 제공한다. 일반적으로 전송과정에서 데이터 오류가 발생할 수 있는데 데이터링크 계층은 이러한 오류를 검출하여 복구시킴으로써 신뢰성 있는 데이터 송수신을 보장해준다. 또한, MAC 주소 제어 등 여러 에러 제어 및 흐름 제어를 수행함으로써 데이터링크의 효율을 향상시키는 역할을 담당한다. 이 계층에서는 프레임 사이의 구분을 위해 앞뒤 flag를 사용하고, flag는 프레임과 프레임 사이를 구분하기 위해서 삽입하는 것이다.

인코딩

인코딩은 문자셋을 컴퓨터가 이해할 수 있는 바이트와 매핑하는 규칙을 말한다. 예를 들어 ASCII Code에서 ABC는 문자셋이고, A는 코드 65, B는 ZHEM 66 등 바이트 순서와 매핑한 것이 인코딩이다.

ERC-721, ERC-20 토큰

1. ERC-721은 증서라고 알려진 NFT의 표준안이다. NFT는 대체불가토큰의 약자이다.
2. ERC-20은 일반적으로 거래소에서 거래하고 있는 대부분의 토큰 발행 기준으로 대체 카등한 특징을 가진다.
3. ERC-20은 이더리움과 교환 가능하며 이더리움 지갑으로 전송이 가능하다.

NoSQL(Not Only SQL)

1. 비관계형 데이터 저장 기술을 의미하며, RDBMS의 한계를 극복하기 위한 형태로 수평적 확장성을 갖고 있다.
2. 문서, 그래프, 키 값, 인 메모리, 검색을 포함해 다양한 데이터 모델을 사용한다.
3. NoSQL은 분산 처리라는 특징으로 인해 클라우드 환경에 맞는 저장 기술이며 주로 빅데이터 분석 등에 사용된다.
4. NoSQL은 데이터 저장에 고정된 테이블 스키마가 필요하지 않고 조인 연산을 사용할 수 없다.

맵 리듀스(Map Reduce)

구글에서 대용량 데이터 처리를 분산 병렬 컴퓨팅으로 처리하기 위한 목적으로 제작하여 2004년 발표한 소프트웨어 프레임워크다. 페타바이트(PetaByte) 이상의 대용량 데이터를 시노리도가 낮은 컴퓨터로 구성된 클러스터 환경에서 병렬 처리를 지원하기 위해 개발되었다.

리브라

1. 페이스북에서 개발 중인 암포화폐로, 2020년 연말 출시를 목표로 하며 2020년 4월에 '리브라 2.0' 백서를 공개하였다.
2. 페이스북은 왓츠앱과 메신저 등 자사 서비스를 활용해 리브라를 글로벌 결제 플랫폼으로 활용하려고 한다.
3. 리브라는 퍼블릭 블록체인이 아닌 프라이빗 블록 체인을 기반으로 운영도딜 것이다.
4. 통화 바스켓을 기초로 한 글로벌 단일 모델에서 각 법정 통화와 연결된 다중 토큰 모델로 전환하였다.

ERD(Entity Relationship Diagram)

ERD에서 개체 집합은 직사각형, 개체 사이의 관계는 마름모, 속성은 타원, 링크는 직선 등으로 표현하며 데이터 구조와 구조들 간의 관계를 표현할 수 있다.

스피어피싱

불특정 다수가 아닌 특정기관이나 기업의 내부 직원을 표적 삼아 집중적으로 공격하는 행위를 일컫는 용어로, 신뢰있는 내용처럼 위장한 악성 이메일을 관련자들에게 전송하여 감염시킨다. 이후 원격 제어 및 데이터 탈취 등을 시도하는 대표적인 지능형 표적 공격으로 문서(HWP,PDF,DOC 등) 파일의 취약점을 이용한 공격 활용이 많다.

역공학(Reverse Engineering)

현재 프로그램으로부터 데이터, 아키텍쳐, 절차에 관한 분석 및 설계 정보를 추출하는 과정으로, 소프트웨어를 분석하여 기존 시스템의 문서화를 재작성하거나 자료사전, ERD 등의 설계 정보를 재생시키는 작업이다.

재공학(Re-Engineering)

기존 프로세스를 파기하지 않고 변경된 사용자의 요구사항이나 수정된 환경으로 기존 프로세스를 보완하여 재구축하는 것을 의미한다. 금융권의 차세대 프로젝트가 큰 규모의 재공학에 해당한다.

리팩토링(Refactoring)

외부동작을 바꾸지 않으면서 내부 구조를 개선하는 방법론을 말한다.

PaaS

사용자 정의의 응용 프로그램을 개발하고 사용할 수 있는 개발자를 위한 프레임워크를 제공한다.

장점 : 필요한 플랫폼만 소비 형태로 사용하기 때문에 비용 부담을 덜 수 있고, 개발 및 배포 프로세스를 빠르게 확보할 수 있다. 단점 : 특정 플랫폼 서비스에 종속될 수 있다.

IaaS

컴퓨팅, 네트워킹, 스토리지 및 기타 인프랄 사용하기 위한 서비스이며 사용자는 필요할 때마다 서비스를 통해 리소스를 구입할 수 있다.

SaaS

애플리케이션은 웹 브라우저를 통해 직접 실행되므로 클라이언트 측에서 다운로드나 설치가 필요하지 않다.

POP(Post Office Protocol)

응용 계층 인터넷 프로토콜 중 하나로, TCP/IP 연결을 통해 이메일을 가져오는데 사용된다. 여러 버전의 POP 프로토콜이 개발되었지만, 일반적으로 POP를 지칭하는 경우 보통 POP3를 가리킨다. G메일 같은 대부분의 웹 메일에서 지원한다.

레그테크

규제와 기술의 합성어로, 내부 통제와 법규 준수를 용이하게 하는 정보기술을 말한다. 이를 도입하면 준법감시 능력을 제고할 수 있고, 금융시장 전체적으로 규제 준수를 위한 사회적 비용 절감이 가능하다.

섭테크

금융감동과 기술의 합성어로, 최신 기술을 활용해 금융감독 업무를 효율적으로 수행하기 위한 기법을 말한다.

린스타트업

아이디어를 빠르게 최소기능제품으로 제조한 후 시장의 반을을 보고 다음 제품 개선에 반영하는 전략이다. 단기간 동안 제품을 제조하고 성과를 측정하여 제품 개선에 반영하는 것을 반복해 성공 확률을 높이는 경영 방법론의 일종이다. 린 스타트업은 만들기 -> 측정 -> 학습의 과정을 통해 꾸준한 혁신을 이루는 것을 주 내용으로 한다.

애자일(Agile)

고객의 요구에 민첩하게 대응하고 그때그때 주어지는 문제를 풀어나가는 방법론을 말한다.

파이썬

파이썬은 들여쓰기를 사용하여 블록을 구분하는 문법을 적용하였으며, 이는 코드의 종속성을 나타내기 위함이다.

레코그니션(Rekognition)

이미지/동영상의 시각적 분석 기능을 쉽게 추가할 수 있게 해주는 아마존으 애플리케이션이다. 이를 통해 수많은 이미지를 검색, 확인 및 구성할 수 있고 rekognition vido를 통해 저장된 도영상 또는 실시간 스트림 동영상에서 동작 기반 컨텍스트를 추출하고 분석할 수 있다.

랭크브레인

구글이 2015년에 발표한 랭크브레인은 검색 결과를 분류하기 위해 사용하는 기계학습(AI) 기반 알고리즘이다. 백링크, 콘텐츠의 신선도, 콘텐츠의 길이, 도메인 권한 등에 따라 결과의 중요성을 증가시키거나 감소시킨다. 한 번도 보지 못한 키워드를 기존에 알고 있던 키워드와 매칭함으로써 사용자가 쓴 새로운 키워드의 뜻을 알아낼 수 있다.

피죤(Pigeon)

구글이 2014년에 발표한 알고리즘으로, 적절하지 않은 검색엔진 결과 페이지에 페널티를 주는 방식을 채택하였다. 피죤 업데이트를 함으로써 검색자의 위치와 다른 지리적인 요인을 고려하여 더 적절하고 정확한 결과를 제공한다.

허밍버드(Humminbird)

구글의 허밍버드는 검색 문의를 잘 파악한 후 검색 의도에 적합한 결과를 제공할 수 있도록 업데이트된 알고리즘으로서, 검색자의 의도를 파악하기 때문에 사이트가 정확히 검색 단어를 갖고 있지 않아도 페이지가 검색엔진 결과 페이지에서 랭킹에 들 수 있게끔 하였다.

에어스(AiRS)

네이버가 2017년에 처음 선보인 인공지능 콘텐츠 추천 알고리즘이다. 이용자가 콘텐츠를 소비하는 패턴을 분석해 비슷한 관심사의 사람들이 많이 본 컨텐츠를 먼저 보여주는 협력 필터와 문서의 충실도 및 이용자 피트백을 반영한 품질 모델이 결합돼 콘텐츠를 추천한다.

로지스틱 회귀분석(Logistic Regression)

데이터를 두 개의 그룹으로 분류하는 문제에 자주 쓰인다. 기존 회귀분석과의 차이는, 회귀분석에서 우리가 원하는 것이 예측값(실수)이기 때문에 종속변수의 범위가 실수이지만, 로지스틱 회귀분석에서는 종속변수 값으로 0또는 1을 갖는다.

서포트 벡터 머신(SVM)

선형 분류와 비선형 분류 및 회귀 모두에 적용 가능하다.

JSP

HTML 내에 자바 코드를 삽입하여 웹 서버에서 동적으로 웹 페이지를 생성하여 웹 브라우저에게 돌려주는 언어이며, 웹 서버에서 동작한다. JSP는 동적인 웹 페이지를 효율적으로 활용하기 위한 방법을 제공한다.

1. JSP는 자바 기반이기 때문에 윈도우즈, 리눅스 등 운영체제에 상관없이 플랫폼에 동립적이다.
2. JSP 페이지에 대한 요청의 처리 등이 웹 서버에 동작한다. JSP는 동적인 웹 페이지를 효율적으로 생성하고 활용하기 위한 방법을 제공한다.

ReLU(Rectified Linear Unit)

딥러닝에서 가장 많이 사용되는 활성화 함수로, 기타 활성화 함수인 sigmoid와 tanh가 갖는 기울기 소실 문제를 해결하기 위함 힘수이다.

1. sigmoid, tanh 함수보다 학습이 따르고, 연산 비용이 적으며 구현이 매우 간단하다.
2. ReLU는 입력값 x가 0보다 크면 기울기가 1인 직선, 0보다 작으면 함수 값이 0이 된다. 이는 0보다 작은 값들이 뉴련에서 죽을 수 있는 단점을 야기한다.

SHA(Secure Hash Algorithm)

미국 국가안보국(NSA)이 1993년 처음으로 설계한 암호학적 해시 함수들의 모임이며, 미국 국가 표준으로 지정되었다. TSL, SSL, PGR, SSH, IPSec 등 많은 보안 프로토콜과 프로그램에서 사용되고 있다.

세그멘테이션

세그멘테이션 기법은 세그먼트가 메모리에 적재될 때 빈 공간을 찾아 할당하는 사용자 관점의 가상 메모리 관리 기법이다.

페이징 기법에서는 가상 메모리를 같은 크기의 단위로 분할하나, 세그멘테이션 기법에서는 가상 메모리를 서로 크기가 다른 논리적 단위인 세그먼트로 분할하고 메모리를 할당하며, 주소 변환을 하게 된다. 각각의 세그먼트들은 연속적인 공간에 저장되어 있다. 세그먼트들의 크기가 서로 다르기 때문에 메모리를 페이징 기법처럼 미리 분할해 둘 수 없으며, 페이징 기법과 마찬가지로 매핑을 위해 세그먼트 테이블을 필요로 한다.

세그멘테이션 기법은 하나의 세그먼트 단위로 통제가 가능한 장점이 있기에 내부 단편화가 발생하지 않는다. 그러나 서로 다른 크기의 세그먼트에 대해 필요시에 메모리에 올리고 필요 없을 경우 내리는 작업을 반복하다 보면 외부 단편화가 생기는 문제점이 있다.

허니팟

비정상적인 접근을 탐지하기 위해 의도적으로 설치해 둔 시스템으로, 네트워크 상에 특정 컴퓨터를 연결해 두고 해당 컴퓨터에 중요한 정보가 있는 것처럼 꾸며두면, 공격자가 해당 컴퓨터를 크래킹하기 위해 시도하는 것을 탐지할 수 있다.

FDS

FDS는 이상거래, 사기거래를 차단할 수 있는 플랫폼을 칭하는 이름이다. 고도화된 FDS는 보이스피싱을 비롯해 메모리해킹까지 대부분의 공격에 대응할 수 있다는 장점도 갖추고 있다.

SIEM

SIEM은 보안 정보 및 이벤트 관리를 의미하며 조직에 탐지. 분석 및 대응 방안을 제공하는 솔루션 개념을 의미한다. SIEM 소프트웨어는 보안 정보 관리(SIM)와 보안 이벤트 관리(SEM)를 결합하여 애플리케이션 및 네트워크 하드웨어에 의해 생성되는 보안 경보에 대한 실시간 분석을 제공한다.

비선점 스케줄링

비선점 스케줄링은 이미 할당된 자원을 다른 프로세스가 뺏을 수 없으며, 응답시간의 예측이 편하고 일괄처리 방식에 적합하다. 단점은 덜 중요한 덜 중요한 작업이 자원을 할당받으면, 중요한 작업이 있더라도 먼저 처리될 수 없다.

FCFS(First Come First Served) SJF(Shortest Job First) HRN(Highest Response-ratio Next)

선점 스케줄링

선점 스케줄링은 우선순위가 높은 프로세스를 빠르게 처리 가능하고, 어떤 프로세스가 자원을 사용하고 있다면 우선순위가 더 높은 프로세스가 올 경우 자원을 뺏길 수 있다. 빠른 응답 시간을 필요로 하는 시스템에서 주로 사용되고, 오버헤드가 크다.

Round Robin SRT(Shortest Remaining Time)

RSA

RSA는 공개키 암호화 방식으로, 공개키 암호화 중 가장 널리 쓰이고 있으며, 자리 수가 많은 양의 정수에 대한 소인수 분해가 어렵다는 것에 착안하여 이를 수학적으로 구현한 비대칭 암호화 알고리즘이라 할 수 있다. 알고리즘의 안정성을 위해 비밀키와 공개키가 비대칭적으로 이루어져 있으며 전자서명에도 적용할 수 있다.

교착상태

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

교착상태 회피 자원이 어떻게 요청될지에 대한 추가정보를 제공하도록 요구하는 것 [자원 할당 그래프 알고리즘, 은행원 알고리즘]

교착상태 무시 예방 혹은 회피기법을 프로그래밍에 넣으면 성능에 큰 영향을 미칠 수 있게 된다.

교착상태 예방 교착상태의 4가지 조건 중 한가지를 제거하여 예방하는 것 (1) 상호 배제 조건의 제거 (2) 점유와 대기 조건의 제거 (3) 비선점 조건의 제거 (4) 순환 대기 조건의 제거

포트

1. TCMP와 UDP는 포트번호로 부호 없는 16비트 정수를 사용함으로써 0 이상 65,535 이하의 값으로 이루어져 있다.
2. 한 프로세스가 포트 번호를 두 개 이상 사용하는 경우가 종종 있으며, 둘 이상의 프로세스가 한 포트 번호를 사용할 수도 있다.
3. 0 ~ 1023 포트번호는 용도가 정해져 있다.
4. 기관이나 사업자들을 위해 IANA에서 관리하는 포트는 registered port 이다.

리눅스 커널

프로세서나 시스템 메모리에 상주하면서 디바이스나 메모리 같은 하드웨어 자원을 관리하고, 프로세스의 스케줄을 관리하여 다중 프로세스를 구현하며, 시스템에 연결된 입출력을 처리하는 운영체제의 핵심 역할을 수행한다.

1. 시스템에 연결된 입출력을 처리한다.
2. 프로세스를 생성하거나 종료한다.
3. 하드웨어와 통신하며 애플리케이션을 통제한다.

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

💻문제

🌏문제풀이

👩‍💻코드

package javaTest;

import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class BOJ_1931 {


    static Node[] Nodes;

    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        Nodes = new Node[N];
        int count = 0;

        for(int i=0; i<N; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();

            Nodes[i] = new Node(s, e);
        }

        Arrays.sort(Nodes, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.end == o2.end) {
                    return o1.start - o2.start;
                }else {
                    return o1.end - o2.end;
                }
            }
        });

        int endTime = 0;
        for(int i=0; i<N; i++) {
            //System.out.println(Nodes[i].start + " " + Nodes[i].end);
            //System.out.println(endTime);
            if(endTime <= Nodes[i].start) {
                endTime = Nodes[i].end;
                count++;
            }
        }

        System.out.println(count);
    }

    private static class Node{
        int start;
        int end;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

}

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

💻문제

🌏문제풀이

👩‍💻코드

package javaTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1806 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int sum = 0;
        boolean flag = true;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int[] numbers = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        sum = numbers[0];
        while(start < N) {
            //합이 S보다 크거나 end가 끝까지 간 경우
            if(sum >= S || end == N-1) {
                if(sum >= S) {//이 중 합이 S보다 큰경우에만 MIN을 구함
                    min = Math.min(min, end-start+1);
                    flag = false;
                }//START를 한칸 옮겨주고 SUM에서는 빼준다
                sum -= numbers[start++];
                //System.out.println("2. "+start + " " + end + " " + sum + " " + min);
            }else {//그 외는 END를 한칸 옮겨준 다음 SUM에 합해준다
                sum += numbers[++end];
                //System.out.println("1. "+start + " " + end + " " + sum);
            }
        }

        if(flag)//sum >= S인 경우가 없을 때는 0을 출력
            min = 0;
        System.out.println(min);

        br.close();
    }

}

👩‍💻 구현

package Algorithm;

public class merge_sort {
    private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1};
    static int[] tmp = new int[input.length];

    public static void main(String[] args) {

        mergeSort(0, input.length-1);

        for(int i : input) {
            System.out.print(i + " ");
        }

    }

    public static void mergeSort(int start, int end) {
        if(start < end) {
            int mid = (start + end) / 2;
            //배열을 분할한다
            mergeSort(start, mid);
            mergeSort(mid+1, end);

            //두 분할의 첫번째 인덱스를 저장
            int p = start;
            int q = mid + 1;
            int idx = p;
            //오른쪽 배열을 끝까지 돌았거나, 왼쪽 배열을 다 돌기 전이고 왼쪽배열 값이 오른쪽배열 값보다 작을 때,
            //임시 배열에 왼쪽 배열 값을 저장
            while(p <= mid || q <= end) {
                if(q > end || (p <= mid && input[p] <= input[q])) {
                    tmp[idx++] = input[p++];
                }else {//반대의 경우 임시 배열에 오른쪽 배열 값을 저장
                    tmp[idx++] = input[q++];
                }
            }

            for(int i=start; i<=end; i++) {
                input[i] = tmp[i];
            }

        }

    }

}

https://ict-nroo.tistory.com/53?category=698685

각 루프마다

1) 최대 원소를 찾는다 2) 최대 원소와 맨 오른쪽 원소를 교환한다. 3) 맨 오른쪽 원소를 제외한다. 하나의 원소만 남을 때까지 위의 루프를 반복한다.

👩‍💻구현

package Algorithm;

public class selection_sort {
    private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1};

    public static void main(String[] args) {
        selectionSort(input, input.length);

        for(int i : input) {
            System.out.print(i + " ");
        }    

    }

    public static void selectionSort(int[] input, int inputLength) {
        int max;
        int tmp;

        for(int i=0; i<inputLength; i++) {
            max = i;
            for(int j=i+1; j<inputLength; j++) {
                if(input[j] > input[i]) {
                    max = j;
                }
            }

            tmp = input[i];
            input[i] = input[max];
            input[max] = tmp;
        }
    }

}

2. Bubble Sort(버블정렬)

👩‍💻구현

package Algorithm;

public class bubble_sort {
    private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1};

    public static void main(String[] args) {
        bubbleSort(input, input.length);

        for(int i : input) {
            System.out.print(i + " ");
        }
    }

    public static void bubbleSort(int[] input, int length) {
        int tmp;

        for(int i=length-1; i>0; i--) {
            for(int j=0; j<i; j++) {
                if(input[j] > input[j+1]) {
                    tmp = input[j];
                    input[j] = input[j+1];
                    input[j+1] = tmp;

                } 
            }
        }
    }

}

3. Insertion Sort(삽입정렬)

👩‍💻구현

package Algorithm;

public class insertion_sort {
    private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1};

    public static void main(String[] args) {
        insertionSort(input, input.length);

        for(int i : input) {
            System.out.print(i + " ");
        }

    }

    public static void insertionSort(int[] input, int length) {
        int tmp;

        for(int i=1; i<length; i++) {
            for(int j=i; j>0; j--) {
                if(input[j] < input[j-1]) {
                    tmp = input[j];
                    input[j] = input[j-1];
                    input[j-1] = tmp;
                }
            }
        }
    }

}

출처: https://ict-nroo.tistory.com/52?category=698685 [개발자의 기록습관]

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

💻문제

🌏문제풀이

👩‍💻코드

package javaTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2003 {

    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int start = 0;
        int end = 0;
        int sum = 0;
        int count = 0;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] numbers = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        while(start < N) {
            //합이 M보다 크거나, end point가 끝에 다다른 경우 start 위치를 한칸 옮겨준다
            if(sum >= M || end == N){
                sum -= numbers[start++];
            }else {//합이 M과 같거나, 작을때 end point를 한칸 옮겨준다
                sum += numbers[end++];
            }

            if(sum == M) {
                count++;
            }
        }

        System.out.println(count);

    }

}

https://programmers.co.kr/learn/courses/30/lessons/42579?language=java

💻문제

🌏문제풀이

1) 장르, 재생횟수, 인덱스 담을 Album 클래스 선언 2) getOrDefault() 활용하여 장르별 재생횟수 합 구함 3) Comparator 활용하여 재생횟수 내림차순 정렬 4) (3)의 key 순서대로, 동일한 장르의 곡을 temp_list에 저장 5) temp_list 재생횟수 내림차순, 인덱스 오름차순 정렬 후 1~2개 값 answer에 저장

👩‍💻코드

import java.util.*;

class Solution {
    class Album{
        String genre;
        Integer index;
        Integer play;

        public Album(String genre, Integer index, Integer play){
            this.genre = genre;
            this.index = index;
            this.play = play;
        }

        public String getGenre(){
            return this.genre;
        }

        public int getIndex(){
            return this.index;
        }

        public int getPlay(){
            return this.play;
        }
    }

    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Album> temp_list = new ArrayList<>();
        ArrayList<Integer> temp_answer = new ArrayList<>();

        int[] answer;
        int max = Integer.MIN_VALUE;
        String maxGenre = "";

        HashMap<String ,Integer> genre = new HashMap<String, Integer>();
        ArrayList<Album> albums = new ArrayList<>();

        //장르별 재생횟수
        for(int i=0; i<genres.length; i++){
            genre.put(genres[i], genre.getOrDefault(genres[i], 0) + plays[i]);
        }

        //재생횟수 내림차수 정렬
        List<Map.Entry<String, Integer>> bestGenre = new ArrayList<>(genre.entrySet());
        bestGenre.sort(new Comparator<Map.Entry<String, Integer>>(){
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2){
                return o2.getValue() - o1.getValue();   
            }
        });

        //많이 재생된 장르 순서대로 인덱스 구하기
        for(Map.Entry<String, Integer> k : bestGenre){
            //해당 장르의 재생횟수와 인덱스 저장
            for(int i=0; i<genres.length; i++){
                if(k.getKey().equals(genres[i])){
                    temp_list.add(new Album(genres[i], i, plays[i]));
                }
            }
            //재생횟수 내림차, 인덱스 오름차순 정렬
            temp_list.sort(new Comparator<Album>(){
               @Override
                public int compare(Album o1, Album o2){
                    if(o1.play == o2.play){
                        return o1.index - o2.index;
                    }else{
                        return o2.play - o1.play;
                    }
                }
            });

            //해당 장르 곡 1개일 때, 1개만 저장
            if(temp_list.size() == 1){
                temp_answer.add(temp_list.get(0).getIndex());
            }//해당 장르 곡 2개 이상일 때, 2개까지 저장
            else if(temp_list.size() > 1){
                temp_answer.add(temp_list.get(0).getIndex());
                temp_answer.add(temp_list.get(1).getIndex());
            }
            //배열 초기화
            temp_list.clear();
        }

        answer = new int[temp_answer.size()];
        for(int i=0; i<temp_answer.size(); i++){
            answer[i] = temp_answer.get(i);
        }

        return answer;
    }
}

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

💻문제

🌏문제풀이

👩‍💻코드

package javaTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2490 {

    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        for(int i=0; i<3; i++) {
            int count = 0;
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<4; j++) {
                if(st.nextToken().equals("0")) {
                    count = count + 1;
                }
            }

            switch(count) {
            case 0 : System.out.println("E");
                     break;
            case 1 : System.out.println("A");
                     break;
            case 2 : System.out.println("B");
                     break;
            case 3 : System.out.println("C");
                     break;
            case 4 : System.out.println("D");
                     break;

            }


        }
    }

}

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

💻문제

🌏문제풀이

👩‍💻코드

package javaTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_10798 {

    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        String[] board = new String[5];
        int maxSize = Integer.MIN_VALUE;

        for(int i=0; i<5; i++) {
            st = new StringTokenizer(br.readLine());
            board[i] = st.nextToken();
            maxSize = Math.max(maxSize, board[i].length());
        }

        for(int i=0; i<maxSize; i++) {
            for(int j=0; j<5; j++) {
                if(i < board[j].length()) {
                    System.out.print(board[j].charAt(i));
                }
            }
        }


    }

}

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

💻문제

🌏문제풀이

주석참고

👩‍💻코드

package javaTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//virus의 위치를 저장하기 위한 class
class virusPoint {
    int row;
    int col;

    public virusPoint(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class BOJ_14502 {
    static ArrayList<virusPoint> virusList;
    static int N, M, max;
    static int[][] map; //입력받는 맵
    static int[][] wall; //벽을 놓을 맵
    //상하좌우로 한칸씩 이동하기 위함
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    //완전탐색을 위해 맵은 카피하여 사용
    public static int[][] copy(int[][] arr){
        int[][] copy = new int[N][M];

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                copy[i][j] = arr[i][j];
            }
        }

        return copy;
    }

    //벽을 세우는 함수
    public static void makeWall(int depth) {
        //벽 3개를 다 세우는 경우 바이러스를 퍼트린다
        if(depth == 3){
            spreadVirus();
            return;
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(wall[i][j] == 0) { //빈칸인 경우
                    wall[i][j] = 1; //벽으로 막아주고
                    makeWall(depth+1); //진행시킴
                    wall[i][j] = 0; //완전탐색을 위해 원복
                } 
            }
        }
    }

    //상하좌우로 이동한 값이 배열의 범위를 벗어나지 않는지 체크
    public static boolean isValid(int row, int col) {
        if(row < 0 || row >= N || col < 0 || col >= M)
            return false;
        return true;
    }

    //바이러스를 퍼트리는 함수
    public static void spreadVirus() {
        //벽을 세운 오리지널 wall 배열에 영향을 주지 않기 위해 copy
        int[][] copyWall = copy(wall);

        //바이러스를 담는 과정
        Queue<virusPoint> vq = new LinkedList<virusPoint>();
        for(int i=0; i<virusList.size(); i++) {
            //virusList 내 virusPoint class 형태로 가져옴
            vq.offer(new virusPoint(virusList.get(i).row, virusList.get(i).col));
        }

        //전염 시작
        while(!vq.isEmpty()) {
            int row = vq.peek().row;
            int col = vq.poll().col;

            //상하좌우로 이동
            for(int k=0; k<4; k++) {
                int nextRow = row+dx[k]; //dy로 바꿔도 값엔 변화 없음
                int nextCol = col+dy[k];

                //이동한 값이 유효하고 0이면 바이러스를 퍼트림
                if(isValid(nextRow, nextCol) && copyWall[nextRow][nextCol] == 0) {
                    copyWall[nextRow][nextCol] = 2;
                    //새로운 바이러스가 생겼으므로 큐에 삽입
                    vq.offer(new virusPoint(nextRow, nextCol));
                }
            }
        }
        //안전지역 수 구함
        int sc = countSafe(copyWall);
        max = Math.max(max, sc);
    }

    public static int countSafe(int[][] copyWall) {
        int sc = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(copyWall[i][j] == 0)
                    sc = sc + 1;
            }
        }
        return sc;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        virusList = new ArrayList<virusPoint>();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        max = 0;

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                //map에 값을 넣으면서 바이러스가 존재하면 해당 위치를 저장
                if(map[i][j] == 2) {
                    virusList.add(new virusPoint(i,j));
                }
            }
        }

        //오리지널 맵 카피
        wall = copy(map);

        makeWall(0);

        System.out.println(max);
    }

}

https://programmers.co.kr/learn/courses/30/lessons/72411

💻문제

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호 주문한 단품메뉴 조합 1번 손님 A, B, C, F, G 2번 손님 A, C 3번 손님 C, D, E 4번 손님 A, C, D, E 5번 손님 B, C, F, G 6번 손님 A, C, D, E, H 가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류 메뉴 구성 설명 요리 2개 코스 A, C 1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다. 요리 3개 코스 C, D, E 3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다. 요리 4개 코스 B, C, F, G 1번, 5번 손님으로부터 총 2번 주문됐습니다. 요리 4개 코스 A, C, D, E 4번, 6번 손님으로부터 총 2번 주문됐습니다. [문제] 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항] orders 배열의 크기는 2 이상 20 이하입니다. orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다. 각 문자열은 알파벳 대문자로만 이루어져 있습니다. 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다. course 배열의 크기는 1 이상 10 이하입니다. course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다. course 배열에는 같은 값이 중복해서 들어있지 않습니다. 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요. 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다. 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다. orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다. [입출력 예] orders course result ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] [2,3,4] ["AC", "ACDE", "BCFG", "CDE"] ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"] [2,3,5] ["ACD", "AD", "ADE", "CD", "XYZ"] ["XYZ", "XWY", "WXA"] [2,3,4] ["WX", "XY"] 입출력 예에 대한 설명 입출력 예 #1 문제의 예시와 같습니다.

입출력 예 #2 AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다. 요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.

입출력 예 #3 WX가 두 번, XY가 두 번 주문됐습니다. 3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다. 또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.

🌏문제풀이

풀이순서 1) 조합을 이용해 만들수 있는 메뉴의 구성을 구한다. 2) 이때, 각 메뉴의 구성이 만들어진 개수를 HashMap 형태로 저장한다. 3) 코수 종류에 따라 만들어진 최대 개수를 저장한다. count[] 4) 메뉴의 구성이 저장된 HashMap에서 코스 종류가 같고 가장 많이 등장한 메뉴의 구성을 반환한다.

👩‍💻코드

/*
    풀이순서
    1) 조합을 이용해 만들수 있는 메뉴의 구성을 구한다.
    2) 이때, 각 메뉴의 구성이 만들어진 개수를 HashMap 형태로 저장한다.
    3) 코수 종류에 따라 만들어진 최대 개수를 저장한다. count[]
    4) 메뉴의 구성이 저장된 HashMap에서 코스 종류가 같고 가장 많이 등장한 메뉴의 구성을 반환한다.
*/

import java.util.*;

class Solution {
    boolean[] visited;
    int[] count;
    HashMap<String ,Integer> orderMap = new HashMap<>();

    public String[] solution(String[] orders, int[] course) {
        String[] answer;
        ArrayList<String> list = new ArrayList<>();
        count = new int[11]; //course 배열의 각 원소는 2 이상 10 이하인 자연수

        //각각의 order가 만들 수 있는 모든 course를 구하기 위해
        for(int i=0; i<orders.length; i++){
            int n = orders[i].length();
            char[] order = orders[i].toCharArray();
            visited = new boolean[n+1];
            for(int j=0; j<course.length; j++){
                int r = course[j]; //코스종류
                int originR = r;
                combination(order, n, r, 0, originR);
            }
        }

        for(int i=1; i<11; i++){
            if(count[i] >= 2){//출연빈도가 2개 이상이며
                for(String s : orderMap.keySet()){//가장 많이 등장한 코스구성
                    if(s.length()==i && orderMap.get(s) == count[i])
                        list.add(s);
                }
            }
        }

        answer = new String[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }

        Arrays.sort(answer);

        return answer;
    }

    public void combination(char[] order, int n, int r, int idx, int originR){
        if(r==0){
            char[] c_tmp = new char[originR];
            int t = 0;
            for(int i=0; i<visited.length; i++){
                if(visited[i]){//방문했다는 것은 해당 요리를 선택했다는 것
                    c_tmp[t] = order[i];
                    t++;
                }
            }
            //XY, YX를 같은 코스로 판단하기 위해 정렬
            Arrays.sort(c_tmp);
            String s_tmp = new String(c_tmp);
            int s_Len = s_tmp.length();

            orderMap.put(s_tmp, orderMap.getOrDefault(s_tmp, 0)+1);

            //s_Len : 코스 종류에서 더 많은 출연빈도를 가지고 있으면 바꿔줌
            if(count[s_Len] < orderMap.get(s_tmp))
                count[s_Len] = orderMap.get(s_tmp);

            return;
        }

        if(idx == n)
            return;

        //해당 요리를 선택했을 때,
        visited[idx] = true;
        combination(order, n, r-1, idx+1, originR);
        //해당 요리를 선택하지 않았을 때,
        visited[idx] = false;
        combination(order, n, r, idx+1, originR);

    }
}

https://programmers.co.kr/learn/courses/30/lessons/12915?language=java

💻문제

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

제한 조건 strings는 길이 1 이상, 50이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. strings의 원소는 길이 1 이상, 100이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 큽니다. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다. 입출력 예 strings n return ["sun", "bed", "car"] 1 ["car", "bed", "sun"] ["abce", "abcd", "cdx"] 2 ["abcd", "abce", "cdx"] 입출력 예 설명 입출력 예 1 "sun", "bed", "car"의 1번째 인덱스 값은 각각 "u", "e", "a" 입니다. 이를 기준으로 strings를 정렬하면 ["car", "bed", "sun"] 입니다.

입출력 예 2 "abce"와 "abcd", "cdx"의 2번째 인덱스 값은 "c", "c", "x"입니다. 따라서 정렬 후에는 "cdx"가 가장 뒤에 위치합니다. "abce"와 "abcd"는 사전순으로 정렬하면 "abcd"가 우선하므로, 답은 ["abcd", "abce", "cdx"] 입니다.

🌏문제풀이

https://st-lab.tistory.com/243

👩‍💻코드

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        Arrays.sort(strings, new Comparator<String>(){
           @Override
            public int compare(String o1, String o2){
                if(o1.charAt(n)!=o2.charAt(n))
                    return o1.charAt(n) - o2.charAt(n);
                else
                    return o1.compareTo(o2);
            }
        });

        return strings;
    }
}

https://st-lab.tistory.com/243

https://programmers.co.kr/learn/courses/30/lessons/42895?language=java

💻문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N number return 5 12 4 2 11 3

입출력 예 설명 예제 #1 문제에 나온 예와 같습니다.

예제 #2 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다

🌏문제풀이

DFS를 통해 모든 경우의 수를 구한 문제 이때 주의할 점은 +, -, *, / 의 경우로 나눠 DFS를 타고 들어갈 때, N, NN, NN 즉 5, 55, 555 를 연산하는 경우의 수를 생각해야 한다는 것이다.

이를 구현하기 위해

int tmpN = 0;
tmpN = tmpN * 10 + N;

를 활용하여 모든 경우의 수를 탐색한다.

👩‍💻코드

class Solution {
    int answer;
    public int solution(int N, int number) {
        //모든 최솟값이 8보다 커서 dfs가 return 되는 경우는 답이 -1
        answer = -1;

         DFS(N, number, 0, 0);

        return answer;
    }

    public void DFS(int N, int number, int sum, int count){
        if(count > 8) return;

        if(sum == number){
            if(count < answer || answer == -1) answer = count;
            return;
        }
        //새로운 DFS를 탈 때 tmpN을 초기화시켜줌으로써 N, NN, NNN 등을 탐색할 수 있다
        int tmpN = 0;
        for(int i=1; i<9; i++){
            tmpN = tmpN*10 + N;
            DFS(N, number, sum+tmpN, count+i);
            DFS(N, number, sum-tmpN, count+i);
            DFS(N, number, sum*tmpN, count+i);
            DFS(N, number, sum/tmpN, count+i);
        }

    }
}

https://programmers.co.kr/learn/courses/30/lessons/43105?language=java

💻문제

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

🌏문제풀이

위에서 부터 더한 값들을 DP 배열에 넣어주면서 내려온다.

경우의 수는

1) 현 위치가 가장 왼쪽 값인 경우 위 트리로부터 가져올 수 있는 값은 DP[i-1][j] 밖에 없으니 DP[i-1][j] + triangle[i][j] 2) 현 위치가 가장 오른쪽 값인 경우 위 트리로부터 가져올 수 있는 값은 DP[i-1][j-1] 밖에 없으니 DP[i-1][[j-1] + triangle[i][j] 3) 그 외의 경우 현 위치로 부터 위 트리의 왼쪽 값의 합과 오른쪽 값 중에 큰 값을 가져와야 함 따라서 Math.max(DP[i-1][j-1], DP[i-1][j]) + triangle[i][j]

👩‍💻코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int dp[][] = new int[triangle.length][triangle.length];

        dp[0][0] = triangle[0][0];

        for(int i=1; i<triangle.length; i++){
            for(int j=0; j<triangle[i].length; j++){
                if(j==0){//맨 왼쪽
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                }else if(j==triangle[i].length-1){//맨 오른쪽
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                }else{//그 외 경우
                    dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
                }
            }
        }

        int len = dp.length;
        for(int i=0; i<len; i++){
            answer = Math.max(answer, dp[len-1][i]);
        }

        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/49189

💻문제

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 n vertex return 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 입출력 예 설명 예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

🌏문제풀이

1) 인접행렬을 링크드리스트 그래프로 변환. 2) point

count[e] = count[tmp]+1

q 가장 앞의 값을 poll() 하면서 큐에 넣는 노드들은 같은 깊이를 가지며, poll()한 노드보다 +1 만큼 깊다.

👩‍💻코드

import java.util.*;

class CngEdge{
    int n;
    boolean[] visited;
    ArrayList<ArrayList<Integer>> graph;
    int[] count;
    int anw = 0;

    public CngEdge(int n){
        this.n = n;
        this.visited = new boolean[n+1];
        this.count = new int[n+1];
        this.graph = new ArrayList<ArrayList<Integer>>();

        for(int i=0; i<n+1; i++){
            graph.add(new ArrayList<Integer>());
        }
    }

    public void put(int x, int y){
        graph.get(x).add(y);
        graph.get(y).add(x);
    }

    public int get(){
        return anw;
    }

    public void print(){
        for(int i=0; i<n+1; i++){
            System.out.print(i + " : ");
            for(int j=0; j<graph.get(i).size(); j++){
                System.out.print(graph.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }

    public void dfs(int x){
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(x);
        visited[x] = true;

        while(!q.isEmpty()){
            int tmp = q.poll();
            for(int e : graph.get(tmp)){
                if(!visited[e]){
                    //[0, 0, 1, 1, 2, 2, 2]
                    //poll()기준으로 연결된 노드를 가져왔다는 것은 poll()한 값보다 깊이가 +1
                    count[e] = count[tmp]+1;
                    q.offer(e);
                    visited[e] = true;
                }
            }

        }
        //가장 깊은 거리를 가진 노드를 카운트
        int max = 0;
        for(int i=0; i<count.length; i++){
            if(max < count[i]){
                max = count[i];
                anw = 0;
            }
            if(max == count[i]){
                anw++;
            }
        }


    }
}

class Solution {
    ArrayList<Integer> list;

    public int solution(int n, int[][] edge) {
        int answer = 0;
        list = new ArrayList<>();

        CngEdge cngEdge = new CngEdge(n);
        for(int i=0; i<edge.length; i++){
            cngEdge.put(edge[i][0], edge[i][1]);
        }

        cngEdge.dfs(1);

        answer = cngEdge.get();


        return answer;
    }
}

중첩해싱 블로그

👀해시 정렬

해시정렬 블로그

https://programmers.co.kr/learn/courses/30/lessons/42577

💻문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. 입출력 예제 phone_book return ["119", "97674223", "1195524421"] false ["123","456","789"] true ["12","123","1235","567","88"] false 입출력 예 설명 입출력 예 #1 앞에서 설명한 예와 같습니다.

입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

🌏문제풀이

Arrays.startWith()

👩‍💻코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        Arrays.sort(phone_book);

        for(int i=0; i<phone_book.length-1; i++){
            if(phone_book[i+1].startsWith(phone_book[i])){
                answer = false;
                break;
            }
        }

        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42578?language=java

💻문제

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. clothes의 모든 원소는 문자열로 이루어져 있습니다. 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다. 스파이는 하루에 최소 한 개의 의상은 입습니다.

🌏문제풀이

👩‍💻코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        HashMap<String, Integer> spy = new HashMap<String, Integer>();
        int sum = 1;
        for(int i=0; i<clothes.length; i++){
            spy.put(clothes[i][1], spy.getOrDefault(clothes[i][1], 0) + 1);
        }

        for(String k : spy.keySet()){
            //하루에 최소 한 개의 의상을 입으므로 모자를 선택할 때,
            //안경은 하나도 선택 안할 수 있기 때문에 선택하지 않는 경우의수 +1
            sum *= spy.get(k)+1;
        }
        //단, 아무것도 선택안하면 안되기 때문에 -1
        answer = sum - 1;

        return answer;
    }
}