개발옹

문제 링크

문제 설명

완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.

각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ scores의 길이 ≤ 100,000
• scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
  • scores[0]은 완호의 점수입니다.
  • 0 ≤ a, b ≤ 100,000
• 완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.

입출력 예

문제 풀이

[고려사항]

scores의 최대 길이가 100,000(십만)이므로 시간복잡도를 고려해서 구현해야한다.

*O(n^2)이면 10,000,000,000(백억)으로 보통 코딩테스트 시간을 넘어섬

[알고리즘, 구현방법]

문제만 딱 봤을때는 쉽게 풀 수 있을 줄 알았는데 생각보다 정답인 구현 방법을 생각해내기가 어려워서 시간이 꽤 걸렸다.

혼자서 생각을 못해내서 다른 분들의 아이디어에서 힌트를 얻어서 구현했다.

X 1차 생각

✅ 2차 생각

모든 사원의 근무 태도 점수(A)를 내림차순으로 정렬하고, 같은 근무 태도 점수인 경우 동료 평가 점수(B)를 오름차순으로 정렬한다.

• 입출력 예시로 들면 [3,2] [3,2] [2,1] [2,2] [1,4] 로 정렬한다.

이 리스트에서 뒤에 나온 사원의 근무 태도 점수(A)는 항상 앞에 있는 사원의 근무 태도 점수보다 작거나 같다.

반면 동료 평가 점수(B)는 오름차순으로 정렬되어있기 때문에, 뒤에 나온 사원의 동료 평가 점수가 앞에 있는 사원의 동료 평가 점수보다 작은 경우, 해당 학생(= 뒤에 나온 사원)보다 두 점수가 높은 사원이 있음이 보장된다.

• 위에서 정렬한 예시로 보면, 인덱스를 0부터 시작할때, 1번 사원과 2번 사원을 비교해보면 된다.
• [3,2] [3,2] [2,1] [2,2] [1,4] 
  • 2번 사원(=뒤에 나온 사원)의 동료 평가 점수(B)는 1로, 1번 사원보다 작다.
  • 그 말은 2번 사원보다 두 점수가 높은 사원인 1번 사원이 있음이 보장된다는 것이다.

앞에 있는 사원과 뒤에 있는 사원을 비교할 때, 근무 태도 점수(A)가 같은 경우가 있으니, 동료 평가 점수(B)가 작다고 해서 둘 다 작다고는 말할 수 없지 않나? 라고 생각이 든다면, 아니다.

근무 태도 점수(A)는 내림차순, 동료 평가 점수(B)는 오름차순이므로 근무 태도 점수(A)가 같은 두 사원은 앞에 있는 사원이 항상 더 큰(정확히는 크거나 같은) 동료 평가 점수(B)를 가지기 때문에 그런 경우는 없다.

결국, 정렬한 리스트에서 뒤에 있는 사원의 동료 평가 점수(B)가 앞에 있는 사원의 동료 평가 점수보다 크거나 같을때만 인센티브를 받는 사원이 되는 것이다.

[풀이 과정]

1. 완호 점수와 합계 저장
2. scores 배열을 근무 태도 점수는 내림차순으로, 동료 평가 점수는 오름차순으로 정렬
3. 정렬한 scores 배열을 순회하면서
   • 완호가 인센티브 대상자인지 확인
   • 비교할 사원의 동료 평가 점수가 이전 사원의 점수보다 크거나 같은 경우
     • 완호의 합계보다 큰 경우에만 석차 1 증가

정답 코드

import java.util.Arrays;
class Solution {
    public int solution(int[][] scores) {
        // 완호 점수와 합계 저장
        int[] target = scores[0];
		int targetSum = target[0] + target[1];
		// 근무 태도 점수는 내림차순, 동료 평가 점수는 오름차순으로 정렬
		Arrays.sort(scores, (o1, o2) -> {
			return o1[0]!=o2[0] ? o2[0]-o1[0] : o1[1]-o2[1];
		});
		
		int answer = 1;
		int before = 0;
		for (int[] score : scores) {
             // 완호가 인센티브 대상자인지 확인
			if (target[0] < score[0] && target[1] < score[1]) return -1;
            // 현 사원의 동료 평가점수가 이전 사원의 점수보다 크거나 같은 경우만 인센티브 받는 대상
			if (before <= score[1]) {
                // 완호의 합계보다 큰 경우만 석차를 올린다
				if (targetSum < score[0] + score[1]) {
					answer++;
				}
				before = score[1];
			}
		}
       
        return answer;
    }
}

📌요약

main 메서드는 자바 프로그램의 진입점(entry point), 즉 시작점이다.

JVM은 자바 프로그램 실행시 main 메서드를 찾아서 시작하므로 main 메서드는 필수적인 메서드이다.

• public: 접근제어자로, JVM이 main 메서드를 접근할 수, 찾을 수 있다.
• static: 인스턴스 생성 없이 클래스가 로드되면 바로 실행되어야하고 프로그램 실행시 main 메서드는 메모리에 할당되어 있어야하기 때문에 가비지 컬렉터의 정리 대상이 아니여야 한다. 
• void: main 메서드가 종료되었다는 것은 프로그램이 종료되었다는 것을 의미하므로 반환할 리턴값도 없다.
• String[] args: 프로그램 실행시 main 메서드에 넘기는 파라미터이다.

main 메서드란?

먼저 이 main 메서드가 무엇인지 알아보자.

main 메서드는 Java 프로그램의 진입점(entry point)로, 프로그램이 실행될 때 가장 먼저 호출된다.

그리고 모든 자바 어플리케이션은 main 메서드를 필수로 포함해야한다.

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello, World!");
    }
}

💡 진입점(entry point)

진입점이란 프로그램이 시작되는 시작점으로, main 메서드가 이에 해당한다.

컴퓨터가 프로그램을 실행할 때 가장 먼저 main 메서드를 찾아서 그 안에 있는 코드를 실행한다.

즉, 프로그램을 시작할 때 컴퓨터가 어디서부터 실행해야할지를 알려주는 역할을 하는 것이다.

모든 자바 프로그램은 main 메서드를 포함해야하는 이유가 이에 있다. main 메서드가 없으면 프로그램이 어디서 시작해야할지를 몰라서 실행되지 않는다.

*관례적으로 프로그램의 시작점을 main으로 한다고 한다!

main 메서드가 자바 프로그램을 실행하려면 필수적으로 있어야하고, 가장 먼저 실행된다는 것을 알아보았으니 이제 하나씩 뜯어보자!

public

public은 접근 제어자(access modifier)중 하나로, 어디서든 해당 객체를 참조할 수 있는 접근 제어자이다.

main 메서드는 진입점(entry point)이기 때문에 JVM에서 이 main 메서드를 어느곳에서든 접근하기 위해 public 이여야한다.

JVM이 자바 프로그램을 시작하고 main 메서드를 실행하려는 시점은 아직 아무런 클래스도 로드되어있지 않은 상태이다.

가장 먼저 main 메서드가 어떤 클래스에 있는지를 찾고, 그 클래스에서 불러오는 과정이 필요하다.

그래서 이 main 메서드에 접근 제약이 생긴다면 JVM은 main 메서드를 찾지 못해서 프로그램을 실행시킬 수 없는 것이다.

이렇게 되면 자바 프로그램 실행이 안되므로, main 메서드에는 아무런 제약이 없도록 public을 써주어야 한다.

접근제어자로 public 이 아니라 private로 실행하면 아래와 같은 에러가 발생한다.  

오류: javafx.application.Application 클래스에서 기본 메소드가 Main3이(가) 아닙니다. 다음 형식으로 기본 메소드를 정의하십시오.
   public static void main(String[] args)

static

static 은 인스턴스 생성없이 메서드를 호출할 수 있게하는 키워드로, 정적 함수임을 의미한다.

static으로 선언한 속성과 메서드는 인스턴스와 관계없이 항상 일정한 값을 가지므로 굳이 인스턴스를 생성하지 않아도 사용할 수 있게끔 만들어진 것이다.

JVM이 main 메서드를 발견하면 main 메서드가 들어있는 클래스를 로드한다.

그 후 별도로 인스턴스를 생성하는 과정을 거치지 않고 클래스가 로드되면 바로 main 메서드를 사용할 수 있도록 해야하기 때문에 static 키워드를 붙여주어야 한다.

그리고 static으로 선언한 속성과 메서드는 프로그램이 실행되는 순간 메모리가 할당되고, 가비지 컬렉터의 메모리 정리대상이 아니다.

즉, static으로 선언한 속성과 메서드는 메모리에 항상 할당되어 있다는 것이다. 

main 메서드는 가비지 컬렉터에 의해 정리되어서는 안되는 기본 함수이므로 static을 붙여야한다.

void

void 는 메서드의 리턴 값이 없음을 의미한다. 자바는 메서드의 실행이 종료되면 리턴 타입을 명시해야하는 언어이기 때문에 main 메서드에도 명시되어있어야 한다.

main 메서드가 종료되었다는 것은 프로그램이 종료되었다는 것을 의미하므로 반환할 리턴값도 없다.

그렇기 때문에 void를 붙여준다.

String[] args

String[] args는 커맨드 라인의 argument들로, 커맨드 라인을 통해 main 메서드 내부에서 사용할 수 있는 String 타입의 데이터를 전달할 수 있다.

*String[]는 String 타입의 여러 값을 저장할 수 있는 저장구조이다.

JVM이 main 메서드의 변수명은 강제하지 않기에 변수명은 임의로 변경해도 잘 동작한다.

하지만 String[]  args 구문 자체를 빼면 안된다. 일반 메서드는 main 메서드 내부에서 호출하기 때문에 입력값을 main 메서드에서 정할 수 있지만, main 메서드는 프로그램 실행시 처음으로 수행되기 때문에 외부로부터 값을 받을 수 있어야하기 때문이다.

즉, main 메서드는 프로그램 내부에서 값을 호출할 수 없기 때문에 문자열 인자를 받을 수 있도록 해야한다는 것이다.

하지만 IntelliJ나 Eclipse 같은 IDE로 Java 프로그램을 구현하고 실행하는 요즘에는 main 메서드에 문자열을 전달할 일이 거의 없다. 위에 기재했듯이 커맨드라인의 인자값으로, Java가 DOS 환경에서 실행되던 때에 사용하던 것이다. 

명령 프롬프트(cmd)등의 터미널을 통해서 자바를 실행할 때 인자값이라고 생각하면 된다. 

예를들어 아래와 같은 자바 파일을 컴파일하고 실행시 인자값을 넣어서 확인해보겠다.

package project01;

import java.util.Arrays;

public class Solution01 {
	public static void main(String[] args) {
		System.out.println(Arrays.toString(args));
	}
}

윈도우의 경우 명령 프롬프트(cmd)에서 실행해보면 아래와 같이 인자값을 잘 받아서 출력해준다는 것을 알 수 있다.

해당 자바 파일이 있는 디렉토리에서 명령어를 입력해서 수행한다.

• java Solution01.java : java 파일 컴파일
• java project01.Solution01 test string HelloWorld : 컴파일한 자바 파일을 실행
  • projext01.Solution01: 패키지명.클래스명
  • test string HelloWorld 가 main 메서드의 인자값으로 들어가는 String[] args에 해당하는 부분이다.

*중간에 cd .. 를 하는 이유는 상위 폴더로 이동하기 위해서!

물론 IDE 에서도 설정을 하면 main 메서드에 String 배열 인자를 전달할 수 있다고 한다.

참고 포스팅

문제 링크

문제 설명

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10%까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10%를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

(상세 예시 설명은 링크 확인 요망)

각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 return 하도록 solution 함수를 완성해주세요. 판매원에게 배분된 이익금의 총합을 계산하여(정수형으로), 입력으로 주어진 enroll에 이름이 포함된 순서에 따라 나열하면 됩니다.

제한사항

• enroll의 길이는 1 이상 10,000 이하입니다.
  • enroll에 민호의 이름은 없습니다. 따라서 enroll의 길이는 민호를 제외한 조직 구성원의 총 수입니다.
