개발옹

문제 링크

문제 설명

완호네 회사는 연말마다 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;
    }
}