쌉쌀한 무화과의 개발로그

[문제]

로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1

로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다.

알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다. 당첨 번호 6개가 31, 10, 45, 1, 6, 19라면, 당첨 가능한 최고 순위와 최저 순위의 한 예는 아래와 같습니다.

순서와 상관없이, 구매한 로또에 당첨 번호와 일치하는 번호가 있으면 맞힌 걸로 인정됩니다.

알아볼 수 없는 두 개의 번호를 각각 10, 6이라고 가정하면 3등에 당첨될 수 있습니다.

3등을 만드는 다른 방법들도 존재합니다. 하지만, 2등 이상으로 만드는 것은 불가능합니다.

알아볼 수 없는 두 개의 번호를 각각 11, 7이라고 가정하면 5등에 당첨될 수 있습니다.

5등을 만드는 다른 방법들도 존재합니다. 하지만, 6등(낙첨)으로 만드는 것은 불가능합니다.

민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변수로 주어집니다. 이때, 당첨 가능한 최고 순위와 최저 순위를 차례대로 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

​

제한사항

lottos는 길이 6인 정수 배열입니다.

lottos의 모든 원소는 0 이상 45 이하인 정수입니다.

0은 알아볼 수 없는 숫자를 의미합니다.

0을 제외한 다른 숫자들은 lottos에 2개 이상 담겨있지 않습니다.

lottos의 원소들은 정렬되어 있지 않을 수도 있습니다.

win_nums은 길이 6인 정수 배열입니다.

win_nums의 모든 원소는 1 이상 45 이하인 정수입니다.

win_nums에는 같은 숫자가 2개 이상 담겨있지 않습니다.

win_nums의 원소들은 정렬되어 있지 않을 수도 있습니다.

​

입출력 예

입출력 예 설명

입출력 예 1

문제 예시와 같습니다.

​

입출력 예 2

알아볼 수 없는 번호들이 아래와 같았다면, 1등과 6등에 당첨될 수 있습니다.

입출력 예 3

민우가 구매한 로또의 번호와 당첨 번호가 모두 일치하므로, 최고 순위와 최저 순위는 모두 1등입니다.

실제로 사용되는 로또 순위의 결정 방식과는 약간 다르지만, 이 문제에서는 지문에 명시된 대로 로또 순위를 결정하도록 합니다.

>문제 풀이

2021 Dev-Matching: 웹 백엔드 개발자(상반기) 코테에 나왔던 문제입니다.

프로그래머스에 문제모음에서 확인하실 수 있습니다.

​

[배경]

문제는 매우 길지만, 다 읽고 보면 매우 간단합니다.

로또 한 장에 6개의 숫자가 있고, 6개가 다 맞을 경우 1등이고, 차례로 5개 2등부터~ 2개 5등 그리고 1개 이하는 낙첨입니다.

[입력]

민우가 로또를 샀는데 동생이 로또에 낙서를 하는 바람에 일부 숫자가 지워져서 0으로 입력된다고 합니다.

[출력]

민우의 로또에 0으로 입력된게 맞는지 틀릴지에 따라, 민우가 당첨될 수 있는 최고 순위와 최저 순위를 answer[] 배열에 담아 출력하면 됩니다.

​

[풀이]

HashSet에 당첨 숫자를 넣어주고,

lotto배열을 돌리면서 당첨 숫자가 몇개인지(rightCnt), 0으로 입력된 숫자가 몇개인지(zeroCnt) 카운팅 합니다.

​

최고 순위는 0으로 입력된 숫자들이 전부 당첨 번호인 경우, 최저 순위는 0으로 입력된 숫자들이 모두 안맞을 경우 입니다. 이에 따라 순위를 출력해주면 됩니다.

>전체 코드

import java.util.HashSet;
class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        HashSet<Integer> set= new HashSet<>();
        
        for(int i: win_nums)
            set.add(i);
        
        int zeroCnt=0, rightCnt=0;
        for(int i: lottos){
            if(set.contains(i)) rightCnt++;
            else if(i==0) zeroCnt++;
        }
        
        answer[0]= 7-rightCnt-zeroCnt==7?6:7-rightCnt-zeroCnt;
        answer[1]= 7-rightCnt==7?6:7-rightCnt;
        
        return answer;
    }
}

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

