99클럽 코테 스터디 11일차 TIL

비기너

문제

완주하지 못한 선수

# 해시

https://school.programmers.co.kr/learn/courses/30/lessons/42576

풀이1

완주하지 못한 선수가 단 한 명이므로 전체 선수와 완주자 배열을 정렬한 뒤에 하나씩 차례대로 비교하다가 같지 않은 선수가 나오면 해당 선수가 완주하지 못한 선수이다.

코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for (int i = 0; i < completion.length;i++) {
            if (!participant[i].equals(completion[i]))
                return participant[i];
        }
        
        return participant[participant.length - 1];
    }
}

미들러

문제

25195번: Yes or yes

# dfs

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

풀이

방향 그래프를 탐색하는데 곰곰이가 없는 노드로만 이동할 수 있는지 체크하는 문제이다.

dfs를 통해 그래프를 탐색하는데 곰곰이가 있는 노드를 방문하면 바로 리턴한다.

dfs를 진행하다가 더 이상 이동할 수 없으면 곰곰이를 만나지 않고 가는 경로를 찾은 것이므로 static 변수 flag를 true로 세팅하고 리턴한다.

사이클이 없는 방향 그래프이므로 방문 처리를 따로 하지 않아도 dfs가 돌아간다.

분명 풀이는 맞는거 같은데 안돼서 10분동안 고민했는데 dfs를 짜놓고 dfs를 돌리지 않고 정답을 출력하고 있었다.

dfs 없아 dfs문제를 풀고 있었다 ㅠㅠ

참고

https://ward.tistory.com/193

그래프 탐색

코드

import java.util.*;
import java.io.*;

public class Main {
	static boolean[] gom;
	static boolean flag;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

	static void dfs(int x) {
		if (gom[x] || flag)
			return;
		if (adj.get(x).size() == 0) {
			flag = true;
			return;
		}
		for (int nx : adj.get(x))
			dfs(nx);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
		}

		int s = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		gom = new boolean[n + 1];
		while (s-- > 0)
			gom[Integer.parseInt(st.nextToken())] = true;

		dfs(1);
		if (flag)
			bw.write("yes");
		else
			bw.write("Yes");

		bw.flush();
		bw.close();
	}
}

챌린저

문제

1461번: 도서관

# 그리디

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

풀이

0의 위치에 있는 책을 제자리에 갔다 놓을 때 드는 최소 걸음 수를 구하는 문제이다.

책은 한 번에 m개까지 옮길 수 있고 책을 모두 제자리에 놓은 뒤에는 0으로 돌아오지 않아도 된다.

위치가 음수인 책과 양수인 책은 책을 가져다 놓기 위해서는 0을 통과해야 하므로 둘을 나누어서 생각한다.

그 다음에 생각해 볼만한 점은 거리가 먼 책부터 가져다 놓는 것이 좋은가 가까운 책부터 가져다 놓는 것이 좋은가인데 예제를 살펴본 결과 거리가 먼 책부터 가져다 놓는 것이 해답을 도출하였다.

우선순위 큐를 사용해서 거리 순으로 책을 뽑아내기 편리하게 하였다.

주의할 점은 가장 먼 책을 가져다 놓는 것은 가장 마지막에 해서 다시 0으로 돌아올 필요가 없게 하는 것이 최소 걸음을 걷는 방법이라는 것이다. 

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		PriorityQueue<Integer> pq1 = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			int tmp = Integer.parseInt(st.nextToken());
			if (tmp > 0)
				pq1.add(tmp);
			else
				pq2.add(tmp * -1);
		}

		int tmp = 0;
		if (pq1.isEmpty())
			tmp = pq2.peek();
		else if (pq2.isEmpty())
			tmp = pq1.peek();
		else
			tmp = Math.max(pq1.peek(), pq2.peek());

		int ans = 0;
		while (!pq1.isEmpty()) {
			ans += pq1.poll() * 2;
			for (int i = 0; i < m - 1; i++) {
				if (pq1.isEmpty())
					break;
				pq1.poll();
			}
		}

		while (!pq2.isEmpty()) {
			ans += pq2.poll() * 2;
			for (int i = 0; i < m - 1; i++) {
				if (pq2.isEmpty())
					break;
				pq2.poll();
			}
		}

		ans -= tmp;
		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

보너스문제

비기너

문제

7785번: 회사에 있는 사람

