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

비기너

문제

9933번: 민균이의 비밀번호

# 문자열

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

풀이

문자열 배열에서 문자열 두 개를 뽑아서 하나를 뒤집었을 때 다른 문자열과 뒤집은 문자열이 같다면 그것이 비밀번호가 된다.

자기 자신을 뒤집어 다시 자기 자신이 되어도 된다.

참고

문자열 뒤집기

String s;
StringBuffer sb = new StringBuffer(s);
String reverse = sb.reverse().toString();

코드

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());
		String[] a = new String[n];
		for (int i = 0; i < n; i++)
			a[i] = br.readLine();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				StringBuffer st = new StringBuffer(a[i]);
				String tmp = st.reverse().toString();
				if (tmp.equals(a[j])) {
					bw.write(a[i].length() + " ");
					bw.write(a[i].charAt(a[i].length() / 2));
					bw.flush();
					bw.close();
					return;
				}
			}
		}
	}
}

미들러

문제

7562번: 나이트의 이동

# bfs

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

풀이

이차원 맵에서 최단 거리를 구하는 문제이다.

bfs를 이용하면 최단 거리를 구할 수 있다.

나이트가 이동하는 8방향을 dy, dx 배열에 저장한다.

참고

https://ward.tistory.com/193

그래프 탐색

코드

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

class Node {
	int y, x;

	public Node(int y, int x) {
		this.y = y;
		this.x = x;
	}
}

public class Main {
	static int n;
	static int[][] visited;
	static int[] dy = { -2, -1, 1, 2, 2, 1, -1, -2 };
	static int[] dx = { 1, 2, 2, 1, -1, -2, -2, -1 };

	static void bfs(int y, int x) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(y, x));
		visited[y][x] = 1;

		while (!q.isEmpty()) {
			Node node = q.poll();
			y = node.y;
			x = node.x;

			for (int i = 0; i < 8; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= n || nx >= n)
					continue;
				if (visited[ny][nx] >= 1)
					continue;
				q.add(new Node(ny, nx));
				visited[ny][nx] = visited[y][x] + 1;
			}
		}
	}

	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 t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int sy = Integer.parseInt(st.nextToken());
			int sx = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			int ey = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());

			visited = new int[n][n];
			bfs(sy, sx);
			
			bw.write((visited[ey][ex] - 1) + "\n");
		}

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

챌린저

문제

다단계 칫솔 판매

# 맵

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

프로그래머스

풀이

판매원이 트리구조를 이루고 있는데 각 판매원이 수익 배분을 마친 뒤 가져가는 수익을 구하는 문제이다.

모든 배열들이 문자열로 이루어져 있는데 문자열로 이루어진 배열을 숫자로 표현하기 위해 맵을 사용한다.

트리 구조이므로 referral 배열을 순회하며 parent 배열에 부모 노드의 번호를 저장한다.

부모가 센터("-")인 경우 -1을 저장한다.

seller 요소마다 반복문을 통해 수익을 부모와 나눈다.

수익 배분이 중단되는 경우는 두 가지가 있는데 수익이 10 미만이거나 센터노드에 도달했을 때이다.

코드

import java.util.*;
class Solution {    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        HashMap<String, Integer> mp = new HashMap<>();
        int parent[] = new int[enroll.length];
        
        for (int i = 0; i < enroll.length; i++) {
            mp.put(enroll[i], i);
            if (referral[i].equals("-"))
                parent[i] = -1;
            else 
                parent[i] = mp.get(referral[i]);
        }
        
        int[] ans = new int[enroll.length];
        for (int i = 0; i < seller.length; i++) {
            int tmp = amount[i] * 100;
            int x = mp.get(seller[i]);
            while (true) {
                if (x == -1)
                    break;
                if (tmp >= 10) {
                    ans[x] += tmp - (tmp / 10);
                    tmp /= 10;
                    x = parent[x];
                }
                else {
                    ans[x] += tmp;
                    break;
                }
            }
        }
        
        return ans;
    }
}