• referral의 길이는 enroll의 길이와 같습니다.
  • referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
  • 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
  • enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
  • 즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.
• seller의 길이는 1 이상 100,000 이하입니다.
  • seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
  • seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
• amount의 길이는 seller의 길이와 같습니다.
  • amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
  • 판매량의 범위, 즉 amount 의 원소들의 범위는 1 이상 100 이하인 자연수입니다.
• 칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
• 모든 조직 구성원들의 이름은 10 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.

입출력 예

문제 풀이

[고려사항]

enroll, referral는 최대 10,000(1만)이고, seller는 100,000(10만) 때문에 시간 복잡도를 고려하여 구현해야한다.

[알고리즘, 구현방법]

판매원의 이름을 key값으로 해서 각 판매원의 정보를 저장한다.

판매원 정보로는 판매원을 조직에 참여시킨 다른 판매원의 이름과 판매원의 누적 이익금을 포함시킨다.

판매량 집계 데이터의 판매원 이름 정보인 seller를 기준으로 판매액을 분배해야하기 때문에, 각 판매원이 이익을 분배해야하는 다른 판매원 정보를 가지고 있어야한다.

판매원 정보 저장한 후 seller 정보를 기준으로 수익금을 배분한다.

예를 들어, young은 위로 3명의 판매원이 걸쳐매있기 때문에 총 4인이 이익금을 나눠가져야한다.

young이 1,200원의 이익금을 벌었다면, young은 10%를 제외한 1,080원 / young의 바로 위 판매원에게는 10%를 제외한 (120-12)108원 / 그 위 판매원에게는 10%를 제외한 (12-1)11원 / 그리고 가장 위인 center에는 1원을 분배해야한다.

즉 각 판매원이 가지는 이익금은 본인에게 할당된 금액의 10%를 제외한 금액이고, 10%만큼의 금액은 그 위 판매원에게 할당되어야한다.

X 1차 생각

아래 과정을 재귀 함수로 호출해서 수행하면 정답이 나오긴 하지만, 시간 복잡도가 O(mn)이 되어 시간 초과로 실패한다.

1. 해당 판매원에게 할당되는 이익금의 10%제외한 금액을 판매원 이익금에 누적합
2. 해당 판매원의 referral 판매원에게 10%를 제외한 금액을 할당
3. referral 판매원으로 1을 다시 수행
4. 판매원 정보에 referral이 없을때까지 수행 (=center)

public static int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        // 1. 판매원 정보 저장
        for (int i=0; i<enroll.length; i++) {
            sellerInfoMap.put(enroll[i], new SellerInfo(referral[i]));
        }
        // 2. seller 판매액 분배
        for (int i=0; i<seller.length; i++) {
            distributeProfits(seller[i], amount[i] * 100);
        }
        // 3. 결과
        int[] answer = new int[enroll.length];
        for (int i=0; i<enroll.length; i++) {
            answer[i] = sellerInfoMap.get(enroll[i]).getProfits();
        }
        return answer;
    }
    public static void distributeProfits(String seller, int profits) {
        // 해당 판매원에게 할당되는 이익금의 10% 제외한 금액을 판매원 이익금에 누적합
        int excludingTen = profits / 10;
        int netProfit = profits - excludingTen;

        SellerInfo s = sellerInfoMap.get(seller);
        s.addProfits(netProfit);

        if (s.getReferral().equals("-")) return; // 최상위 판매원(center)은 이익금 결과로 없어도 됨

        distributeProfits(s.getReferral(), excludingTen); // 해당 판매원의 referral 판매원에게 10%를 제외한 금액을 할당
    }

distributeProfits 함수를 seller 길이만큼 호출하고, 함수 내부에서는 최대 깊이가 총 판매원 수(=enroll 길이)이므로, 최악의 경우 seller 최대 길이 100,000(10만) * enroll 최대 길이 10,000(1만) = 1,000,000,000(10억)이므로 시간 초과가 뜬다.

즉, 시간 복잡도O(mn)으로 실패한다. (m = seller 길이, n = enroll 길이)

✅ 2차 생각

seller를 순회하면서 각 seller에 대한 이익금 분배를 BFS로 수행하면 시간 복잡도를 O(m+n)으로 줄일 수 있다.

각 판매원에 대해 BFS 순회를 1번만 하기때문에 m(seller 길이) + n(enroll 길이)로 수행할 수 있는 것이다.

그리고 탈출 조건으로 더이상 분배할 이익금이 없는 경우도 추가한다.

해당 조건을 추가함으로써 불필요한 반복문 수행을 없앤다.

[풀이 과정]

1. 판매원 정보 저장
   • 판매원 정보: 해당 판매원을 추천한 판매원 정보(referral), 해당 판매원의 이익금(profits)
2. seller 순회하면서 판매액 분배
   • 이익금을 얻은 판매원(seller)의 상위 판매원들을 모두 BFS로 순회하면서 이익금을 규칙에 맞게 할당
3. 결과 출력

정답 코드

static Map<String, SellerInfo> sellerInfoMap = new HashMap<>();
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
    // 1. 판매원 정보 저장
    for (int i=0; i<enroll.length; i++) {
        sellerInfoMap.put(enroll[i], new SellerInfo(referral[i]));
    }
    // 2. seller 판매액 분배
    for (int i=0; i<seller.length; i++) {
        distributeProfits(seller[i], amount[i] * 100);
    }
    // 3. 결과
    int[] answer = new int[enroll.length];
    for (int i=0; i<enroll.length; i++) {
        answer[i] = sellerInfoMap.get(enroll[i]).getProfits();
    }
    return answer;
}
public void distributeProfits(String seller, int profits) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(seller);
    int currentProfit = profits;

    while (!queue.isEmpty() && currentProfit > 0) { // 더이상 분배할 판매원이나 이익금이 없을때까지 반복
        String currentSeller = queue.poll();
        // 해당 판매원에게 할당되는 이익금의 10% 제외한 금액을 판매원 이익금에 누적합
        int excludingTen = currentProfit / 10;
        int netProfit = currentProfit - excludingTen;

        SellerInfo s = sellerInfoMap.get(currentSeller);
        s.addProfits(netProfit);

        currentProfit = excludingTen;
        if (!s.getReferral().equals("-")) { // 최상위가 아닌 경우에 Queue에 판매원 추가
            queue.offer(s.getReferral());
        }
    }
}
public class SellerInfo {
    private String referral;
    private int profits;
    public SellerInfo(String referral) {
        this.referral = referral;
        this.profits = 0;
    }
    public void addProfits(int profits) {
        this.profits += profits;
    }
    public String getReferral() {
        return referral;
    }
    public int getProfits() {
        return profits;
    }
}

1. 트라이(Trie)란?

원하는 요소를 찾기위해 자주 사용되는 이진 검색 트리 등에서는 타겟 요소를 찾는데에 O(logN)의 시간이 걸립니다.
하지만 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에,
원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸립니다.
따라서 이 작업을 여러번 수행한다면 시간이 오래 걸리게 됩니다. 
이러한 문자열 검색시의 단점을 해결하기 위해 나온 자료구조가 트라이(Trie)입니다.

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 구글이나 네이버 등에 검색어를 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 합니다.
• 래딕스 트리(Radix Tree)나 접두사 트리(Prefix Tree), 탐색 트리(Retrieval Tree)라고도 합니다
  • 트라이(Trie)는 Retrieval Tree에서 나온 단어

예를 들어 'Tistory'라는 단어를 검색하기 위해 제일 먼저 'T'를 찾고, 다음에 'i', 's', 't', ... 의 순대로 찾으면 됩니다.

이런 개념을 적용한 자료구조가 트라이(Trie)입니다.

2. 트라이(Trie)의 작동 원리

다음 그림은 문자열 집합 {"apple", "app", "dad", "dream", "age"}를 트라이로 구현한 것입니다.

*트라이(Trie)는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리입니다.

[공통 접두어]

"apple"과 "app"은 "app"라는 공통 접두어가 있으므로 같은 서브 트리에 표시됩니다.

즉, "a"라는 공통 접두어를 가진 "apple", "app", "age"는 Head의 자식 노드 'a'에,

"d"라는 공통 접두어를 가진 "dad", "dream"은 Head의 자식 노드 'd'에 표시됩니다.

[Leaf Node]

리프 노드는 각 단어의 마지막 문자를 의미하므로, 단어의 끝 문자라는 표시(endOfWord)를 해야합니다.

또한 리프 노드의 개수는 단어의 개수를 의미합니다.

[트라이(Trie) 생성 과정]

1. "apple"를 트라이에 삽입

• 'a': 첫번째 문자인 'a'는 초기에 트라이 자료구조 내에 아무것도 없으므로 Head의 자식노드에 'a'를 추가
• 'p': 'a' 노드에도 현재 자식이 하나도 없으므로 'a'의 자식노드에 'p'를 추가
• 'p', 'l', 'e'에 대해서도 자식노드로 추가
• 'l': "apple" 단어가 끝남을 알기 위해 'l' 노드에 마지막 노드(endOfWord)임을 표시

2. "app"를 트라이에 삽입

• 'a': 현재 Head의 자식 노드로 'a'가 이미 존재하기 때문에 'a' 노드를 추가하지 않고 기존에 있는 'a'노드로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동하면서, 'p'노드에 마지막 노드임을 표시

3. "dad", "dream",  "age"를 트라이에 삽입

• "dad"와 "dream"의 첫 문자인 'd'는 Head의 자식 노드로 없기 때문에 추가해서, 각 단어별로 문자를 순차적으로 추가
• "age"는 Head의 자식 노드로 'a'가 있기 때문에,
  • 'a'로 이동 => 'a'의 자식 노드에 'g'가 없으므로 'g'를 추가 => 'e'도 'g'의 자식 노드로 추가한 후 마지막 노드 표시

3. 트라이(Trie) 구현(Java)

그럼 트라이를 Java로 구현하려면 어떻게 해야할까?

기본적으로는 Map Interface를 사용해서 구현합니다.

Map의 Key값에는 단어를 이루는 각각의 문자들이 들어가고, Value에는 자식 노드 클래스를 저장합니다.

이제 순차적으로 자바로 구현을 해보겠습니다.

Node 클래스 생성

Node 클래스는 해당 노드의 자식 노드정보와 단어의 끝인지를 판단하는 변수로 구성합니다.

private class Node {
    HashMap<Character, Node> childNode = new HashMap<>(); // 자식 노드
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
}

트라이(Trie) 자료구조 클래스 생성

기본적으로 루트 노드를 초기화해 줍니다.

*루트 노드는 1) 항상 비어있고 2) 루트노드의 자식 노드는 각 단어의 첫 글자입니다.

public class Trie {
    private Node rootNode;
    Trie() {
        // Trie 생성시 루트 노드는 기본으로 생성
        rootNode = new Node(); // 루트 노드는 빈 노드
    }
}

기본 메서드

1) 노드 추가(insert)

입력 받은 단어를 문자 순대로 트리 계층 구조의 자식 노드로 생성해서 넣습니다.

• 문자가 자식 노드에 존재하면 새로 생성하지 않고 자식 노드로 이동
• 단어의 마지막 문자인 노드라면 endOfWord = true로 설정

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드를 확인
    //  1) 자식 노드에 있는 문자라면 자식 노드를 가져옴
    //  2) 자식 노드에 없는 문자라면 새롭게 생성
    for (int i=0; i<word.length(); i++) node = node.childNode.computeIfAbsent(word.charAt(i), key -> new Node());
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

2) 포함 여부 확인(contains)

특정 단어가 트라이에 존재하는지 확인합니다.

• 루트 노드부터 단어의 문자 순대로 일치하는 자식 노드가 계층을 이루고 있는지 확인
• 단어의 마지막 문자에 endOfWord가 true

두 조건을 만족하는 경우가 트라이에 존재하는 경우입니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        if (!node.childNode.containsKey(c)) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode.get(c); // 마지막 문자를 node에 저장
    }
    return node.endOfWord; // 마지막 문자 여부를 반환
}