[문제]

숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.

게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.

편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.

[입력]

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. 모든 건물을 짓는 것이 가능한 입력만 주어진다.

[출력]

N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.

[예제]

>문제 풀이

위상정렬 문제였는데, 이론을 배우긴 했는데 문제로 풀어보는건 처음이라 다른 블로그의 코드를 참고하여 공부하였습니다.

​

문제 조건

1. 어떤 건물을 짓기 위해 다른 건물을 먼저 지어야 할 수도 있다.

2. 여러 건물을 동시에 지을 수 있다.

​

순환이(cycle) 없고 상대적 순서를 지켜서 수행해야 한다. -> 위상정렬 (Topological Sort)

inDegree: 선행건물들의 개수가 0인 애들을 큐에 넣어서 실행시간을 넣어놓고 이 건물을 선행 조건으로 하는 건물들을 살펴봐야한다.

선행 건물들 부터 실행시간을(여기서 말한 실행시간은 선행조건을 포함한 건설시간) 저장해놓고 다음 건물을 지어야 함으로 dp적인 요소가 들어갔다고 할 수 있다.(Memoization)

​

나도 다른 분의 코드와 설명을 참고하여 공부했기 때문에 이상 자세한 설명은 생략한다.

(세부적인 내용은 아래 블로그를 참고하길 바랍니다.)

​

https://subbak2.tistory.com/53

>전체 코드

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

public class Main {
	static int N;
	static Building[] buildingList;
	static int input;
	static Queue<Integer> queue;
	static StringBuilder sb= new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		//1.입력
		N= Integer.parseInt(br.readLine());
		buildingList= new Building[N+1];
        for(int i=1; i<=N; i++{
			buildingList[i]= new Building();
        }
		
		//2. N개의 건물정보 입력
		for(int i=1; i<=N; i++) {
			st= new StringTokenizer(br.readLine());
			
			buildingList[i].time= Integer.parseInt(st.nextToken());
			input= Integer.parseInt(st.nextToken());
			while(input!=-1) {
				buildingList[i].inDegree++;
				buildingList[input].adjList.add(i);
				input= Integer.parseInt(st.nextToken());
			}
		}
		
		//2. 위상정렬 재료 만들기
		//- 선행건물이 없는 경우(inDegree=0)인 경우 큐에 넣기
		queue= new ArrayDeque<Integer>();
		for(int i=1; i<=N; i++) {
			if(buildingList[i].inDegree==0) {
				queue.add(i);
			}
		}
		
		//3. 위상정렬
		while(!queue.isEmpty()) {
			//1) 선행건물이 더이상 없는 녀석을 뽑아서 최종 건설시간에 자기 자신을 더해줌
			int quePoll= queue.poll();
			buildingList[quePoll].result+= buildingList[quePoll].time;
			
			//2) 자신을 지어야 지을 수 있는 건물들에게 선행건물의 건설이 끝났음을 알림
			for(int i: buildingList[quePoll].adjList) {
				//2-1) 선행건물의 개수 빼주기
				buildingList[i].inDegree--;
				//2-2) 타겟건물은 아직 건물을 지을 수 없는 상태
				//->현재 상태에서 타겟 건물의 res는 선행건물의 건설시간 중 최댓값: res를 최댓값으로 갱신시켜야
				buildingList[i].result= Math.max(buildingList[i].result, buildingList[quePoll].result);
				//2-3) 타겟건물의 선행건물 개수가 0이면 큐에 넣기
				if(buildingList[i].inDegree==0) queue.add(i);
			}
		}
		
		for(int i=1; i<=N; i++) {
			sb.append(buildingList[i].result+"\n");
		}
		System.out.println(sb.toString());
		
	}//main
	
	public static class Building{
		int time;		//각 건물 건설시간
		int inDegree;	//건물의 선행조건 개수
		int result;		//선행건물 포함 건설시간
		ArrayList<Integer> adjList; //건물이 지어져야 지을수 있는 건물들
		
		public Building() {
			this.time= 0;
			this.inDegree= 0;
			this.result= 0;
			this.adjList= new ArrayList<Integer>();
		}
	}
        
}

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

[문제]

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