# 해시

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

풀이

셋을 이용해서 회사에 들어온 사람을 저장한다.

회사를 나간 사람은 셋에서 제거한다.

셋의 전체 요소를 배열로 변환한 뒤 내림차순으로 정렬하여 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		HashSet<String> s = new HashSet<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String a = st.nextToken();
			String b = st.nextToken();
			if (b.equals("enter"))
				s.add(a);
			else
				s.remove(a);
		}

		String[] ans = s.toArray(new String[0]);
		Arrays.sort(ans, Comparator.reverseOrder());
		for (String i : ans)
			bw.write(i + "\n");

		bw.flush();
		bw.close();
	}
}

미들러

문제

2573번: 빙산

# dfs

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

풀이

시간이 지남에 따라 물과 인접한 빙하가 녹는다.

빙하가 녹는 과정에서 빙하가 두 덩어리로 분리되는 최초의 시간을 구하는 문제이다.

매 턴마다 빙하가 녹는 것을 구현하고 빙하가 분리되었는지 dfs를 통해서 확인하면 되는 문제이다.

만약 빙하가 다 녹아서 없다면 0을 출력해야 한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m;
	static int[][] a;
	static boolean[][] visited;
	static int[] dy = { 1, -1, 0, 0 };
	static int[] dx = { 0, 0, 1, -1 };

	static void dfs(int y, int x) {
		visited[y][x] = true;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= m)
				continue;
			if (visited[ny][nx] || a[ny][nx] == 0)
				continue;
			dfs(ny, nx);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		a = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++)
				a[i][j] = Integer.parseInt(st.nextToken());
		}

		int ans = 0;
		while (true) {
			ans++;

			int tmp[][] = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (a[i][j] > 0) {
						for (int k = 0; k < 4; k++) {
							int ny = i + dy[k];
							int nx = j + dx[k];
							if (a[ny][nx] == 0)
								tmp[i][j]++;
						}
					}
				}
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++)
					a[i][j] = Math.max(0, a[i][j] - tmp[i][j]);
			}

			int cnt = 0;
			visited = new boolean[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (a[i][j] > 0 && !visited[i][j]) {
						dfs(i, j);
						cnt++;
					}
				}
			}

			if (cnt == 0) {
				bw.write("0");
				bw.flush();
				bw.close();
				return;
			} else if (cnt >= 2)
				break;
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

자물쇠와 열쇠

# 완전 탐색

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

풀이

자물쇠 배열과 열쇠 배열이 주어진다.

열쇠와 자물쇠를 맞춰서 자물쇠를 열 수 있는지를 구하는 문제이다.

자물쇠와 열쇠의 크기가 20이기 때문에 완전 탐색으로 풀 수 있는 문제이다.

열쇠를 (-m, -m)에서부터 (n, n)까지 이동시키면서 자물쇠를 완벽하게 채울 수 있는지 확인한다.

열쇠는 90도씩 회전이 가능하므로 해당 내용도 구현해야 한다.

자물쇠를 채우는 코드를 작성하는 과정에서 자물쇠 원본 배열을 수정하고 복원을 하지 않아 오답이 발생하였다.

조심해야겠다.

코드

class Solution {
    int n, m;
    
    int[][] rotate(int[][] key) {
        int[][] tmp = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                tmp[i][j] = key[m - j - 1][i];
            }
        }
        return tmp;
    }
    
    boolean check(int y, int x, int[][] key, int[][] lock) {
        int[][] tmp = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++)
                tmp[i][j] = lock[i][j];
        }
        
        for (int i = 0; i < m; i++) {
            for(int j = 0; j < m; j++) {
                if (i + y >= n || j + x >= n || i + y < 0 || j + x < 0)
                    continue;
                if (lock[i + y][j + x] == 1 && key[i][j] == 1)
                    return false;
                if (lock[i + y][j + x] == 0 && key[i][j] == 1)
                    tmp[i + y][j + x] = 1;                    
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                if (tmp[i][j] == 0)
                    return false;   
        }
        
        return true;
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        n = lock.length;
        m = key.length;
         
        for (int i = -m; i < n; i++) {
            for (int j = -m; j < n; j++)                   
                for (int k = 0; k < 4; k++) {
                    key = rotate(key);
                    if (check(i, j, key, lock))
                        return true;
                }
        }
        
        return false;
    }
}