3) 노드 삭제(delete)

트라이에 추가했던 단어를 삭제합니다.

• 부모 노드에 대한 정보는 없기 때문에 삭제할 단어의 마지막 문자까지 이동해서 문자를 삭제해와야 합니다. => 재귀
• 다음 문자에 존재하는 자식노드가 있고, 삭제를 시작하는 마지막 노드(리프 노드)에는 endOfWord가 true로 되어있어야 합니다. 
  • 즉, 삭제할 단어가 트라이에 포함되어있어야 합니다.
• 단어 삭제를 위해 마지막 문자 노드인 리프 노드의 endOfWord를 false로 변경합니다. 이후 순차적으로 거꾸로 올라가면서 노드를 삭제합니다. 단, 아래 두 조건이 아닌 경우에만 삭제합니다.
  • 해당 노드의 자식노드가 있는 경우
    • 자식노드가 있다는 뜻은 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.
  • endOfWord가 true인 경우
    • 단어의 끝인 문자인 경우 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
private void delete(Node node, String word, int idx) {
    // 단어의 마지막 인덱스인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    }
    char c = word.charAt(idx); // 현재 확인해야하는 문자
    if (!node.childNode.containsKey(c)) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    Node child = node.childNode.get(c); // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childNode.isEmpty() && !child.endOfWord) node.childNode.remove(c, child);
}

🧪 구현 테스트

public static void main(String[] args) {
        Trie trie = new Trie();
        // insert
        String[] arr = {"apple", "app", "dream", "dad", "age"};
        for (String word: arr) {
            trie.insert(word);
        }
        // delete
        trie.delete("app");
        trie.delete("dream");
        // contains
        System.out.println(trie.contains("apple")); // true
        System.out.println(trie.contains("app")); // 삭제했으므로 false
        System.out.println(trie.contains("age")); // true
        System.out.println(trie.contains("dream")); // 삭제했으므로 false
        System.out.println(trie.contains("dad")); // true
}

위에서 예시로 들었던 문자열 배열을 기준으로 트라이를 생성하고 삭제, 포함여부를 확인하면 아래와 같은 결과를 확인할 수 있습니다.

💡 전체 코드는 아래 링크에서 확인해주세요.

4. 트라이(Trie) 시간 복잡도

총 문자의 개수를 N, 가장 긴 문자열의 길이가 L이라고 할때

• 생성 시간 복잡도: O(N*L)
  • 모든 문자열 N개를 넣어야하고, N개에 대해 트라이에 넣는 건 가장 긴 문자열 길이인 L만큼 걸린다.
  • 삽입은 O(L)만 소요
• 탐색 시간 복잡도: O(L)
  • 트리를 가장 깊게 탐색하는 경우는 가장 긴 문자열 길이인 L까지 들어가는 것이므로 O(L)

5. 트라이(Trie) 장단점

• 문자열에 대한 검색을 빠르게 할 수 있습니다.
  
  • 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나 추가하면 되기 때문에 문자열의 추가와 탐색 모두 O(M)만에 가능합니다.

• 필요로 하는 메모리의 크기가 너무 크다는 단점이 있습니다.
  • 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있기에 저장공간의 크기가 크다는 단점이 있습니다.
  • 문자열이 모두 영소문자로 이루어져 있어도, 자식 노드를 가리키는 26개의 포인터를 저정해야하는데
  • 최악의 경우에는 집합에 포함되는 문자열의 길이의 총 합만큼의 노드가 필요하기 때문에 총 메모리는 O(포인터 크기*포인터 배열 개수*총 노드 개수)가 됩니다.
    • 만약 1,000자리의 문자열이 1,000만개가 있다면 이때, 100만개의 노드가 필요하고 포인터의 크기가 8Byte라 하면 약 200MB의 메모리가 필요합니다.

트라이(Trie) 단점 해결을 위한 방법

'메모리의 크기가 너무 큰' 단점을 해결하기 위해, 보통 map이나 vector를 이용해서 필요한 노드만 메모리를 할당하는 방식을 사용합니다. 그러나 이는 메모리 제한이 타이트한 경우에는 최적화가 까다롭습니다.

또한 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다고 합니다.

6. 트라이(Trie) 코딩테스트 문제

• [백준] - 전설
• [백준] - 전화번호 목록 : 🔗풀이 포스팅

참고한 링크

• [자료구조] 트라이 (Trie)
• [Algorithm] Trie를 Java로 구현해보자!
• [자료구조] 트라이

네트워크를 공부하면 필수로 알아야하는 개념들에 대해 공부한 내용을 정리합니다.

네트워크(Network)

네트워크(Network)란 노드(Node)와 링크(Link)가 서로 연결되어 있으며 리소스를 공유하는 집합을 의미합니다.

• 노드: 서버, 라우터, 스위치 등의 네트워크 장치
• 링크(=Edge): 유선 또는 무선과 같은 연결매체로, 와이파이나 LAN

트래픽(Traffic)

트래픽(Traffic)은 특정 시점에 링크 내에 흐르는 데이터의 양, 서버를 통해 최종 사용자에게 전달된 데이터의 양을 의미합니다.

• ex. 서버에 저장된 파일(문서, 이미지 등)을 클라이언트(사용자)가 다운로드시 발생되는 데이터의 누적량
• 단위: bps(bits per seconds)

트래픽 계산

트래픽 = 용량 * 사용자 수

Q. 4GB 영화를 10명이 다운로드 받을때의 트래픽은?

• 4GB * 10명 = 40GB

처리량(Throughput)

처리량(Throughput)은 링크 내에서 성공적으로 전달된 데이터의 양을 의미합니다.

보통 트래픽 처리량을 나타내며, 많은 트래픽을 처리한다 = 많은 처리량을 가진다는 의미와 같습니다.

• 단위: bps(bits per seconds) 초당 전송 또는 수신되는 비트수

처리량은 사용자들이 많이 접속할때마다 커지는 트래픽, 네트워크 장치간의 대역폭, 네트워크 중간에 발생하는 에러, 장치의 하드웨어 스펙에 영향을 받습니다.

💡 트래픽과 처리량은 헷갈릴 수 있기 때문에 이렇게 이해하면 됩니다.

• "트래픽이 많아졌다" = 흐르는 데이터가 많아졌다.
• "처리량이 많아졌다" = 처리되는 트래픽이 많아졌다.

대역폭(Bandwidth)

대역폭(Bandwidth)은 주어진 시간 동안 네트워크 연결을 통해 흐를 수 있는 최대 비트수이며, 최대로 처리할 수 있는 트래픽을 의미합니다.

• 대역폭이 높을수록 사용자에게 빠른 서비스를 제공
  • ex. 고속도로의 차선이 2차선일때보다 8차선일 때 더욱 원활한 교통이 이루어짐
• 대략적인 최대 동시 접속자 수를 유추하는 척도
• 단위: bps(bits per seconds) 초당 전송 또는 수신되는 비트수 (초당 bit단위의 데이터 처리량)

대역폭 계산

대역폭(bps) = (용량 * 사용자수 * 8bits) / 처리시간

• bps 계산식 = 데이터크기(bits 단위) / 소요시간(초 단위)
• * 8bits는 Byte에서 bit(대역폭의 단위는 bps이기 때문)로 변환하기 위한 값 

Q1. 20,000명이 홈페이지에 접속할때 접속시마다 4MB의 용량을 다운로드 받아야하고, 이 요청이 10분내에 완료되어야 할 때, 대역폭은?

• 트래픽 =  (20,000명 * 4MB * 1개) = 80,000MB
• 대역폭 = (20,000 * 4MB * 8 = 640,000) /  (10분 * 60초 ) =1066Mbps = 1.066Gbps = 약 1Gbps의 대역폭 필요

Q2. 100Mbps 대역폭의 서버로 한 사용자당 100kbps로 동영상 파일을 요청할때, 최대 동접자수는?

• 100Mbps / 100kbps = 약 1,000명

트래픽 vs 처리량 vs 대역폭

트래픽은 흐르려는, 이동하려는 데이터 양을 의미하며, 이 트래픽을 처리할 때를 기준으로 생각하면 처리량과 대역폭을 쉽게 구분할 수 있습니다.

• 대역폭 : 네트워크의 '도로 폭'과 같으며, 이 '도로'를 통해 한 번에 얼마나 많은 데이터(트래픽)가 이동할 수 있는지를 나타냅니다.
• 처리량 : 특정 시점에서 '도로'를 통과하는 차량의 수에 해당하며, 다양한 요인에 의해 영향을 받을 수 있습니다. (네트워크 혼잡, 하드웨어 제한 등과 같은 외부 요인)

참고 강의 및 사이트

• [NETWORK] 대역폭(Bandwidth)이란?
• CS 지식의 정석 - 인프런

백엔드 웹개발자로 일을 하다가 신입 공채시장에 뛰어들게 되면서 전공지식을 더 공부해야겠다는 생각을 한 후 공부를 시작했어요. 

직접 필기하면서 공부하는 것도 도움이 많이 되지만, 매번 찾아봤던걸 다시 검색하는게 시간이 더 들길래 정리했습니다.

나중에 확인할 용도이긴 하지만, 혹시 잘못된 부분이 있다면 댓글로 알려주시면 감사드리겠습니다 🙇🏻

*공부하면서 계속 추가할 예정입니다.

🧑‍🏫 강의

• CS 지식의 정석 - 인프런
• 개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제

문제 링크

문제 설명

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.

• 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.

• 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 같습니다.

• 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다. 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다. 8자 모양 그래프의 형태는 다음과 같습니다.

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모야 ㅇ그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.

그 후 각 정점에서 서로 다른 번호를 매겼습니다. 

이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.

그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ edges의 길이 ≤ 1,000,000
  • edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
  • 1 ≤ a, b ≤ 1,000,000
• 문제의 조건에 맞는 그래프가 주어집니다.
• 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

입출력 예

문제 풀이

[고려사항]

edges는 최대 1,000,000(백만)이기 때문에 시간 복잡도 n^2을 조심해야한다.

[알고리즘, 구현방법]

먼저 기준이 되는 중앙노드를 판별해야한다.

그래프들과 무관한 정점을 중앙 노드라하면, 중앙 노드는 out 간선이 무조건 2개 이상인 노드이다.

제한사항에 나와있듯 나올 수 있는 그래프 개수는 2개 이상이므로, 중앙 노드에서 연결해야하는 노드는 2개 이상이기 때문에 중앙 노드에서 뻗어나가는 간선만 있고, 그 간선의 개수는 2개 이상이어야 한다.

도넛, 막대, 8자 모양 그래프에서 나가는 간선만 있으면서 그 간선 수가 2개 이상인 것은 없다.

그래서 중앙 노드 판별을 위와 같이 할 수 있다.

X 1차 생각

1. edges를 순회하면서 각 노드별 들어오는 간선, 나가는 간선, 자식 노드, 해당 노드에 연결된 노드를 Node 객체에 저장하고 중앙 노드의 자식 노드를 중심으로 순회한다.
2. 중앙 노드에 연결된 자식 노드를 순회할때는 각 자식 노드에서도 자식 노드를 순회하면서 해당 노드의 간선을 계산한다.
3. 중앙 노드에 연결된 자식 노드의 순회가 끝날때까지 2번을 반복한다.
4. 중앙 노드에 연결된 자식 노드의 자식 노드 순회도 끝나면, 저장한 간선 수와 노드 수로 그래프 모양을 판별한다.

이렇게 하면 테스트 케이스 22, 26번에서 런타임 에러가 발생한다.

edges가 크게 주어질때 재귀 깊이가 초과해서 발생하는 것으로 보인다.

* 재귀 호출을 하면 호출된 메서드에서 사용할 변수가 메모리에 추가 할당되기에 너무 깊이 들어가면 메모리가 차서 StackOverFlowError 예외가 발생한다. 

✅ 2차 생각