1번 학생의 키 < 5번 학생의 키

3번 학생의 키 < 4번 학생의 키

5번 학생의 키 < 4번 학생의 키

4번 학생의 키 < 2번 학생의 키

4번 학생의 키 < 6번 학생의 키

5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

[입력]

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.

[출력]

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

[예제]

>문제 풀이

1~N번 까지의 학생들의 키 순서를 상대적으로 비교한 정보가 주어진다.

이 정보를 통해 몇 번째로 키가 큰지 알 수 있는 학생이 몇 명인지 출력하라

​

어떤 학생에 대하여 자신을 제외한 1~N까지의 학생과 키를 비교할 수 있는지 확인해야한다.

그러나 한 명씩 매번 연산을 한다면 시간초과가 발생한다.

>> 모든 경로를 구해놓고서 1~N까지의 학생들이 가능한지 안한지만 체크해야한다.

​

플로이드-워셜 알고리즘

: 음의 간선 or 양의 간선에서 최단거리 파악할 수 있음

: 음의 싸이클 있으면 안되고 N<500일 때 다익스트라 보다 효율이 좋다고 알고있다.

​

​

::구현::

​

1) (N과 M을 입력받고,) int[][] distance 배열 선언 후 INF=999999999로 초기화

연결 여부 확인 할 때 비정상값인 경우 거르기 위해서 INF로 초기화 해놓는 것이다.

​

2) 키 정보값을 입력 받는다.

ex) i번 학생 < j번 학생 인 경우 distance[i][j]= 1;

​

3) for문을 돌면서 distance[i][j] 와 distance[i][k]+distance[k][j] 중 최소값을 선택한다.

( i는 출발지, j는 목적지, k는 경유지 // distance[i][j]: i에서 j로 가는 거리 )

어느 한쪽이 INF이면 다른 쪽을 선택할 것이고, 둘 다 INF이면 4)번에서 걸러진다.

​

4) 2중 for문 :: 1~N까지 확인하면서 distance[i][j]나 distance[j][i]가 INF가 아닌 경우를 cnt++카운팅 해서

cnt==N-1인 경우 answer++ 카운팅

//자기 자신 distance[i][j]는 무조건 INF 이다.

//그러니까 자신을 뺀 나머지랑 연결되어 있어야 하는데 이것을 cnt= N-1을 체크해줌으로써 확인이 가능하다.

>전체 코드

큰 차이는 없지만 두 가지 방법으로 풀어보았다.

어차피 연결여부만 확인하면 된다는 부분에서, int 보다는 boolean이 더 목적에 맞을 것 같아서 2)번으로도 고쳐본 것이다. 위의 설명을 이해했다면 2)번은 int->boolean이기 때문에 코드만 봐도 이해가 될 것 이다.

​

1) int[][] 배열 이용

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		final int INF= 999999999;
		int N, M, answer=0;
		int a, b;
		int[][] distance;
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st= new StringTokenizer(br.readLine());
		N= Integer.parseInt(st.nextToken());
		M= Integer.parseInt(st.nextToken());
		
		distance= new int[N+1][N+1];
		for(int i=1; i<N+1; i++) {
			Arrays.fill(distance[i], INF);
		}
		
		for(int i=0; i<M; i++) {
			st= new StringTokenizer(br.readLine());
			
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			
			distance[a][b]= 1; //a, b가 서로 연결되어있다.
		}
		
		//플로이드-워셜: 경유지-출발지-도착지 : 3중 for문
		//출발 i, 도착:j, 경유지:k
		for(int k=1; k<=N; k++) {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					distance[i][j]= distance[i][j]<=distance[i][k]+distance[k][j]?
									distance[i][j]:distance[i][k]+distance[k][j];
				}
			}
		}
		
		for(int i=1; i<=N; i++) {
			int cnt=0;
			for(int j=1; j<=N; j++) {
				if(distance[i][j]!=INF || distance[j][i]!=INF) cnt++;
			}
			if(cnt==N-1) answer++;
		}
		
        System.out.println(answer);
	}//main
        
}

