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

지난번에 풀었던 신고결과받기 문제가 레벨1 치고 신경쓸게 많아서 걱정했는데,

이번 문제는 정말 간단한 난이도였습니다.

라이브러리나 자료구조(배열을 제외한)의 활용 없이 반복문과 조건문 정도만 사용해도 풀이가 가능했습니다.

내 로또에서 맞춘 번호의 갯수를 c (Correct Number) 맞출 가능성이 있는 번호의 갯수를 p (Potential Number)로 따로 카운팅하고 번호 갯수에 따라 미리 등수 배열을 만들어 놓은 뒤 넣어주는 식으로 구현했습니다.

만약 로또용지의 번호 갯수가 달랐다면 내가 이미 맞춰서 소비된 번호를 고려한다던지 예외적인 상황이 발생했을것 같지만 문제의 조건에선 별다른 특이사항이 보이지 않아서 쉽게 구현했습니다.

import java.util.Arrays;

public class q77484_Programmers_로또의최고순위와최저순위 {

	static int[] lottos = { 44, 1, 0, 0, 31, 25 };
	static int[] win_nums = { 31, 10, 45, 1, 6, 19 };

	public static void main(String[] args) {
		int[] answer = { 0, 0 };
		int[] grade = { 6, 6, 5, 4, 3, 2, 1 };

		int p = 0;
		// potential Num
		int c = 0;
		// correct Num

		for (int i = 0; i < 6; i++) {
			if (lottos[i] == 0) {
				p++;
			} else {
				for (int j = 0; j < 6; j++) {
					if (lottos[i] == win_nums[j]) {
						c++;
						break;
					}
				}
			}
		}
		
		answer[0] = grade[p+c];
		answer[1] = grade[c];
		
		System.out.println(Arrays.toString(answer));
	}
}

프로그래머스 코딩테스트 연습의 문제입니다.

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

문제 자체는 간단한 시뮬레이션입니다.

주의해야할 점은 신고를 당한 이용자가 아닌 신고자에게 결과를 보내야한다는 점,

그리고 같은 신고를 여러번 하는 경우를 예외처리해 하나로 카운팅 해야 한다는 점 입니다.

저는 HashMap 자료구조를 활용해 이용자의 id를 Integer로 연결시키고,

같은 크기의 배열을 활용해 신고 기록을 저장, 활용했습니다.