런타임 에러 관련해서 찾아보다가, 들어오고 나가는 간선을 기준으로 그래프 모양을 판별하라는 힌트를 보고, 코드를 수정했다.

도넛 모양, 막대 모양, 8자 모양 그래프의 각각 고유한 특성을 확인했다.

*이렇게 하니까 속도와 메모리 차이가 2배 이상 차이났다..!

• 막대 모양 : 단방향이기 때문에 Root 노드는 들어오는 간선 수가 0개이면서 나가는 간선은 1개이고, Leaf 노드는 들어오는 간선 수가 1개이면서 나가는 간선은 0개인 경우
• 도넛 모양 : 모든 노드가 들어오는 간선 수가 1개이면서 나가는 간선도 1개인 경우
• 8자 모양 : 정점으로 들어오는 간선 수가 2개이면서 나가는 간선도 2개인 경우 (=8자 모양의 중앙 노드)

이때 모든 그래프에 있는 경우는, 들어오는 간선이 1개이면서 나가는 간선도 1개인 경우이다.

이때는 해당 노드의 방문 여부와 자식 노드를 확인해서 재탐색하면 그래프 모양 확인이 가능하다.

즉, 들어오고 나가는 간선 수가 모두 1개인 경우, 해당 노드의 자식노드를 탐색하거나 이미 방문한 노드인지 확인하여 판별한다.

• 도넛 모양의 경우, 들어오고 나가는 간선 수가 1개인데 이미 방문한 노드라면 판별이 가능하다. 
• 막대 모양의 경우, 중간에 있는 노드면 위의 경우가 되는데, 이때 막대 모양 그래프는 Leaf 노드까지 방문해서 Leaf 노드에 도달하면 들어오는 간선 수가 1개이면서 나가는 간선 수가 0개이므로 판별이 가능하다.
• 8자 모양의 경우, 중간에 있는 노드가 무조건 들어오는 간선 수가 2개, 나가는 간선 수가 2개이고, 8자 모양 그래프를 모두 탐색하려면 무조건 8자 모양 그래프의 중앙 노드를 거치게 되므로 판별이 가능하다.

* 8자 모양의 경우, 도넛 모양이 2개 합쳐진 모양이지만, 시작 노드에서 전체 탐색을 하고 다시 돌아와야 이미 방문한 노드를 재방문하므로 도넛 모양과 별개로 판별 가능

[풀이 과정]

1. edges를 순회하면서 노드 정보 저장
   • Node 객체 : 들어오는 간선 수(in), 나가는 간선 수(out), 자식노드 리스트(childNodeList)
   • 예시) [2,3]
     • 2번 노드에는 나가는 간선 수 +1 & 자식노드 리스트에 3추가
     • 3번 노드에는 들어오는 간선 수 +1
2. 저장한 노드 정보로 중앙노드 찾기
   • 들어오는 간선(in) == 0 && 나가는 간선(out) >= 2
3. 중앙 노드의 자식 노드를 순회
   • 그래프 하나씩 확인해야하므로, 깊이 탐색을 위해 Stack에 자식노드 번호 저장
4. Stack 이 비워질 때까지 아래 과정 반복
   • 해당 노드에서 그래프 모양 판별이 가능하다면 판별하여 각 그래프 수 +1
     • 8자 모양이나 막대 모양 그래프의 고유한 특징으로 판별이 가능하다면 각 그래프 수 +1
   • 아니라면, 노드 방문여부 확인
     • 방문한 노드이면서 들어오고 나가는 간선 수가 1개라면 (in == 1 && out == 1) 도넛 모양 그래프 수 +1
     • 아니라면, 해당 노드의 자식 노드를 Stack에 push해서 해당 노드 위와 같은 과정으로 탐색
5. 중앙 노드 번호, 각 그래프 수 반환

정답 코드

import java.util.*;
public class Solution {
    public class Node {
        int in = 0; // 들어오는 간선
        int out = 0; // 나가는 간선
        boolean visited = false;
        List<Integer> childNodeList = new ArrayList<>(); // 자식 노드 (=나가는 간선이 가리키는 노드)
        public Node(int child) {
            if (child != 0) this.addChildNode(child); // 자식 노드가 있을때
            else this.in++;
        }
        public void addChildNode(int child) {
            this.out++;
            this.childNodeList.add(child);
        }
    }
    public int[] solution(int[][] edges) {
        /**
         * 방문한 노드인데 자식 노드로 재방문하는 경우, 도넛 모양
         * 단방향이라 무조건 한번씩만 방문하는 막대 모양 그래프는, Leaf 노드가 in=1, out=0 | Root 노드는 in=0, out=1
         * in=2, out=2인 노드가 있으면 8자 모양
         */
        int donut = 0;
        int bar = 0;
        int eight = 0;
        Map<Integer, Node> nodeMap = new HashMap<>(); // key: Node num, value: Node 정보
        // Node Setting
        for (int[] edge: edges) {
            int node = edge[0];
            int childNode = edge[1];

            if (nodeMap.containsKey(node)) nodeMap.get(node).addChildNode(childNode);
            else nodeMap.put(node, new Node(childNode));

            if (nodeMap.containsKey(childNode)) nodeMap.get(childNode).in++;
            else nodeMap.put(childNode, new Node(0));
        }
        // 중앙 노드 찾기
        int middle = 0;
        Iterator<Integer> it = nodeMap.keySet().iterator();
        while (it.hasNext()) {
            int nodeNum = it.next();
            Node node = nodeMap.get(nodeNum);
            // 들어오는 간선(in), 나가는 간선(out) 계산
            if (node.in == 0 && node.out >= 2) {
                middle = nodeNum;
                break;
            }
        }
        Stack<Integer> searchStack = new Stack<>(); // 탐색할 노드 번호 (깊이 탐색을 해야하기 때문에 Stack)
        for (int child: nodeMap.get(middle).childNodeList) {
            searchStack.push(child);
            nodeMap.get(child).in--; // 중앙 노드에서 들어오는 선 제외
        }
        // Find Graph
        while (!searchStack.isEmpty()) {
            Node child = nodeMap.get(searchStack.pop());
            int in = child.in;
            int out = child.out;

            if (in == 2 && out == 2) {
                eight++;
            } else if ((in == 0 && out == 0) || (in == 1 && out == 0) || (in == 0 && out == 1)) {
                bar++;
            } else {
                if (child.visited && (in == 1 && out == 1)) donut++;
                else if (!child.childNodeList.isEmpty()) for (int num: child.childNodeList) searchStack.push(num);
            }
            child.visited = true;
        }
        return new int[]{middle, donut, bar, eight};
    }
}

문제 링크

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution을 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

문제 풀이

[고려사항]

입국심사를 기다리는 사람(n)의 최대값이 1,000,000,000(십억)이고, 시간복잡도 O(n)으로 풀어야한다.

[알고리즘, 구현방법]

times에 담긴 각 심사관의 심사 시간이 더 짧은 순으로 배정을 해서 n명을 입국심사한다.

어떤 시점에서 심사 시간이 더 긴 심사관이 비어있는 상태라해도 더 짧게 끝낼 수 있는 심사관이 심사해야 최솟값을 구할 수 있다.

X 1차 생각

times를 값이 작은 순서대로 정렬해서, 더 짧게 끝낼 수 있는 심사관이 우선 심사할 수 있게 한다.

맨 처음에는 별도의 조건 없이 times 배열 길이 = 심사관 수만큼 사람을 배정한다.

총 심사 소요시간 변수(answer)에는 입국심사하는 사람의 심사 시간을 누적한다.

그런데 이렇게 순차적으로 심사관을 배정하면 고려해야하는 조건이 많아진다.

ex) 입출력 예시에서 나왔듯 20분이 지난 시점에서 10분이 걸리는 심사관이 비어있지만, 1분 더 기다려서 7분이 걸리는 심사관이 심사해야 최소 시간이 나오는 예시

✅ 2차 생각

프로그래머스에 이분탐색으로 분류되어있는 것에서 힌트를 얻어서

심사 소요시간에 대한 이분탐색으로 계산해야겠다고 생각했다.

• 이분탐색은 오름차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법으로, 정렬된 배열에서 특정 값을 찾을 때 정중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있는 방법이다.

탐색 기준을 시간의 범위로 잡아서 이분탐색을 수행한다.

기준이 되는 mid값을 소요시간으로 두고, 그 시간(mid분)에 몇 명을 심사할 수 있는지 계산한다.

계산 값이 심사 받아야하는 인원(n)과 같다면 반환한다.

예를들어, mid = 30이고 심사시간이 각각 7분, 10분 걸리는 심사관이 있다면,

30/7 + 30/10 = 4+3 = 7명이 30분안에 심사를 받을 수 있다는 뜻이다.

여기서 28분, 29분을 같은 예시로 계산하면 모두 6명이 나오는데, 

이는 심사 받아야하는 인원(n)이 나오더라도 그보다 더 적은 시간내에 심사를 할 수도 있음을 의미한다.

따라서 반환하는 조건을 심사 받아야 하는 인원(n) == 계산한 값 으로 하면 안된다.

최소 심사 시간을 구해야하기 때문에, 이분탐색시 양 끝값인 left, right를 left > right로 조건을 두어야 

n명이 모두 심사를 받은 시간이라해도 더 적은 시간을 찾을 수 있다.

[풀이 과정]

1. 심사 소요시간이 짧은 순으로 배열 정렬
   
   • times에 담긴 각 심사관의 심사 시간이 더 짧은 순으로 배정하기 위함
2. 최대 소요시간 계산
   • 가장 긴 심사시간 * 심사 받아야하는 총 인원
3. 이분탐색 하면서 최소 시간 구하기
   • left = 0분 , right = 최대 소요시간 , mid = (left + right) / 2
   • n명이 모두 심사가능한 시간이라해도 그보다 더 최솟값이 있을 수 있으므로,
     • 반복문 탈출 조건을 심사 받아야 하는 인원(n) == 계산한 값으로 하지 않음
     • 반복문 탈출 조건은 left > right 로 설정 (while문의 수행 조건으로는 left <= right가 됨)
   • mid분에 계산한 심사 가능 인원이 n보다 작다면,
     • 해당 시간안에 모든 사람을 심사할 수 없다는 뜻이므로, mid보다 큰 값의 범위를 탐색
   • mid분에 계산한 심사 가능 인원이 n보다 크거나 같다면, 
     • mid보다 작은 값의 범위를 탐색
     • 현재 값보다 최솟값이 있을 수 있으므로 우선 answer에 저장 후 진행
4. left <= right 가 FALSE가 되면 반복문 탈출해서 answer 반환

[Java 문법]

int[] to List

1차 생각을 구현하기 위해 int 배열을 List로 변환하는 방법에 대해 찾아보다가 알게된 내용을 포스팅 했다.

[Java] Array를 List로 변환 : int[] to List<Integer>

1차 시도 실패

이분탐색에 필요한 right 값, 

즉 최대 소요시간 계산시 우항인 n, times[times.length-1]을 long 타입으로 변환하지 않아서 실패했다.

long right = n * times[times.length-1];

🔼 실패코드 원인 부분

int * int = int인데, int 값의 범위를 넘어서면서(=오버플로우 발생) long 변수에 할당하여 문제가 발생한 것이다.

n의 최대값은 1,000,000,000(십억)이고 심사관은 최대 100,000(10만)명이라서 

두 수의 최대값은 1,000,000,000 * 100,000 = 100,000,000,000,000(100조)라는 어마무시하게 큰 수가 나온다. 

int형은 할당되는 메모리의 크기가 4바이트로, 최대값은 2의 31승 - 1인 2,147,483,647이므로 당연히 오버플로우가 발생한다.

long형은 할당되는 메모리의 크기가 8바이트로, 최대값은 2의 63승 - 1인 9,223,372,036,854,775,807라서 범위가 넘지 않는다.

* 2의 n승보고 대략적인 0의 개수 확인하기

따라서 int형은 오버플로우 발생 가능성이 있으므로, 우항 변수를 long 타입으로 변환하여 계산하는 것으로 바꿨다.