2) boolean 배열

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		int N, M, answer=0;
		int a, b;
		boolean[][] distance;
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st= new StringTokenizer(br.readLine());
		N= Integer.parseInt(st.nextToken());
		M= Integer.parseInt(st.nextToken());
		
		distance= new boolean[N+1][N+1];
		
		for(int i=0; i<M; i++) {
			st= new StringTokenizer(br.readLine());
			
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			
			distance[a][b]= true; //a, b가 서로 연결되어있다.
		}
		
		//플로이드-워셜: 경유지-출발지-도착지 : 3중 for문
		//출발 i, 도착:j, 경유지:k
		for(int k=1; k<=N; k++) {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(distance[i][k]&&distance[k][j]) {
						distance[i][j]= true;
					}
				}
			}
		}
		
		boolean check;
		for(int i=1; i<=N; i++) {
			check= false;
			for(int j=1; j<=N; j++) {
				//i에서 시작해서 연결이 안된 학생이 있다.
				if(i!=j && !distance[i][j] && !distance[j][i]) {
					check= true;
					break;
				}
			}
			if(!check) answer++;
		}
		
        System.out.println(answer);
	}//main
        
}

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

[문제 설명]

개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다.

아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부여한 표입니다.

예를 들면, SQL의 SI 직업군 언어 점수는 3점이지만 CONTENTS 직업군 언어 점수는 2점입니다. SQL의 HARDWARE, PORTAL, GAME 직업군 언어 점수는 0점입니다.

직업군 언어 점수를 정리한 문자열 배열 table, 개발자가 사용하는 언어를 담은 문자열 배열 languages, 언어 선호도를 담은 정수 배열 preference가 매개변수로 주어집니다. 개발자가 사용하는 언어의 언어 선호도 x 직업군 언어 점수의 총합이 가장 높은 직업군을 return 하도록 solution 함수를 완성해주세요. 총합이 같은 직업군이 여러 개일 경우, 이름이 사전 순으로 가장 빠른 직업군을 return 해주세요.

​

[제한사항]

table의 길이 = 5

table의 원소는 "직업군 5점언어 4점언어 3점언어 2점언어 1점언어"형식의 문자열입니다. 직업군, 5점언어, 4언어, 3점언어, 2점언어, 1점언어는 하나의 공백으로 구분되어 있습니다.

table은 모든 테스트케이스에서 동일합니다.

1 ≤ languages의 길이 ≤ 9

languages의 원소는 "JAVA", "JAVASCRIPT", "C", "C++" ,"C#" , "SQL", "PYTHON", "KOTLIN", "PHP" 중 한 개 이상으로 이루어져 있습니다.

languages의 원소는 중복되지 않습니다.

preference의 길이 = languages의 길이

1 ≤ preference의 원소 ≤ 10

preference의 i번째 원소는 languages의 i번째 원소의 언어 선호도입니다.

return 할 문자열은 "SI", "CONTENTS", "HARDWARE", "PORTAL", "GAME" 중 하나입니다.

​

[입출력 예]

​

[입출력 예 설명]

입출력 예 1

각 직업군 별로 점수를 계산해보면 아래와 같습니다.

아래 사진은 개발자 언어 선호도 나타낸 표입니다.

아래 사진은 개발자가 선호하는 언어의 직업군 언어 점수를 나타낸 표입니다.

따라서 점수 총합이 41로 가장 높은 "HARDWARE"를 return 해야 합니다.

​

입출력 예 2

각 직업군 별로 점수를 계산해보면 아래와 같습니다.

아래 사진은 개발자 언어 선호도 나타낸 표입니다.

아래 사진은 개발자가 선호하는 언어의 직업군 언어 점수를 나타낸 표입니다.

점수 총합이 55로 가장 높은 직업군은 "SI" 와 "PORTAL"입니다.

따라서 사전 순으로 먼저 오는 "PORTAL"을 return 해야 합니다.

>문제 풀이

table[] 에 5개 직업군이 선호하는 언어 5개가 문자열로 저장되어있다.

languages[] 에 개발자가 선호하는 언어

preference[] 에 선호하는 언어의 선호 점수가 저장되어있다.

​

table이 말이 테이블이지 문자열로 저장되어있기 때문에 쪼개서 ArrayList[] score 에 저장해준다.