이용자의 전체 크기가 최대 1000명이기 때문에 해당 2차원 배열의 크기는 1000x1000으로 코딩테스트에서 사용하기에 큰 무리가 없다고 생각했습니다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class q92334_Programmers_신고결과받기 {

	static String[] id_list = { "muzi", "frodo", "apeach", "neo" };
	static String[] report = { "muzi frodo", "apeach frodo", "frodo neo", "muzi neo", "apeach muzi" };
	static int k = 2;

	public static void main(String[] args) {

		int user = id_list.length;
		boolean[][] log = new boolean[user][user];
		int[] count = new int[user];
		int[] answer = new int[user];
		Map<String, Integer> map = new HashMap<String, Integer>();

		for (int i = 0; i < id_list.length; i++) {
			map.put(id_list[i], i);
		}

		for (int i = 0; i < report.length; i++) {
			StringTokenizer st = new StringTokenizer(report[i]);
			int reporter = map.get(st.nextToken());
			int target = map.get(st.nextToken());

			if (!log[reporter][target]) {
				log[reporter][target] = true;
				count[target]++;
			}
		}
		
		for(int i = 0; i < id_list.length; i++) {
			if(count[i] >= k) {
				for(int j = 0; j < id_list.length; j++) {
					if(log[j][i]) {
						answer[j]++;
					}
				}
			}
		}
		
		System.out.println(Arrays.toString(answer));
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

1. 이해 (5분) - 1분

문제도 깔끔하고 이해에 어려운 부분도 없어 금방 이해를 마쳤습니다.

정답이 가능한 범위가 무척 넓은데 여기서 이분 탐색 문제임을 유추했습니다. 

(최악의 경우 스태프 1명이 100만분 마다 풍선 하나를 만들고, 이를 100만 개 불어야 하면.... 1조가 정답이다!) 

2. 계획 (5분) - 1분

문제를 이해한 대로 이분탐색을 통해 풀이할 계획을 세웠습니다.

이분 탐색에선 초기값을 잡는 것이 중요한데, 정답의 최댓값은 가장 빨리 풍선을 부는 스태프가 전부 부는 경우보다 작기 때문에 그 값을 최댓값으로 놓았습니다.

최솟값과 최댓값 사이의 중간값을 잡고, 이 값이 정답이 가능한 수인지를 확인합니다.

중간값을 각 스태프들이 풍선을 부는데 걸리는 시간으로 나누면 그 시간에 스태프들이 불 수 있는 풍선의 개수가 나오고 그 값을 전부 합치면 이 시간에 가능한 풍선의 개수가 나옵니다! 

풍선의 갯수를 주어진 M과 비교해서 크거나 같으면 정답이 중간값이거나 더 아래에 존재하므로 이분 탐색의 최댓값을 중간값으로 바꾸고 풍선이 부족하면 중간값 위에 정답이 존재하므로 최솟값을 중간값으로 바꿔줍니다.

3. 검증 (5분) - 3분

이분탐색 문제는 기본적으로 정답의 범위가 크기 때문에 오버플로우가 자주 발생합니다.

본 문제에서도 int의 범위는 넘을것이 딱 보였기 때문에 문제 전체에서 long을 사용하기로 했습니다.

(JAVA 언어의 long은 C, C++ 등의 longlong과 같습니다.)

4. 풀이 (30분) - 8분

이분탐색 코드는 생각해내기가 어렵지 코드량과 작성 자체는 어렵지 않기 때문에 금방 작성을 마쳤습니다.

하지만 이분탐색의 마수가 또다시 저를 괴롭히니...

5. 채점, 디버깅 (+20분)

여러 번의 오답을 맞으면서 디버깅 시간이 길어졌습니다.

문제 풀이의 접근과 코드의 논리에는 문제가 없으나, 이분 탐색의 양 극단의 값 중에서 정답을 고르는 부분에 문제가 있어 예외가 발생하는 것 같았습니다. (테스트 케이스 62%쯤에서 오답 처리되었습니다.)

검색을 통해 유익한 글을 찾아... 이분 탐색을 다시 이해하고 코드를 제출해 통과했습니다.

핵심 로직은 건드린 게 없으니, 예상대로 정답을 고르는 부분에서 문제가 있었던 것 같습니다.

https://www.acmicpc.net/blog/view/109

상당히 유익한 글이고 이분 탐색 문제 풀이에서 발생하는 오답을 잡아주기 때문에 저와 비슷한 어려움을 겪으시는 분들은 꼭 읽어보시길 추천드립니다.

구현은 쉽지만 오류 찾기가 어려운 이분 탐색 문제였습니다. 감사합니다!

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

public class Main {
	static StringTokenizer st;

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

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

		st = new StringTokenizer(br.readLine());
		long min = Integer.MAX_VALUE;
		for (int n = 0; n < N; n++) {
			staffs[n] = Integer.parseInt(st.nextToken());
			min = Math.min(min, staffs[n]);
		}
		
		long left = 0;
		long right = min * M;
		
		while(left+1 < right) {
			long center = (left + right)/2;
			long balloon = 0;
			
			for (int n = 0; n < N; n++) {
				balloon += (center / staffs[n]);
			}
			
			if(balloon >= M) {
				right = center;
			}else {
				left = center;
			}
		}
		
		System.out.println(right);
	}
}

루틴에 맞춰 풀어본 첫 문제입니다.

몸풀기를 할 생각으로 실버 문제를 골랐는데... 너무 빨리 끝나서 생각처럼 잘 되진 않았습니다 ㅋㅋ

문제풀이 루틴에 관한 글은

https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

숭실대학교 교내 대회에서 사용된 문제입니다.

설명도 직관적이고 DP의 개념을 잡기 좋은 문제인 것 같습니다. 

제가 짜 놓은 루틴대로 문제를 풀어보도록 하겠습니다.

1. 이해 (5분) - 1분

설명이 워낙 간단명료한 터라 이해에는 긴 시간이 걸리지 않았습니다. 

캠퍼스를 산책하고 주어진 시간에 시작점인 정보과학관에 도착하는 경로가 몇 개인지 알아내면 됩니다.

2. 계획 (5분) - 1분

우선 문제의 캠퍼스는 생긴 것 부터 그래프와 유사합니다. 시간이 정해져 있고 경로의 개수를 찾는 것이니 BFS를 생각해 볼만도 하지만 10만 분이라는 시간 후에 무시무시하게 많은 경로를 고려하면 안 될 것 같습니다.

대신 우리는 경로의 갯수만을 구하면 되고, 경로를 알 필요는 없다는 점에 착안해서 DP를 사용해 간단하게 구현이 가능할 것 같습니다. 

비슷한 느낌의 DP 문제로는 https://www.acmicpc.net/problem/2579  [계단오르기 (실버 3)]가 있을 것 같네요.

DP가 진행되는 기준이 시간과 계단으로 다르고 이 문제 같은 경우는 순환이 가능하단 차이가 있지만... 느낌이 비슷하다고 봐주시면 될 것 같습니다. 

특정 시간에 8개의 건물에 위치하는 경로의 갯수를 각각 저장하도록 [입력받은 시간][8]의 2차원 배열을 선언해 앞 시간의 정보를 토대로 풀이해보겠습니다.

그림처럼 건물들에 번호를 매기고

처음 시간 D=0일때 가능한 경로는 0번 건물이 1

D=1일 때 가능한 경로는 1,2번 건물이 각각 1

... 이런식으로 진행해나가려고 합니다.

3. 검증 (5분) - 1분

시간의 최대치는 10만, 제 계획에선 시간 1 당 8번의 덧셈 연산만 진행되면 되니 주어진 시간 1 초안에 무난하게 통과할 것 같습니다. (시간제한 1초를 대략 1억 번의 연산으로 생각하면 됩니다.)

문제에선 정답을 10억7로 나눈 나머지를 출력하라고 했는데, 풀이 도중에 int의 크기를 넘어서는 오버플로우가 발생하기 때문입니다.

매 연산마다 나누기를 진행해주면 되지만, 제가 구상한 풀이에선 신양관, 한경직기념관이 각각 4개의 값이 더해집니다.

그럼 최대 40억의 값이 나오므로 오버플로우를 방지하기 위해 아예 long 타입으로 배열을 선언해줍시다.

주어지는 입력으로 가능한 최대 80만개의 long타입 배열이 있다면 long타입의 크기는 16Byte로 사용하는 메모리는 1280만 Byte입니다.

1MB가 약 100만 Byte이므로 12MB가량의 메모리가 필요하고, JVM을 감안해도 문제에서 주어진 512MB의 메모리 안에서 충분히 동작할 것 같습니다.

4. 풀이 (30분) - 8분

여기까지 구상한 내용으로 풀어봅니다!

코드를 작성 한 뒤 주어진 예제를 넣어 확인합니다.

입력의 최솟값인 1과 10만을 넣어 출력이 정상적으로 되는 것을 확인합니다.

(움직이지 않고 머무르는 것이 불가능하므로 입력이 1인 경우 0이 나오는 것이 당연합니다. 10만을 입력한 경우의 정답은 지금 상황에서 확신할 수 없으므로 에러가 발생하지 않는지만 확인했습니다. )

5. 채점, 디버깅 (+@)

다행히 한번에 정답으로 통과되었습니다. 

이 문제를 푸는데는 총 11분이 걸렸습니다. 

실버 1의 난이도면 코딩 테스트에서 1,2번의 앞 순위로 나오는 문제니 스타트로 나쁘지 않았습니다!

DP를 구상하고 정답이 자료형의 크기를 넘치는것만 주의하면 크게 어려울 것이 없는 문제였습니다.

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

public class Main {
	static final long div = 1_000_000_007;

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

		int D = Integer.parseInt(br.readLine());
		long[][] map = new long[D + 1][8];
		map[0][0] = 1;

		for (int d = 0; d < D; d++) {
			map[d + 1][0] = (map[d][1] + map[d][2]) % div;
			map[d + 1][1] = (map[d][0] + map[d][2] + map[d][3]) % div;
			map[d + 1][2] = (map[d][0] + map[d][1] + map[d][3] + map[d][5]) % div;
			map[d + 1][3] = (map[d][1] + map[d][2] + map[d][4] + map[d][5]) % div;
			map[d + 1][4] = (map[d][3] + map[d][5] + map[d][6]) % div;
			map[d + 1][5] = (map[d][2] + map[d][3] + map[d][4] + map[d][7]) % div;
			map[d + 1][6] = (map[d][4] + map[d][7]) % div;
			map[d + 1][7] = (map[d][5] + map[d][6]) % div;
		}

		System.out.println(map[D][0]);
	}
}

