고양멍멍이

[문제링크]

1. 사용한 풍선은 표시해두고, 지나가더라도 카운트하지 않는다

2. 양 끝 간 이동 처리를 위해, 증감시 N으로 나머지 연산

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = pint(br.readLine());
		int[] num = new int[N];
		boolean[] chk = new boolean[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			num[i]=pint(st.nextToken());
		}
		
		int cur=0;
		sb.append(cur+1).append(" ");
		int move = num[cur];
		chk[cur]=true;
		for (int i = 1; i < N; i++) {
			int cnt=0;
			while(cnt<Math.abs(move)) {
				if(move>0) {
					cur++;
					cur%=N;
					if(chk[cur])continue;
				}
				else {
					cur--;
					cur+=N;
					cur%=N;
					if(chk[cur])continue;
				}
				cnt++;
			}
			sb.append(cur+1).append(" ");
			move = num[cur];
			chk[cur]=true;
		}System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 단순한 구현 문제

1. 4개의 대각선을 옮기는 작업을 한다

• 두 수를 swap하듯, 하나를 백업하고 후에 복구

2. -X 각도로의 회전은 360-X 각도의 회전과 같다

• 별도의 함수를 만들지 않고, 45도 회전 함수를 동일하게 사용

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

public class Main{
	static int[][] map;
	static int n,d;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = pint(st.nextToken());
			d = pint(st.nextToken())/45;
			if(d<0)d+=8;
			map=new int[n][n];
			
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			
			for (int i = 0; i < d; i++) {
				spin();
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					sb.append(map[i][j]).append(" ");
				}sb.append("\n");
			}
		}System.out.println(sb);
	}
	static void spin() {
		int[] backup = new int[n];
		for (int i = 0; i < n; i++)backup[i]=map[i][i];//백업
		
		for (int i = 0; i < n; i++)map[i][i]=map[n/2][i];
		for (int i = 0; i < n; i++)map[n/2][i]=map[n-i-1][i];
		for (int i = 0; i < n; i++)map[n-i-1][i]=map[n-i-1][n/2];
		for (int i = 0; i < n; i++)map[i][n/2]=backup[i];
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 방향 그래프에서, 가장 많은 노드를 방문할 수 있는 노드 찾기

1. 정점 N에 비해 간선 M의 범위가 작으므로, 그래프의 저장은 List로 한다

2. 모든 정점에 대해 BFS로 방문 가능한 노드 갯수를 탐색, 저장한다

3. 최댓값을 가지는 정점들을 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[] result = new int[n];
		int max=0;
		List<List<Integer>> graph = new ArrayList<>();
		
		for (int i = 0; i < n; i++)graph.add(new ArrayList<>());
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = pint(st.nextToken())-1;
			int b = pint(st.nextToken())-1;
			graph.get(b).add(a);
		}
		
		for (int i = 0; i < n; i++) {
			//각각 서치 돌려보고, 결과값 추리기
			int cnt=0;
			
			Queue<Integer>qu = new LinkedList<Integer>();
			qu.offer(i);
			boolean[] isV=new boolean[n];
			isV[i]=true;
			while(!qu.isEmpty()) {
				int cur = qu.poll();
				cnt++;
				for (int next : graph.get(cur)) {
					if(!isV[next]) {
						isV[next]=true;
						qu.offer(next);
					}
				}
			}
			result[i]=cnt;
			if(max<cnt)max=cnt;
		}
		for(int i=0; i<n; i++) {
			if(result[i]==max)sb.append(i+1).append(" ");
		}sb.setLength(sb.length()-1);
		System.out.println(sb);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 친구의 친구까지만 찾는 문제

1. BFS를 딱 두번만 돌린다

• 혹은 DFS를 깊이 2에서 종료한다 (깊이 1과 2를 공유하는 node에 유의하면서)

2. 방문한 노드의 수 = 초대할 사람의 수이다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int M = pint(br.readLine());
		ArrayList<ArrayList<Integer>>graph = new ArrayList<>();
		
		for (int i = 0; i < N; i++)graph.add(new ArrayList<>());
		boolean[]isV = new boolean[N];
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken())-1;
			int y = pint(st.nextToken())-1;
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		
		//1부터 시작해, 2번 안에 갈수있는 사람의 수 찾기
		int count=0; //몇번 건넌 친구인지 = 몇 번 돌았는지
		int friendCnt=0;
		Queue<Integer>qu = new LinkedList<Integer>();
		qu.offer(0); //초기 node = 자기 자신
		isV[0]=true;
		while(count<2) {
			int len =qu.size();
			for (int i = 0; i < len; i++) {
				int curNode = qu.poll();
				
				int graphLen = graph.get(curNode).size();
				for (int j = 0; j < graphLen; j++) {
					int nextNode = graph.get(curNode).get(j);
					if(!isV[nextNode]) {
						friendCnt++;
						isV[nextNode]=true;
						qu.offer(nextNode);
					}
				}
				
			}
			
			count++;
		}
		System.out.println(friendCnt);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. x와 y 슬라임으로, x+y 슬라임을 만들며, x*y 점수를 획득한다

1. N번째 합칠 슬라임의 무게가 y였다면, N+1, N+2...번째 연산에도 y가 포함되게 된다

2. 크기가 큰 슬라임을 빠르게 합쳐, 이후 연산들에 최대한 많이 포함되도록 해야 한다 (그리디)