(2차원 배열을 쓰지 않은 이유는 선호하는 언어를 찾기 쉽다. for문 하나를 줄이려고

// 근데 어차피 직업군이 5개에 언어도 5개라서 굳이 리스트 안써도 될 것 같다.)

​

그리고 개발자가 입력한 언어가 있는지 확인해보고 회사의 선호 점수와 개발자의 선호점수를 곱해서 각 직무별 총합 선호점수를 구한다.

결과는 result[5][2]에 저장하는데 result[i][0]에는 회사 직업군, result[i][1]에는 점수 총합이 담긴다.

​

이제 직업군에 따라 구한 선호점수 총합에 따라 result배열을 정렬을 하고 만약 총점이 같으면 직업군 이름의 사전순으로 가장 먼저 나오는 것을 answer로 한다.

>전체 코드

import java.util.*;
class Solution {
    public String solution(String[] table, String[] languages, int[] preference) {
        String answer= "";
        ArrayList[] score= new ArrayList[5];
        String[][] result= new String[5][2];
        
        for(int i=0; i<5; i++){
            String[] strArr= table[i].split(" ");
            score[i]= new ArrayList<String>(Arrays.asList(strArr));
            
            result[i][0]= score[i].get(0).toString();
            int calc= 0;
            for(int j=0; j<languages.length; j++){
                if(score[i].contains(languages[j])){
                    calc+= preference[j]*(6-score[i].indexOf(languages[j]));
                }
            }
            result[i][1]= calc+"";
        }
        Arrays.sort(result, new Comparator<String[]>(){
            public int compare(String[] o1, String[] o2){
                if(Integer.parseInt(o1[1])==Integer.parseInt(o2[1])){
                    return o1[0].compareTo(o2[0]);
                }else{
                    return Integer.parseInt(o2[1])-Integer.parseInt(o1[1]);
                }
            }
        });
        
        answer= result[0][0];
        
        return answer;
    }
}

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

[문제 설명]

사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다.

입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.

오늘 회의실에는 총 n명이 입실 후 퇴실했습니다. 편의상 사람들은 1부터 n까지 번호가 하나씩 붙어있으며, 두 번 이상 회의실에 들어온 사람은 없습니다. 이때, 각 사람별로 반드시 만난 사람은 몇 명인지 구하려 합니다.

​

예를 들어 입실 명부에 기재된 순서가 [1, 3, 2], 퇴실 명부에 기재된 순서가 [1, 2, 3]인 경우,

- 1번과 2번은 만났는지 알 수 없습니다.

- 1번과 3번은 만났는지 알 수 없습니다.

- 2번과 3번은 반드시 만났습니다.

​

또 다른 예로 입실 순서가 [1, 4, 2, 3], 퇴실 순서가 [2, 1, 3, 4]인 경우,

- 1번과 2번은 반드시 만났습니다.

- 1번과 3번은 만났는지 알 수 없습니다.

- 1번과 4번은 반드시 만났습니다.

- 2번과 3번은 만났는지 알 수 없습니다.

- 2번과 4번은 반드시 만났습니다.

- 3번과 4번은 반드시 만났습니다.

회의실에 입실한 순서가 담긴 정수 배열 enter, 퇴실한 순서가 담긴 정수 배열 leave가 매개변수로 주어질 때, 각 사람별로 반드시 만난 사람은 몇 명인지 번호 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

​

제한사항

1 ≤ enter의 길이 ≤ 1,000

1 ≤ enter의 원소 ≤ enter의 길이

모든 사람의 번호가 중복없이 하나씩 들어있습니다.

​

leave의 길이 = enter의 길이

1 ≤ leave의 원소 ≤ leave의 길이

모든 사람의 번호가 중복없이 하나씩 들어있습니다.

[입출력 예]

입출력 예 설명

입출력 예 1

만약, 다음과 같이 회의실에 입실, 퇴실했다면

1번과 2번은 만나지 않습니다.

1번과 3번은 만납니다

2번과 3번은 만납니다.

만약, 다음과 같이 회의실에 입실, 퇴실했다면

1번과 2번은 만나지 않습니다.

1번과 3번은 만나지 않습니다.

2번과 3번은 만납니다.

위 방법 외에 다른 순서로 입실, 퇴실 할 경우 1번과 2번이 만나도록 할 수도 있습니다. 하지만 2번과 3번이 만나지 않도록 하는 방법은 없습니다.

따라서

1번과 2번은 만났는지 알 수 없습니다.

1번과 3번은 만났는지 알 수 없습니다.

2번과 3번은 반드시 만났습니다.

​

입출력 예 2

문제의 예시와 같습니다.

​

입출력 예 3

1번과 2번은 만났는지 알 수 없습니다.

1번과 3번은 반드시 만났습니다.

2번과 3번은 반드시 만났습니다.

​

입출력 예 4

1번과 2번은 반드시 만났습니다.

1번과 3번은 반드시 만났습니다.

2번과 3번은 반드시 만났습니다.

​

입출력 예 5

1번과 2번은 반드시 만났습니다.

1번과 3번은 만났는지 알 수 없습니다.

1번과 4번은 반드시 만났습니다.

2번과 3번은 만났는지 알 수 없습니다.

2번과 4번은 반드시 만났습니다.

3번과 4번은 만났는지 알 수 없습니다.

>문제 풀이

n명이 회의실에 들어왔다가 나가는데, i번째 사람이 반드시 만난 사람이 몇명인지 사람의 번호 순서대로 answer[] 배열에 담아서 return

​

- 입실과 퇴실은 동시에 이루어지지 않는다.

- 두번 이상 입실한 사람은 없다

​

>문제 풀이

[1, 4, 2, 3] - [2, 1, 3, 4]

들어왔다가 나가는 리스트를 구해보면

: 1, 4, 2, 2, 1, 3, 3, 4 : 이렇게 됩니다.

​

ex) 1번의 입장에서는 입실 시, 방 안에 아무도 없고 이후에 4, 2 번을 만나고 퇴실합니다. 즉 2명