감사합니다!

표준 함수형 interface

Runnable

입력 X, 출력 X
입력도 출력도 없이 함수 내의 동작만 수행 가능하다.

ex)

void hello(){
    System.out.println("Hello World!");
}

Consummer

입력 O, 출력 X
입력은 있지만 출력이 존재하지 않는다.

ex)

void hello(String msg){
    System.out.println("msg: " + msg);
}

Operation

입력 O, 출력 입력과 같은 Type
입력을 받아 함수가 동작한 뒤 입력과 같은 타입을 return 한다.

ex)

int plus(int a, int b){
    return a+b;
}

Function

입력 O, 출력 anyType
입력의 타입과 상관 없이 return한다. 같은 타입을 return 해도 Function이다. (Operation < Function)

ex)

String plusOperation(int a, int b){
    StringBuilder answer = new StringBuilder();
    answer.append("answer is ").append(a+b);
    return answer.toString();
}

Supplier

입력 X, 출력 O
입력 없이 출력만 존재한다. 정해진 data등을 return 한다.

ex)

String[] getDayArr(){
    String[] dayArray = {"Sun","Mon","Tue","Wed","Thu","Fri","Sat"};
    return dayArray;
}

Predicate

입력 O, 출력 Boolean
입력에 따라 적절한 Boolean값을 return 한다.