3. 슬라임을 크기순으로 2개씩 꺼내며 합쳐나간다.

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		PriorityQueue<Integer>pq = new PriorityQueue<>();
		
		int N = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			pq.offer(pint(st.nextToken()));
		}
		
		int score = 0;
		while(pq.size()!=1) {
			int fst = pq.poll();
			int snd = pq.poll();
			score+=fst*snd;
			pq.offer(fst+snd);
			
		}
		
		System.out.println(score);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 수빈이의 이동 방법 3가지를 활용해, 동생에게 가장 빠르게 갈 수 있는 경우 찾기

  - 3개의 선택지가 있는 탐색 문제.

  - 어떤 선택지를 먼저 선택하느냐에 따라 해가 나오지 않거나 큰 해가 나오는 경우가 존재하므로 DFS가 아닌 BFS 사용

1. 수빈이의 시작지점 N에서 BFS방식으로 +1, -1, *2 지점을 큐에 넣으며 진행한다

2. 수빈이가 어떤 칸 X에 W초를 거쳐 도달했는데, 이미 해당 칸에 W보다 적은 시간으로 도달한 기록이 있다면, 더이상 탐색하는것은 의미가 없다.

  - BFS는 W초에서 갈수있는 모든 지점을 완료한 후 W+1초의 지점들에 대해 작업하므로, 값의 유/무로만 판단해도 무방하다

  - X번 노드에 도달했을 때의 이동 횟수를 num배열에 저장하여, 그 값이 없는 좌표에 대해서만 진행한다

3. 수빈이의 현재 위치가 동생의 위치보다 크다면, 반드시 작아져야하므로 +1 *2 연산을 진행할 필요 없다

  - 마찬가지로, 수빈이의 현재 위치가 동생의 위치보다 작다면, 반드시 커져야하므로 -1 연산을 진행할 필요 없다

4. 정리하자면,

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X+1 좌표에 진행해본적이 없을때 진행

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X*2 좌표에 진행해본적이 없을때 진행

  - 현재 좌표 X가 동생의 좌표 K보다 크며, X-1 좌표에 진행해본적이 없을때 진행하며,

  - K좌표에 도달하는 순간 연산 횟수를 출력, 종료한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int len=100001;
		int[] num = new int[len*2];
		num[N]=1;
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		
		while(num[K]==0) {
			int temp = q.poll();
			if(temp < K && num[temp+1]==0) {
				num[temp+1]=num[temp]+1;
				q.offer(temp+1);
			}
			if(temp-1 >= 0 && num[temp-1]==0) {
				num[temp-1]=num[temp]+1;
				q.offer(temp-1);
			}
			if(temp < K && num[temp*2]==0) {
				num[temp*2]=num[temp]+1;
				q.offer(temp*2);
			}
			
		}
		System.out.println(num[K]-1);
	}
}

[문제링크]

0. bufferedreader로 EOF 입력받는법 : null인지 아닌지 체크하기

1. 모든 수를 입력받아서 list로 저장

2. 전위순회의 결과물이므로 [루트] [왼쪽 서브트리] [오른쪽 서브트리] 의 형태로 나눌 수 있다.

3. 루트보다 커지는 지점이 오른쪽 서브트리의 시작점이므로, [왼쪽 서브트리] > [오른쪽 서브트리] > [루트] 의 순서로 재귀를 실행한다

4. 인자로 받은 서브트리가 1칸짜리면 그 원소를 list에 넣고 반환한다

  - 루트는 1칸짜리라 재귀 실행 = list에 자신 저장이므로 재귀 호출 대신 직접 넣는다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s;
		num = new ArrayList<>();
		back = new ArrayList<>();
		
		while((s=br.readLine())!=null) {
			num.add(pint(s));
		}
		
		rec(0,num.size()-1);
		
		for (int i = 0; i < back.size(); i++) {
			System.out.println(back.get(i));
		}
		
	}
	static ArrayList<Integer>num;
	static ArrayList<Integer>back;
	
	static void rec(int s, int e) {
		if(s==e) {
			back.add(num.get(s));
			return;
		}
		
		int root = num.get(s);
		int cnt=s+1;
		while(cnt<=e && num.get(cnt)<root)cnt++;
		
		if(s+1<=cnt-1)rec(s+1, cnt-1);
		if(cnt<=e)rec(cnt,e);
		back.add(root);
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 블록의 길이는 n*m이며 블록 중간에는 상점도 길도 없으므로 한바퀴 도는 경로를 n+m+n+m크기의 1차원 배열로 관리할 수 있다

1. 북쪽 > 동쪽 > 남쪽 > 서쪽 순서의 경로를 가정하고, 입력받은 상점의 위치를 가공해 저장한다

2. 마지막에 시작점을 입력받고, 배열을 한바퀴 순회(배열의 범위를 넘어가면 0으로 초기화)하며 거리를 누적한다

  - 거리는 정방향(i)과 역방향(totalLen - i) 중 짧은쪽을 누적한다

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		int[] map = new int[(n+m)*2];
		int store = pint(br.readLine());
		int pos=0;
		int totalCost=0; //최소 코스트 
		int totalLen = (n+m)*2; // 상점가 블록 전체의 갯수
		
		for (int i = 0; i <= store; i++) {
			int temp=0;
			st = new StringTokenizer(br.readLine());
			switch (st.nextToken()) {
			case "1"://북쪽
				temp=pint(st.nextToken());break;
			case "2"://남쪽
				temp=n+m+n-pint(st.nextToken());break;
			case "3"://서쪽
				temp=(n+m)*2-pint(st.nextToken());break;
			case "4"://동쪽
				temp=n+pint(st.nextToken());break;
			default: break;
			}
			if(i==store)pos=temp; // 마지막 입력은 시작 위치
			map[temp]=1;
		}
		for (int i = 1; i < totalLen; i++) {
			if(pos+i==totalLen)pos=-i;
			if(map[pos+i]==1) {
				totalCost+=Math.min(i, totalLen-i);
			}
		}System.out.println(totalCost);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}