ex) 2번의 입장에서는 입실 시, 방 안에 있던 1, 4번을 만나고 이후에 퇴실하게 됩니다. 즉, 2명

ex) 3번의 입장에서는 입실 시, 방 안에 있던 4번을 만나고 이후에 퇴실하게 됩니다. 즉, 1명

ex) 4번의 입장에서는 입실 시, 방 안에 있던 1번을 만나고 이후에 2, 3번을 만나게 됩니다. 즉 3명

​

전에 들어와있던 애 + 앞으로 나가기 전에 들어온 애들

answer[i]= (i이 들어가기 전에 방 안에 있는 사람)+ (i가 들어오고나서 나갈 때까지 만난 사람)

>전체 코드

import java.util.LinkedList;
import java.util.HashSet;
class Solution {
    public int[] solution(int[] enter, int[] leave) {
        int[] answer = new int[enter.length];
        LinkedList<Integer> list= new LinkedList<>();
        
        //입퇴실 순서를 list에 넣기
        for(int i=0, j=0; i<enter.length||j<leave.length;){ 
            if(list.isEmpty()){
                list.add(enter[i++]);
                continue;
            }
            if(list.contains(leave[j])){
                list.add(leave[j++]);
            }else{
                list.add(enter[i++]);
            }
        }
        
        HashSet<Integer> remainSet= new HashSet<>(); //방 안에 있던 사람
        HashSet<Integer> rangeSet= new HashSet<>();  //새로 만나는 사람
        for(int i=0; i<list.size(); i++){
            int num= list.get(i);   //i번째 사람
            if(remainSet.contains(list.get(i))){ //이미 입실한 적 있으면 퇴실
                remainSet.remove(num);
                continue;
            }
            remainSet.add(num); //처음 입실
            for(int j=i+1; j<list.size(); j++){ //입실 후 퇴실까지 만난 사람들
                if(list.get(j)==num) break;
                rangeSet.add(list.get(j));
            }
            rangeSet.addAll(remainSet); //두 set을 합친다.(방안+새로만난)
            answer[num-1]= rangeSet.size()-1; //set에 나 자신도 포함됨, 빼주기
            rangeSet.clear();
        }
        
        return answer;
    }
}

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

+) 나쁘지 않은 구조로 짰다고 생각했는데 더 컴팩트하게 구현하신 분들도 계시더라고요.

코드는 그냥 이 사람은 이렇게 짰구나 참고만 해주세요:)