정답 코드

public static long solution(int n, int[] times) {
    Arrays.sort(times); // 심사 소요시간이 짧은 순으로 정렬
    long answer = 0; // 최소 심사 시간(최종 결과)

    long left = 0;
    // 최대 소요시간 = 가장 긴 심사시간 * 심사 받아야하는 총 인원
    long right = (long)n * (long)times[times.length-1]; // int형 오버플로우 발생 가능성이 있으므로, 우항 변수를 long 타입으로 변환하여 계산
    // n명이 모두 심사가능한 시간이라해도, 그보다 더 최솟값이 있을 수 있으므로, while조건을 (n == complete)로 하지 않음
    while (left <= right) {
        long mid = (left + right) / 2;
        long complete = 0; // mid 분안에 심사를 할 수 있는 인원수
        // mid 분 안에 심사를 할 수 있는 인원수 계산
        for (int i=0; i < times.length; i++) {
            complete += mid / times[i]; // 각 심사 시간으로 나눠서 심사 가능 인원 계산
        }

        // 심사 가능 인원이 n보다 작다면, 해당 시간안에 모든 사람을 심사할 수 없다는 뜻이므로, mid보다 큰 값의 범위를 탐색
        if (complete < n) {
            left = mid + 1;
        } else { // 계산한 심사한 사람 수가 n보다 크거나 같다면
            right = mid - 1; // mid보다 작은 값의 범위를 탐색
            answer = mid; // 현재 값보다 최솟값이 있을 수 있으므로 우선 answer에 저장 후 진행
        }
    }
    return answer;
}

참고 포스팅

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++)

JAVA 기본 자료형 & 데이터 타입 - 한눈에 정리

✏️ 코딩테스트를 풀면서 int[] 를 List로 변환하다가 마주한 문제와 알게된 문법에 대한 포스팅

int[ ] to List<Integer>

int 배열을 List로 변환하는 방법, 즉 int 배열에 담긴 요소를 그대로 List<Integer> (=ArrayList<Integer>)타입으로 변환하는 방법을 아래와 같이 시도했었다.

❌ Fail : Arrays.asList()로 변환

Arrays.asList()에 int 배열(int[])을 매개변수로 그대로 담으면 List<int[]>형으로 변환된다.

// int 배열
int[] arr = {1,2,3,4};

// 리스트로 변환
List<int[]> list = Arrays.asList(arr);

// 결과
System.out.println(list.size());                    // 1
System.out.println(list.get(0));                    // [I@36baf30c
System.out.println(Arrays.toString(list.get(0)));   // [1, 2, 3, 4]

int 배열인 arr을 asList로 변환했을때 기대한 건 arr의 요소(1,2,3,4)를 가진 List<Integer> 타입이지만, List<int[]>로 반환된다.

내가 원하는 List<Integer> 타입이 아니다!

결론부터 말하자면,

Arrays.asList()는 primitive 타입을 Wrapper 클래스로 형변환해주지 않는다.

즉, int 타입을 Integer로 형변환해주지 않기때문에,
primitive 타입의 배열은 Arrays.asList()를 사용해서 List로 변환할 수 없다.

따라서 int 타입의 배열은 다른 방식으로 배열에서 List로 변환해야한다.

1) 반복문을 사용하거나 2) Stream을 사용해서 변환하는 방식이 있다.

✅ Success : 반복문 or Stream 사용해서 변환

1. 반복문

// int 배열
int[] arr = {1,2,3,4};

// 리스트로 변환
List<Integer> list = new ArrayList<>();
for (int el: arr) {
    list.add(el);
}

// 결과
System.out.println(list.size());    // 4
System.out.println(list);           // [1, 2, 3, 4]

위처럼 반복문을 통해 int 배열을 순회하면서 list에 값을 하나씩 추가해주면 된다.

결과를 확인해보면 List에 Integer 요소 4개가 그대로 들어가 있는것을 확인할 수 있다.

2. Stream 

Stream은 람다와 함께 사용되어 간결하게 표현 가능한 기능으로, Java 8부터 지원된다.

// int 배열
int[] arr = {1,2,3,4};

// 리스트로 변환
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());

// 결과
System.out.println(list.size());    // 4
System.out.println(list);           // [1, 2, 3, 4]

• Arrays.stream(arr) : int[] → IntStream
• boxed() : IntStream → Stream<Integer>
• collect(Collectors.toList()) : Stream<Integer> → ArrayList<Integer>
  • Stream의 데이터를 변형 등의 처리를 하고 원하는 자료형으로 변환
  • collect: 스트림의 최종연산으로, 매개변수로는 Collector를 필요로 함
  • Collectors.toList(): Collectors를 이용하여 스트림의 요소들을 List 객체로 변환
    *Collectors: 미리 작성된 다양한 Collector를 반환하는 static 메서드를 가지고 있다.

이렇게 int[]를 List<Integer>로 변환하는데 성공했는데,

다음에는 배열을 리스트로 변환하는 방법을 더 알아보고,

Arrays.asList()와 new ArrayList<>()로 생성된 List의 차이점도 포스팅 해야겠다.

참고 포스팅

자바 프로그래머가 자주 실수 하는 10가지 - 1

[JAVA] For과 Stream은 어떤 차이가 있는걸까?

문제 링크

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0,1,3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

문제 풀이

이 문제는 numbers에서 추출한 한자리 숫자의 조합을 먼저 찾고, 조합한 수가 소수인지 판별하면 된다.

추출한 한자리 숫자의 조합은 dfs로 완전탐색을 이용해서 찾고, 찾은 수를 기준으로 소수 판별을 하면 된다.

이때 소수란, 1과 자기 자신 만을 약수로 가지는 수를 뜻한다.

어떤 수가 소수인지를 확인하기 위해서는 2부터 그 숫자 횟수만큼 반복하며 나누어떨어지는 수가 있는지 확인하는 방법도 있지만,

해당 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 더 빠르게 구할 수 있다.

* 제곱근까지만 반복해도 되는 이유

* 이때, 대량의 소수를 한번에 판별해야 하는 경우, 에라토스테네스의 체를 이용한다.

[풀이 과정]

이 문제에서는 특정 한자리 숫자들로 조합된 숫자들의 소수 판별을 해야하므로 

1. 숫자들로 조합할 수 있는 모든 경우의 수를 찾고
2. 찾은 수가 소수가 맞는지 판단

하면 된다.

[알고리즘, 구현방법]

먼저 숫자의 조합은 위에서 말한대로 완전탐색 중 DFS를 이용해서 찾는다.

dfs(numbers, "", 0);

public static void dfs(String numbers, String s, int depth) {
    if (depth > numbers.length()) return; // numbers 끝까지 순회하면 return

    for (int i=0; i<numbers.length(); i++) {
        if (!checked[i]) {
            checked[i] = true;
            set.add(Integer.parseInt(s + numbers.charAt(i)));
            dfs(numbers, s + numbers.charAt(i), depth+1);
            checked[i] = false; // 다음 조합을 위해 false로
        }
    }
}

방문하지 않은 문자를 기존 문자열(s)에 추가하는 방식으로 숫자를 추가했다.

숫자가 중복되면 안되므로 저장할 자료구조는 Set으로 정했다.

numbers 문자열의 특정 문자의 조합이 끝나면, 다음 조합을 위해 checked를 false로 돌려준다.

이 과정을 numbers 문자열을 문자 개수만큼(=문자열 길이) 반복하면 모든 조합을 찾을 수 있다.

그리고 조합한 수의 소수 판별은 해당 수의 제곱근까지 반복하여 나머지 연산 결과가 0이 아닌지 확인한다.

public static boolean isPrime(int num) {
    if (num < 2) return false;
    for (int i=2; i <= (int)Math.sqrt(num); i++) { // num의 제곱근까지 확인
        if (num % i == 0) return false;
    }
    return true;
}

코드

import java.util.*;
public class Solution {
	Set<Integer> set;
    boolean[] checked = new boolean[7]; // 조합한 수인지 (numbers는 최대 7자)
    
	public int solution(String numbers) {
   		set = new HashSet<>();
        // 문자열 numbers의 수 조합 찾기
        dfs(numbers, "", 0);

        int answer = 0;
        // 소수 판별
        for (int val: set) {
            if (isPrime(val)) answer++;
        }

        return answer;
    }

	public void dfs(String numbers, String s, int depth) {
        if (depth > numbers.length()) return; // numbers 끝까지 순회하면 return

        for (int i=0; i<numbers.length(); i++) {
            if (!checked[i]) {
                checked[i] = true;
                set.add(Integer.parseInt(s + numbers.charAt(i)));
                dfs(numbers, s + numbers.charAt(i), depth+1);
                checked[i] = false; // 다음 조합을 위해 false로
            }
        }
    }

    public boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i=2; i <= (int)Math.sqrt(num); i++) { // num의 제곱근까지 확인
            if (num % i == 0) return false;
        }
        return true;
    }
}

문제 링크

문제 설명

고객의 약관 동의를 얻어서 수집된 1 ~ n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다.

예를 들어, A라는 약관의 유효기간이 12달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 

당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다.

모든 달은 28일까지 있다고 가정합니다.

오늘 날짜를 의미하는 문자열 today, 약관의 유효기간을 담은 1차원 문자열 배열 terms와 수집된 개인정보의 정보를 담은 1차원 문자열 배열 privates가 매개변수로 주어집니다. 이때 파기해야 할 개인정보의 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• today는 "YYYY.MM.DD" 형태로 오늘 날짜를 나타냅니다.
• 1 ≤ terms의 길이 ≤ 20
  • terms의 원소는 "약관 종류 유효기간" 형태의 약관 종류와 유효기간을 공백 하나로 구분한 문자열입니다.
  • 약관 종류는 A~Z중 알파벳 대문자 하나이며, terms 배열에서 약관 종류는 중복되지 않습니다.
  • 유효기간은 개인정보를 보관할 수 있는 달 수를 나타내는 정수이며, 1 이상 100 이하입니다.
• 1 ≤ privacies의 길이 ≤ 100
  • privacies[i]는 i+1번 개인정보의 수집 일자와 약관 종류를 나타냅니다.
  • privacies의 원소는 "날짜 약관 종류" 형태의 날짜와 약관 종류를 공백 하나로 구분한 문자열입니다.
  • 날짜는 "YYYY.MM.DD" 형태의 개인정보가 수집된 날짜를 나타내며, today 이전의 날짜만 주어집니다.
  • privacies의 약관 종류는 항상 terms에 나타난 약관 종류만 주어집니다.
• today와 privacies에 등장하는 날짜의 YYYY는 연도, MM은 월, DD는 일을 나타내며 점(.) 하나로 구분되어 있습니다.
  • 2000 ≤ YYYY ≤ 2022
  • 1 ≤ MM ≤ 12
  • MM이 한 자릿수인 경우 앞에 0이 붙습니다.
  • 1 ≤ DD ≤ 28
  • DD가 한 자릿수인 경우 앞에 0이 붙습니다.
• 파기해야 할 개인정보가 하나 이상 존재하는 입력만 주어집니다.

입출력 예

문제 풀이

[구현방식 생각]

약관 종류별 유효기간을 개인정보 수집 일자에서 계산해서 오늘 일자와 비교한다.

개인정보 수집일자 + 약관 유효기간 > 오늘 : 보관 가능한 개인정보

개인정보 수집일자 + 약관 유효기간 < 오늘 : 파기해야 할 개인정보

수집된 개인정보 중 파기해야 할 개인정보를 반환해야 하므로,

수집된 개인정보의 정보를 담은 1차원 문자열 배열 privacies를 순회하면서 각 정보의 보관 가능 여부를 판단하는 걸로 구현했다.

[고려사항]

privacies의 최대 길이는 100이므로 한 원소씩 확인해도 시간 초과하지 않을 것이다.

그리고 파기해야 할 개인정보는 무조건 하나 이상 존재하므로 result가 null인 경우는 없기 때문에 null 예외처리는 제외해도 된다.