ex)

Boolean isSmall(int a, int b){
    if(a < b){
        return true;
    }
    return false;
}

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

또 다른 웰 노운(Well Known인데 우리는 모르는) 알고리즘, 분리집합의 등장입니다. 

유니온이라고도 알려져 있습니다.

유니온은 일종의 단방향 트리라고 생각하셔도 될 것 같습니다.

데이터들을 집합들로 구분할때 어떻게 할 수 있을까요?

일일히 넘버링을 붙이거나 이름을 붙여도 되겠지만, 구현은 어떻게 하실건가요?

두개의 집합이 합쳐질때는요?

분리집합은 자신들을 대표하는 데이터를 부모로 가리킴으로서 자신이 속한 집합을 구분합니다.

이 데이터를 노드라고 생각한다면, 집합은 여러 노드들이 연결된 그래프가 되겠죠.

자신이 이미 속한 집합의 노드와 연결된다면 그 그래프는 사이클이 생긴 그래프가 됩니다.

간단하죠?

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

public class Main {
	static StringTokenizer st;
	static int[] parent;

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

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

		parent = new int[N];
		for (int n = 0; n < N; n++) {
			parent[n] = n;
		}

		for (int m = 1; m <= M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int aParent = findParent(a);
			int bParent = findParent(b);

			if (aParent == bParent) {
				answer = m;
				break;
			} else {
				parent[aParent] = bParent;
			}
		}

		System.out.println(answer);
	}

	static int findParent(int a) {
		if (parent[a] == a) {
			return a;
		} else {
			parent[a] = findParent(parent[a]);
			return parent[a];
		}
	}
}

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

또 다른 투 포인터 문제입니다. 

정확히는 슬라이딩 윈도라고 할 수 있겠네요. 

기본적인 투 포인터가 데이터의 양 쪽 끝에서 좁혀 들어오면서 탐색한다면, 슬라이딩 윈도는 한쪽 끝에서 시작해서 연속된 특정 범위를 찾습니다.

조금 더 상세히 설명해 볼까요?

N길이의 수열에서 연속된 부분을 구한다는 것은, 연속된 부분합의 시작점과 끝점을 정한다는 뜻입니다.

즉 N*N개의 경우가 존재한다는 뜻입니다.

슬라이딩 윈도우는 이 시작점과 끝점을 모든 경우에 대해 계산해보지 않고, 현재 부분에서 조건보다 작으면 연속된 부분을 늘리고 크면 연속된 부분을 줄이면서 진행합니다.

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

public class Main {
	static StringTokenizer st;

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

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

		int[] num = new int[N];

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

		int left = 0;
		int right = 1;
		int sum = num[0];
		int answer = 100_001;

		while (left < N) {
			if (sum >= S) {
				answer = Math.min(answer, right - left);
				sum -= num[left];
				left++;
			} else {
				if (right == N) {
					break;
				} else {
					sum += num[right];
					right++;
				}
			}
		}
		if(answer == 100_001) {
			System.out.println(0);
		}else {
			System.out.println(answer);
		}
	}
}

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

정석적인 투포인터 문제입니다.

투포인터 알고리즘에 대해선 나중에 포스팅을 작성해 보도록 하겠습니다.

투포인터 알고리즘을 통해 절댓값이 0에 가장 가까운 두개의 특성값을 기록하고 출력하면 간단히 풀립니다.

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

public class Main {
	static StringTokenizer st;

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

		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		int value = Integer.MAX_VALUE;
		int[] answer = new int[2];

		st = new StringTokenizer(br.readLine());

		for (int n = 0; n < N; n++) {
			num[n] = Integer.parseInt(st.nextToken());
		}

		int left = 0;
		int right = N - 1;

		while (left < right) {
			int sum = num[left] + num[right];
			int abs = Math.abs(sum);

			if (abs < value) {
				value = abs;
				answer[0] = num[left];
				answer[1] = num[right];
			}

			if (sum <= 0) {
				left++;
			} else {
				right--;
			}

		}
		System.out.println(answer[0] + " " + answer[1]);
	}
}