또한 약관 종류로 주어진 약관만 privacies에 주어지므로 이에 대한 예외처리도 하지 않아도 된다.

그리고 파기될 약관 개수가 몇 개인지 모르기 때문에 정답 배열은 리스트로(ArrayList)로 초기화한다.

약관 종류는 String이기 때문에 유효기간 정보를 담을 자료구조는 Map으로 한다.

[풀이 과정]

1. 오늘 일자(today), 약관 종류 배열(terms) 구현 용도에 맞게 세팅
   • 오늘 일자는 온점(.)을 구분자로 연, 월, 일로 변수에 저장
   • 약관 종류를 Key, 유효기간을 Value로 해서 Map에 저장
2. privacies 순회하면서 약관 유효기간 계산
   • 날짜와 약관 종류를 공백을 구분자로 분리하여 저장
   • Map에서 해당하는 약관 종류의 유효기간 가져와서 달(month)에 더함
     • 계산한 달이 12월을 넘어가는 경우 연도에 1 더하고 달에 12 빼기
   • 계산한 유효 일자랑 현재 일자 비교
     • 파기되지 않는 경우(=보관 가능한 경우)를 체크
     • 위 조건에 해당하지 않는 경우, 정답 리스트에 추가
3. int[]을 반환해야하므로 List 순회해서 answer 배열에 담아서 반환

[구현시 고려한 사항]

문자열을 구분할때 split()을 사용할지, StringTokenizer를 사용할지 고민했는데,

자바 공식 문서를 확인해보니 StringTokenizer는 레거시 클래스로, 호환성을 위해 사용되고 있기때문에  spilt 함수를 사용할 것을 권장하고 있다.

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

그래서 날짜를 년,월,일로 구분할때나 약관 정보를 가져올때 split() 함수를 사용했다.

💡 spilt() 주의사항

split()은 정규표현식으로 문자열을 구분하기 때문에 온점(.)을 구분자로 구분하려고 한다면 온점 앞에 역슬래시(\)를 붙여줘야한다. 

이때 Java에서 역슬래시를 표현하기 위해서는 앞에 역슬래시(\)를 붙여줘야한다. (\\)

즉, split("\\.")으로 사용해야 온점을 구분자로 문자열을 분리할 수 있다.

* 정규표현식에서 온점(.)은 임의의 한 문자를 뜻하기 때문에 온점(.)만 구분자로 넣는 경우 (즉,  split(".")), 그냥 빈 배열이 반환된다.

코드

import java.util.*;
class Solution {
	public static int[] solution(String today, String[] terms, String[] privacies) {
        // 오늘 일자 Y,M,D로 분리
        String[] todayInfo = today.split("\\.");
        int todayY = Integer.parseInt(todayInfo[0]);
        int todayM = Integer.parseInt(todayInfo[1]);
        int todayD = Integer.parseInt(todayInfo[2]);

        // 약관 종류
        Map<String, Integer> termsMap = new HashMap<>();
        for (String el : terms) {
            String[] temp = el.split(" ");
            termsMap.put(temp[0], Integer.parseInt(temp[1]));
        }

        // privacies 순회하면서 약관 유효기간 계산
        List<Integer> list = new ArrayList<>();
        int collectionY, collectionM, collectionD;
        for (int i=0; i<privacies.length; i++) {
            String[] privacyInfo = privacies[i].split(" ");
            String[] collectionDate = privacyInfo[0].split("\\.");
            collectionY = Integer.parseInt(collectionDate[0]);
            collectionM = Integer.parseInt(collectionDate[1]);
            collectionD = Integer.parseInt(collectionDate[2]);

            String typeOfTerms = privacyInfo[1];

            collectionM += termsMap.get(typeOfTerms);
            while (collectionM > 12) { // 계산한 달이 12월을 넘어가는 경우 연도에 1추가
                collectionM -= 12;
                collectionY += 1;
            }

            // 계산한 유효 일자랑 현재 일자 비교 (파기되지 않는 경우(=보관 가능한 경우)를 체크)
            if (collectionY > todayY) {
                continue;
            } else if (collectionY == todayY) {
                if (collectionM > todayM) {
                    continue;
                } else if (collectionM == todayM) {
                    if (collectionD > todayD) continue;
                }
            }
           list.add(i+1);
        }

        int[] answer = new int[list.size()];
        int idx = 0;
        for (int index : list) {
            answer[idx++] = index;
        }
        return answer;
    }
}

문제 링크

문제 설명

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.

• 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.
  • 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.
• 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.
• 누적 주차 시간이 기본 시간이하라면, 기본 요금을 청구합니다. 
• 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구합니다.
  • 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림합니다. 
  • ⌈a⌉ : a보다 작지 않은 최소의 정수를 의미합니다. 즉, 올림을 의미합니다.

주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한사항

• fees의 길이 = 4 
  • fees[0] = 기본 시간(분) | 1 ≤ fees[0] ≤ 1,439
  • fees[1] = 기본 요금(원) | 0 ≤ fees[1] ≤ 100,000
  • fees[2] = 단위 시간(분) | 1 ≤ fees[2] ≤ 1,439
  • fees[3] = 단위 요금(원) | 1 ≤ fees[3] ≤ 10,000
• 1 ≤ records의 길이 ≤ 1,000
  • records의 각 원소는 "시각 차량번호 내역" 형식의 문자열입니다.
  • 시각, 차량번호, 내역은 하나의 공백으로 구분되어 있습니다.
  • 시각은 차량이 입차되거나 출차된 시각을 나타내며, HH:MM 형식의 길이 5인 문자열입니다.
    • HH:MM은 00:00부터 23:59까지 주어집니다. 
    • 잘못된 시각("25:22", "09:65" 등)은 입력으로 주어지지 않습니다.
  • 차량번호는 자동차를 구분하기 위한, `0'~'9'로 구성된 길이 4인 문자열입니다. 
  • 내역은 길이 2 또는 3인 문자열로, IN 또는 OUT입니다. IN은 입차를, OUT은 출차를 의미합니다. 
  • records의 원소들은 시각을 기준으로 오름차순으로 정렬되어 주어집니다. 
  • records는 하루 동안의 입/출차된 기록만 담고 있으며, 입차된 차량이 다음날 출차되는 경우는 입력으로 주어지지 않습니다.
  • 같은 시각에, 같은 차량번호의 내역이 2번 이상 나타내지 않습니다. 
  • 마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않습니다. 
  • 아래의 예를 포함하여, 잘못된 입력은 주어지지 않습니다.
    • 주차장에 없는 차량이 출차되는 경우 
    • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우

입출력 예

문제 풀이

시각을 기준으로 오름차순 정렬되어있는 records를 차량번호을 기준으로 오름차순 정렬해서 사용 요금을 반환해야한다.

그래서 먼저 records를 차량번호를 Key값, 그 외 정보를 Value로 담아서 저장해서 계산해야겠다고 생각하여 구현했다.

[정의한 클래스 및 함수 설명]

[ParkingInfo 클래스]

• 차량번호별 주차 정보를 관리할 클래스
• 멤버 변수: 차량번호(carNum), 입차시간(inTime), 총 누적시간(totalTime)
  • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우는 입력에 없기 때문에, 입차시간과 출차시간을 쌍으로 묶어 저장할 필요는 없다고 판단하였다.
  • 입/출차 기록에서 출차인 경우, 총 누적시간(totalTime)을 계산하여 갱신하는 방식으로 구현했다.
• setTotalTime(doble totalTime)
  • 해당 차량의 총 누적시간을 갱신 
    • this.totalTime += totalTime
  • '주차장에 없는 차량이 출차되는 경우'나 '주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우'는 없기 때문에 총 누적시간 계산/갱신시 저장되어있던 입차시간(inTime)은 초기화한다.
    • this.inTime = "";
• implements Comparable<ParkingInfo> : @Override compareTo(ParkingInfo o)
  • 차량번호를 기준으로 정렬하기 위해 Comparable 인터페이스를 implements한다.
• @Override equals(), hashCode()
  • 차량번호를 기준으로 객체 비교
  • 객체의 멤버 변수인 차량번호(carNum)가 같다면, 같은 객체로 판단해야하기때문에 equals()와 hashCode()를 오버라이딩했다.

[calculateTime(String in, String out)]

public static double calculateTime(String in, String out) {
    double inH = Integer.parseInt(in.substring(0,2));
    double inM = Integer.parseInt(in.substring(2));
    double outH = Integer.parseInt(out.substring(0,2));
    double outM = Integer.parseInt(out.substring(2));

    return (outH * 60 + outM) - (inH * 60 + inM);
}

• 주차장 사용 시간 계산 메소드
• 이후 주차 요금 계산시 단위 시간 당 총 누적시간을 계산해야되어서 올림 연산이 필요하기 때문에 double로 선언
• 입/출차 시간의 시, 분을 나눠서, 시간에 *60해서 분으로 치환하여 계산한다.
  • 사용시간 = (출차 시 * 60 + 출차 분) - (입차 시 * 60 + 입차 분)

[풀이 과정]

1. records 순회하면서 Map, ParkingInfo 로 세팅
   • Map<String, ParkingInfo>
   • 입/출차 내역은 "시각 차량번호 내역" 형식의 문자열
     • 시각: "HH:MM"형식이므로 ":"를 공백으로 치환
       
       • 이후 누적시간 계산시 형변환하여 계산하기 위함
       • 올림 함수인 Math.ceil 을 정수형으로 계산시, 정수로 계산되기 때문에 원하는 값을 얻지 못할 수 있다.
         • 정수10/정수4를 올림함수를 이용하면 기대하던 3.0이 아니라 2.0이 반환된다.
         • 따라서 올림 값을 제대로 받으려면 실수형을 계산해야한다.
   • Map의 Key값인 차량번호가 이미 있는 경우
     • 내역이 입차(IN)인 경우, 저장된 ParkingInfo 객체에 inTime을 갱신
     • 내역이 출차(OUT)인 경우, 저장된 ParkingInfo 객체의 inTime을 가져와서 출차시간으로 총 누적시간 계산하고 갱신
       • calculateTime(String in, String out)
       • setTotalTime(double totalTime)
   • MaP의 Key값인 차량번호가 없는 경우(=입/출차기록이 없는 경우)
     • Key로 cardNum과 Value에 ParkingInfo를 세팅해서 Map에 추가한다.
     • OUT이 먼저 들어오는 경우는 제한사항에서 제외되었기에 고려하지 않아도 된다.
2. records 확인 및 List에 값 할당 / 정렬
   • Map에 저장된 차량 번호를 순회하면서
     • 출차 시간이 입력되지 않은 경우 totalTime 계산해서 갱신
       • 이때, 출차 시간은 23시 59분
     • 정렬을 위해 ParkingInfo를 리스트에 저장
       • infoList.sort(ParkingInfo::compareTo);
       • 정렬은 ParkingInfo에 오버라이딩 한 비교(compareTo)를 기준으로 한다.
3. 주차 요금 계산
   • fees 요소를 기본 시간, 기본 요금, 단위 시간, 단위 요금을 할당
   • 정렬을 한 list를 순회하면서 계산한 주차 요금을 int[] answer에 저장
     • 총 누적시간이 기본 시간이상이라면 요금 계산
       • 기본 요금 + 올림((총 누적시간 - 기본시간) / 단위 시간) * 단위 요금
     • 총 누적시간이 기본 시간을 넘지 않는다면 기본 요금을 저장
   • list에 이미 차량번호 순으로 정렬해두었기 때문에 answer 배열에 차량번호 순으로 주차 요금을 저장할 수 있다.

[구현시 고려(고민)한 사항]

records를 ParkingInfo로 저장할 때, 자바 클래스 중 List, Map 중 Map 으로 선택했다. 

입차/출차 내역이 있는지 확인해야 했기에 해당 Key값이 있는지 확인할 수 있는 구조가 필요했다.

•  Key 값을 차량번호로 두고 containsKey로 판단했다.

코드

import java.util.*;
class Solution {
	public static int[] solution(int[] fees, String[] records) {
        /**
         * 1. records 세팅
         *      - 이미 저장되어있는 차량번호 체크를 위해 map으로 선언
         */
        Map<String, ParkingInfo> map = new HashMap<>();
        for (String record : records) {
            StringTokenizer st = new StringTokenizer(record, " ");
            String time = st.nextToken().replace(":", "");
            String carNum = st.nextToken();
            String type =  st.nextToken();

            double inH, inM, outH, outM;
            if (map.containsKey(carNum)) {
                ParkingInfo carParkingInfo = map.get(carNum);
                if (type.equals("IN")) {
                    carParkingInfo.setInTime(time);
                } else { // type == "OUT"
                    // 이전에 저장되어있는 입차시간 가져와서 계산
                    String inTime = carParkingInfo.getInTime();
                    carParkingInfo.setTotalTime(calculateTime(inTime, time));
                }
            } else {
                // OUT이 먼저 들어오는 경우는 제한사항에서 제외되었기에 고려하지 않아도 됨
                map.put(carNum, new ParkingInfo(carNum, time));
            }
        }

        /**
         * 2. records 확인
         *      - 출차 시간이 입력되지 않은 경우 totalTime 계산해서 갱신
         *      - ParkingInfo를 리스트에 저장 : 정렬을 위함
         */
        List<ParkingInfo> infoList = new ArrayList<>();
        for (ParkingInfo mapInfo : map.values()) {
            String infoInTime = mapInfo.getInTime();
            if (!infoInTime.isBlank()) {
                mapInfo.setTotalTime(calculateTime(infoInTime, "2359"));
            }
            infoList.add(mapInfo);
        }
        infoList.sort(ParkingInfo::compareTo);

        /**
         * 3. 주차 요금 계산
         */
        double basicTime = fees[0];
        int basicPrice = fees[1];
        double unitTime = fees[2];
        int pricePerTime = fees[3];

        int[] answer = new int[map.size()];
        int idx = 0;
        for (ParkingInfo info : infoList) {
            int calPrice = basicPrice;
            if (info.getTotalTime() >= basicTime) {
                calPrice += Math.ceil((info.getTotalTime() - basicTime)/unitTime) * pricePerTime;
            }
            answer[idx++] = calPrice;
        }

        return answer;
    }

    public static double calculateTime(String in, String out) {
        double inH = Integer.parseInt(in.substring(0,2));
        double inM = Integer.parseInt(in.substring(2));
        double outH = Integer.parseInt(out.substring(0,2));
        double outM = Integer.parseInt(out.substring(2));

        return (outH * 60 + outM) - (inH * 60 + inM);
    }

    public static class ParkingInfo implements Comparable<ParkingInfo>{
        String carNum; // 차량번호

        String inTime; // 입차시간 (주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우는 입력에 없기 때문에)
        double totalTime; // 총 누적시간

        public ParkingInfo(String carNum, String inTime) {
            this.carNum = carNum;
            this.inTime = inTime;
            this.totalTime = 0;
        }

        public void setInTime(String inTime) {
            this.inTime = inTime;
        }

        public String getInTime() {
            return inTime;
        }

        public void setTotalTime(double totalTime) {
            this.inTime = ""; // 입차시간 초기화 (출차시간 입력되는 경우에만 totalTime Setting)
            this.totalTime += totalTime;
        }

        public double getTotalTime() {
            return totalTime;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ParkingInfo other = (ParkingInfo) o;
            return other.carNum == carNum;
        }

        @Override
        public int hashCode() {
            return Objects.hash(carNum);
        }

        @Override
        public int compareTo(ParkingInfo o) {
            int intCarNum = Integer.parseInt(this.carNum);
            int intOtherCarNum = Integer.parseInt(o.carNum);
            return intCarNum - intOtherCarNum;
        }
    }
}

참고 포스팅

문제 링크

문제 설명

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k 입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

제한사항

• 5 ≤ sequence의 길이 ≤ 1,000,000 
  • 1 ≤ sequence의 원소 ≤ 1,000 
  • sequence는 비내림차순으로 정렬되어 있습니다. 
• 5 ≤ k ≤ 1,000,000,000 
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

입출력 예

문제 풀이

[고려사항]

sequence는 최대 1,000,000(100만)개이니까 시간 복잡도를 고려해서 구현해야한다.

O(N^2)이 되면 1,000,000,000,000가 되어서 시간 초과로 실패할 것이기 때문이다.

[처음 생각으로만 한 풀이방법]

[실제 구현한 알고리즘 / 구현방법]

이 문제는 특정 조건을 만족하는 부분 구간을 구하는 문제이므로 투 포인터(Two Pointer) 알고리즘을 이용해서 풀면 된다.

투 포인터(Two Pointer) 알고리즘은 일반적으로 배열이 정렬되어 있을 때 사용하는 알고리즘이다.

투 포인터 알고리즘은 선형시간 복잡도를 가지므로 효율적이고, 한 번의 반복으로 모든 요소를 처리할 수 있다.

배열을 순회하면서 누적합을 앞에서부터 구하면 되니까

start pointer를 0번에 두고 end pointer의 인덱스를 이동시키면서 누적 합을 구한다.

누적 합이 k 를 초과하면 start pointer를 이동시켜서 start ~ end pointer의 합을 구한다.

이때 마지막으로 저장된 누적 합에서 sequence[start pointer]를 빼주면 현재의 start ~ end pointer의 합이 된다.

예를 들어, [1,2,3,4,5]라면 1부터 4까지 누적하면 합이 10이므로 k를 넘어선다.

이때 start pointer를 2로 옮기면 2부터 4까지의 합인데, 이 합은 10에서 1을 뺀 9이다.

그렇게 진행하다가 누적합이 k와 같아지면 해당 start pointer와 end pointer를 반환한다.

start, end pointer를 앞쪽 인덱스부터 시작하면 가장 짧은 길이 + 가장 작은 인덱스 값을 만족시키는 인덱스를 반환할 수 있다.

[풀이 과정]

1. 첫번째 인덱스부터 start pointer와 end pointer가 마지막 인덱스를 가리킬때까지, 아래 과정을 반복하여 정답 후보를 구한다.
   1. 누적 합이 k인 경우(sum==k), 정답 후보에 해당 인덱스를 저장한다.(start pointer, end pointer)
   2. 누적 합이 k보다 작고(sum<k), end pointer가 마지막 인덱스가 아니라면, end pointer를 한 칸 이동하고, 누적 합을 계산한다.
   3. 누적 합이 k보다 크거나(sum>k), end pointer가 마지막 인덱스라면, 현재 start pointer의 값을 누적 합에서 빼주고 start pointer를 한 칸 이동한다. 
2. 정답 후보 중 1) 길이가 짧고, 2) 인덱스가 가장 작은 부분 수열 인덱스를 반환한다.

[구현시 고려한 사항]

최종 답을 list에서 SubSequence 클래스의 left, right를 각각 가져와서 int배열로 반환을 할지 고민했는데, 

• 즉, return new int[]{answerList.get(0).left, answerList.get(0).right};

SubSequence 클래스에 (left, right)를 int 배열로 반환하는 함수(getSequence)를 생성해서 반환하는 걸로 구현했다.

함수를 생성하는게 가독성이 좋고, 

• return answerList.get(0).getSequence();

생성한 SubSequence 클래스의 요소를 조합해서 반환하는 것이므로 SubSequence 클래스에 함수를 생성하는 것이 이 클래스의 목적성도 좀 더 명확하다고 생각했기 때문이다.

코드

public class Solution {
    public static int[] solution(int[] sequence, int k) {
        int startPointer = 0;
        int endPointer = 0;
        List<SubSequence> answerList = new ArrayList<>(); // 정답 후보 저장할 리스트

        int sum = sequence[startPointer];
        int length = sequence.length;
        while (true) { // end pointer가 마지막 인덱스를 탐색할 때까지
            if (sum == k) answerList.add(new SubSequence(startPointer, endPointer, endPointer-startPointer+1));

            if (startPointer == length - 1 && endPointer == length - 1) break;

            if (sum < k && endPointer < length - 1) { // 누적 합이 k보다 작다면
                endPointer++; // end pointer 한칸 이동
                sum += sequence[endPointer]; // 누적 합 계산
            } else { // 누적 합이 k보다 크거나 end pointer가 마지막 인덱스라면
                sum -= sequence[startPointer]; // 움직인 start pointer에서 end pointer까지의 누적합은 움직이기 전 start pointer를 뺀 값
                startPointer++; // start pointer 이동
            }
        }
        // 정답 후보에서 1) 길이가 짧고 2) 인덱스가 작은 부분 수열 인덱스를 반환
        answerList.sort(SubSequence::compareTo);

        return answerList.get(0).getSequence();
    }

    public static class SubSequence implements Comparable<SubSequence> {
        int left, right, size;
        public SubSequence(int left, int right, int size) {
            this.left = left;
            this.right = right;
            this.size = size;
        }

        public int[] getSequence() {
            return new int[]{this.left, this.right};
        }

        @Override
        public int compareTo(SubSequence o) {
            if (this.size == o.size) return this.left - o.left;
            else return this.size - o.size;
    }
}

문제 링크

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 

"()()" 또는 "(())()" 는 올바른 괄호입니다. 

")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. 

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수 
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

첫번째 문제 풀이

* 혼자 풀어본 후 다른 코드를 보고나서 개선된 문제풀이를 하나 더 작성했다.

괄호 문자열(s)를 한 문자씩 확인하면서 다음 문자랑 괄호 조합이 되는지 확인해야한다.

괄호를 Stack에 쌓으면서 이전 문자와 다음 문자의 조합이 괄호가 되는지 알 수 있다.

원본 문자열의 문자를 저장할 Stack과 괄호 조합이 안되는 경우 저장할 Stack을 두 개 선언하여 구현했다.

[고려사항]

괄호 문자열(s)는 최대 100,000(10만)개 이하이므로 문자열 조작에 대한 시간 복잡도를 고려해야한다.

시간을 최소화할 수 있는 방법으로 Stack을 생각했다.

Stack의 삽입, 삭제, isEmpty, peek 연산은 모두 O(1)의 시간 복잡도를 가지고, 필요한 연산은 저 4가지면 되기 때문이다.

그래서 내가 구현한 방식에서는

    1) Stack에 문자열을 문자로 변환하여 삽입 : O(N)

    2) Stack을 순회하면서 Stack 연산 : O(N)이라서

전체 시간 복잡도는 O(N)이 된다.

[풀이 과정]

1. 문자열을 문자(char)로 변환해서 원본 Stack에 할당한다. 
   • String에서 char로 형변환을 하기 위해 charAt()을 이용한다.
2. 괄호 완성이 안되는 경우, 원본 Stack의 char값을 저장할 Stack을 선언
3. 아래 과정을 원본 Stack이 빌 때 까지 반복한다.
4. 원본 Stack에서 pop()한 값을, 저장 Stack에 값이 있는 경우에 괄호 완성이 되는지 확인한다.
   • 괄호가 완성되면 저장 Stack에서 해당 값을 pop(); ➔ 괄호 삭제
   • 괄호가 완성되지 않으면 저장 Stack에 해당 값을 push();
5. 반복문이 끝난 후, 저장 Stack에 값이 남아있다면 올바른 괄호가 아니다.
   • 괄호가 완성되어서 값이 pop(), 즉 삭제되었다면 저장 Stack은 비어있어야한다.

첫번째 코드

import java.util.*;
class Solution {
	public boolean solution(String s) {
        Stack<Character> stackInitial = new Stack<>(); // 문자열을 문자로 분할해서 넣을 Stack
        for (int i=0; i<s.length(); i++) {
            stackInitial.push(s.charAt(i));
        }

        char c;
        Stack<Character> stackStorage = new Stack<>(); // 괄호 완성이 안되는 경우 초기 Stack의 char 값을 저장할 Stack
        while (!stackInitial.isEmpty()) {
            c = stackInitial.pop();
            if (!stackStorage.isEmpty()) {
                char charStorage = stackStorage.peek();
                if (c == '(' && charStorage == ')') { // 괄호 완성하면 다음 문자로 넘어감
                    stackStorage.pop();
                    continue;
                }
            }
            stackStorage.push(c);
        }

        // 남은 문자열이 있으면 실패
        if (!stackStorage.isEmpty()) return false;
        else return true;
    }
}

두번째 문제 풀이

다른 사람들의 풀이를 보니까, 완성되지 않은 괄호를 굳이 Stack에 넣지 않고 열린 괄호와 닫힌 괄호의 개수로 확인하는 방법도 있다.

열린 괄호인 경우엔 변수를 증가시키고, 닫힌 괄호인 경우엔 변수를 감소시키면서 연산하고,

마지막에 변수가 0인 경우에만 올바른 괄호라고 판단하면 된다.

실행 시간을 비교해보면 Stack을 이용한 첫번째 코드보다 훨씬 개선된 것을 확인할 수 있었다.

 두번째 코드

class Solution {
    boolean solution(String s) {
        
        int cnt = 0;
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') { // 열린 괄호일때
                cnt++;
            } else {
                if (cnt == 0) return false; // 닫힌 괄호일때 cnt가 0이면 열린 괄호가 없는것이므로 올바른 괄호 아님
                else cnt--;
            };
        }
        if (cnt == 0) return true;
        else return false;
        
    }
}

문제 링크

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

문제 풀이

우선 카펫의 전체 너비는 갈색 격자와 노란 격자를 합한 값이 되고, 그건 가로*세로와 같다.

전체 너비(total) = brown + yello = 가로 * 세로

그리고 카펫의 테두리의 1줄은 갈색으로 칠해져 있다고 했으므로, 

노란 격자의 양 옆과 위, 아래로 갈색 격자가 1개씩 있어야 하기때문에 아래와 같은 식이 성립한다.

노란 격자(yellow) = (가로 - 2) * (세로 - 2)

두 식을 통해 갈색 격자는 아래와 같은 식을 만족한다.

갈색 격자(brown) = 총 너비(total) - yello

결국, 노란 격자와 갈색 격자의 식을 모두 만족하는 가로, 세로 조합을 구하면 되는 문제!

[알고리즘, 구현방법]

이 문제는 가로*세로 조합에 대한 탐색이 필요하므로, 완전 탐색으로 풀었다.

[풀이 과정]

1. 가로*세로 조합 탐색 (가로가 큰 기준)
2. 총 너비를 가로로 나누었을때, 나머지가 생기지 않는 경우, 즉 나누어 떨어지는 경우만 탐색
   • 각 조합마다 가로와 세로가 yellow, brown 식에 대입했을때 모두 true인 경우가 정답
3. 정답이 나올때까지 반복

[구현시 고려한 사항]

카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 길기때문에 조합을 탐색할때 가로가 큰 경우부터 확인한다.

 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int total = brown + yellow;

        // 가로 길이 <= 세로 길이 이므로, 가로 길이가 큰 것 부터 탐색
        for (int width=total; width>0; width--) {
            if (total % width != 0) continue; // 나누어 떨어지지 않는 경우 넘어가기

            int height = total / width;
            int y = (width-2) * (height-2);
            if (brown == total - y && yellow == y) {
                answer[0] = width;
                answer[1] = height;
                break;
            }
        }
        return answer;
    }
}

문제 링크

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 

   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5 

   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12] 

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 

   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13 

   가진 음식의 스코빌 지수 = [13, 9, 10, 12] 

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

문제 풀이

[고려사항]

scoville 배열을 오름차순으로 정렬해서 1번째 원소가 K 이상일때까지 음식을 섞어서 횟수를 구한다.

- 새로운 음식의 스코빌 지수를 만들때마다 scovillle 배열은 오름차순으로 정렬되어야 한다. 

- scoville의 길이는 최대 1,000,000(100만), K는 최대 1,000,000,000(10억)이므로 시간복잡도를 고려해야한다.

[알고리즘, 구현방법]

이 문제는 array나 ArrayList로 구현하면 효율성 검증을 통과하지 못한다.  

그래서 최솟값을 빠르게 찾을 수 있는 완전 이진트리 형태의 구조를 가지는 Heap으로 구현해야한다.

처음에는 Heap의 삽입, 삭제 연산을 array로 구현해서 제출했는데 시간초과로 실패했다.

*이후에 찾아보니까 이 문제를 Heap으로 직접 구현해서 푸는걸 시도한 사람들도 실패했다고 한다.

그래서 Java에서 Heap구조를 가진 PriorityQueue(우선순위 큐)로 구현했다. 

[풀이 과정]

1. 우선순위 큐를 오름차순으로 생성하여 scovile 값 삽입
2. Queue의 1,2번째 원소를 가져와서 계산 
   • 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
3. 계산한 값을 Queue에 삽입하고 섞은 횟수 증가
4. 2,3번 과정을 Queue의 첫번째 원소가 K보다 같거나 클때까지 반복
   • 이때, Queue의 사이즈가 2미만이면 스코빌 지수를 K이상으로 만들수 없다는 뜻이므로 -1 return

[구현시 고려한 사항]

PriorityQueue 함수 호출시 실패하는 경우 Exception을 던지는 함수가 아닌, null이나 false를 반환하는 함수로 구현했다.

• offer() vs add()
• poll() vs remove()
• element() vs peek()

정답 코드

import java.util.*;
class Solution {
    // PriorityQueue 사용하여 Heap (Min-Heap) 으로 구현
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int val : scoville) {
            queue.offer(val);
        }

        // 스코빌 지수 계산
        int first, second, mix;
        int count = 0; // 섞은 횟수
        // 루트 값이 K와 같거나 크면 종료
        while (queue.peek() < K) {
            if (queue.size() < 2) {
                return -1;
            } else {
                // 연산할 값 가져오기
                first = queue.poll();
                second = queue.poll();

                // 섞은 음식의 스코빌 지수를 삽입
                mix = first + (second * 2);
                queue.offer(mix);
                count++;
            }
        }
        return count;
    }
}

문제 링크

문제 설명

카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.

이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.

1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.

1번 목표가 우선이며, 2번 목표가 그 다음입니다. 

이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.

• n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
• 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.

카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.

• 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
• 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다.

이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ users의 길이 = n ≤ 100
  • users의 원소는 [비율, 가격]의 형태입니다.
  • users[i]는 i+1번 고객의 구매 기준을 의미합니다.
  • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
  • 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
• 1 ≤ emoticons의 길이 = m ≤ 7
  • emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
  • 100 ≤ emoticons의 원소 ≤ 1,000,000
  • emoticons의 원소는 100의 배수입니다.

입출력 예

문제 풀이

할인율(10%, 20%, 30%, 40%) 조합을 구해서 사용자(users)별로 모든 이모티콘의 구매 여부를 확인해서 계산해야한다.

모든 경우의 수를 확인해야하기 때문에 완전탐색으로 구현했다.

할인율은 4가지로 고정되어있고, 이모티콘은 최대 7개, 사용자는 최대 100명이므로 완전탐색으로 구현할 경우,

시간복잡도 Worst Case가 O(100*4^7)로, 약 160만 정도가 나오므로 완전탐색으로 구현할 수 있다고 생각했다.

[풀이 과정]

1. DFS로 모든 할인율 조합을 구하고
2. 모든 이모티콘에 적용할 할인율 조합이 결정되면
3. 사용자별로 이모티콘 할인율이 적용된 가격에 대한 구매 여부를 판단하여 (users 정보를 완전탐색)
4. 이모티콘 플러스 가입 여부와 매출액을 갱신
5. 모든 user의 탐색이 끝나면 해당 조합에 대한 최대값 여부를 확인하여 저장

코드

class Solution {
    static int[] percent = {10, 20, 30, 40}; // 할인율 배열
    static int maxSubscribeCnt = 0; // 최대 이모티콘 플러스 가입자 수
    static int maxProfit = 0; // 최대 이모티콘 매출액
    
    public int[] solution(int[][] users, int[] emoticons) {
        findMaxValue(0, emoticons.length, new int[emoticons.length], users, emoticons);
        return new int[]{maxSubscribeCnt, maxProfit};
    }

    public void findMaxValue(int index, int emotionsLength, int[] discounts, int[][] users, int[] emoticons) {
        // 이모티콘 개수만큼 할인율 조합이 생성되었다면 계산
        if (index == emotionsLength)
        {
            int subscribe = 0;
            int profit = 0;

            // 사용자별로 이모티콘의 할인율을 계산한 가격으로 판단
            for (int[] user : users) {
                int cost = 0; // 각 사용자가 지불할 금액

                for (int j=0; j<emotionsLength; j++) {
                    // 할인율이 사용자의 기준 비율 이상이면 이모티콘 구매
                    if (discounts[j] >= user[0]) {
                        cost +=  emoticons[j] * (100 - discounts[j])/100;
                    }
                }

                if (cost >= user[1]) subscribe++; // 사용자의 가격보다 총 합이 크면 구독 +1
                else profit += cost;  // 아니면 매출액에 포함
            }

            // 최대 값 갱신
            if (subscribe > maxSubscribeCnt) { // 가입자 수가 1순위이므로 먼저 체크
                maxSubscribeCnt = subscribe;
                maxProfit = profit;
            } else if (subscribe == maxSubscribeCnt) { // 최대 가입자 수와 계산한 가입자 수가 같으면, 매출액 갱신
                maxProfit = Math.max(maxProfit, profit);
            }
            return;
        }
        else
        {
            // 할인율 조합 생성
            for (int i=0; i<4; i++) {
                discounts[index] = percent[i];
                findMaxValue(index+1, emotionsLength, discounts, users, emoticons);
            }
        }

    }
}

www.acmicpc.net/problem/1500

문제

합이 S인 K개의 양의 정수 중 그 곱이 가장 큰 경우를 구하는 문제이다.

• 입력: 첫째 줄에 S와 K가 주어짐(K는 20보다 작거나 같고, S는 100보다 작거나 같으며 K보다 크거나 같다.
• 출력: 첫째 줄에 정답 출력. 답은 9,223,372,036,854,775,807보다 작다

풀이 과정

이 문제는 수학문제로, 곱하는 수의 차이가 가장 작은 경우를 구하면 된다.

1. S를 K로 나눠서 몫과 나머지를 각각 저장한다.

2. 몫을 K개 만큼 저장한다.

3. 나머지 수만큼 몫에 1씩 더해준다. 이외의 것들은 몫으로 남겨둔다.

4. 수를 모두 곱해서 결과를 출력한다.  

예시

입력: S=52, K=9

1. S/K = 5, S%K = 7

2. 5,5,5,5,5,5,5,5,5

3. 나머지가 7이므로 7번 반복하여 몫에 1씩 더해준다

4. 6,6,6,6,6,6,6,5,5를 곱한 곱은 6,998,400

JAVA 소스코드

출력은 9,223,372,036,854,775,807보다 작으므로 변수는 모두 long형으로 선언한다.

※ 자바의 기본 자료형(primitive type) 정수형의 범위

* 백준에 자바코드로 올릴경우, class이름은 반드시 Main으로 해야하고 패키지명은 제외해야한다. 아니면 런타임에러 뜬다. 본인도 처음에 몰라서 알수없는 Runtime에러때문에 당황했었다.

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        List<Long> list = new ArrayList<>();//k개의 정수를 저장할 리스트
        long result = 1; //k개의 정수를 곱한 결과
        long s = scan.nextInt();
        long k = scan.nextInt();
        long div = s/k; //s를 k로 나눈 몫
        long res = s%k; //나머지

        //몫을 k개만큼 저장
        for(int i=0;i<k;i++){
            list.add(div);
        }
        //나머지만큼만 1씩 더함
        for(int i=0;i<res;i++){
            list.set(i,(list.get(i)+1));
        }
        //result에 k개의 정수를 곱함
        for(int i=0;i<list.size();i++){
            result *= list.get(i);
        }

        System.out.println(result);
    }
}