고양멍멍이

[문제링크]

0. j ~ j+i 까지의 수가 팰린드롬 수가 되려면

  - j, j+1번 자리의 수가 같아야하며

  - j+1 ~ j+i-1 까지의 수가 팰린드롬 수여야 한다

1. 1, 2자리 수에 대해 팰린드롬 수 여부를 계산한다

  - 1자리의 수는 전부 다 팰린드롬 수

  - 두 자리의 수가 연속이라면 팰린드롬 수

2. isP[x][y] 배열은 y번째 수부터, x개의 수를 고려했을때 해당 수가 팰린드롬인지 여부를 판단한다

  - isP[10][5] - 5~14의 수가 팰린드롬인지 정보 저장

3. 3자리부터 n자리까지 모든 가능한 경우에 대해 팰린드롬 수 여부를 검사한다

  - isP[i-2][j+1] : j+1 ~ j+i-1까지의 팰린드롬 여부

4. m개의 입력을 처리하며, 미리 구성된 isP 정보에 따라 1/0 출력 결정

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			num[i]=pint(st.nextToken());
		}
		//2.
		boolean[][]isP = new boolean[N][N];
        
		//1.
		Arrays.fill(isP[0], true);
		for (int i = 0; i < N-1; i++) {
			if(num[i]==num[i+1])isP[1][i]=true;
		}
        
		//3.
		for (int i = 2; i < N; i++) {
			for (int j = 0; j < N-i; j++) {
				if(num[j]==num[j+i]) {
					if(isP[i-2][j+1]) {
						isP[i][j]=true;
					}
				}
			}
		}
        
		//4.
		int m = pint(br.readLine());
		for (int i = 0; i < m; i++) {
			st=new StringTokenizer(br.readLine());
			int s = pint(st.nextToken()), e=pint(st.nextToken());
			sb.append(isP[e-s][s-1]?1:0).append("\n");
		}
		System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. A칸에서 이동해 B칸으로 갈 경우, A와 B는 같은 집합에 속한다

  - 이러한 이동-집합에 대해, 각 집합당 1개의 SAFE-ZONE이 필요하게 된다

  - disjoint-set으로 집합 관리

1. n*m개의 각 칸을 set으로 만들고, set의 갯수 또한 n*m으로 초기화한다

2. 모든 칸을 순회하며 각 칸의 이동에 따라 도착지점의 set과 결합한다

3. 최종적으로 남아있는 set의 갯수가 필요한 SAFE-ZONE의 수가 된다

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(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
        
		init();
		
		for (int i = 0; i < n; i++) {
			String s =br.readLine();
			for (int j = 0; j < m; j++) {
				switch(s.charAt(j)) {
				case 'U':
					union(i*m+j, (i-1)*m+j);
					break;
				case 'D':
					union(i*m+j, (i+1)*m+j);
					break;
				case 'L':
					union(i*m+j, i*m+j-1);
					break;
				case 'R':
					union(i*m+j, i*m+j+1);
					break;
				default:
					break;
				}
			}
		}
		
		System.out.println(cntSet);
		
	}
	static int n,m;
	static int[][]parent;
	static int cntSet;
	
	static void init() {
		parent = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				parent[i][j]=m*i+j;
			}
		}
		cntSet=n*m;
	}
	
	static int find(int x) {
		if(parent[x/m][x%m]!=x)return parent[x/m][x%m]=find(parent[x/m][x%m]);
		return x;
	}
	
	static void union(int x, int y) {
		int rx = find(x), ry=find(y);
		if(rx!=ry) {
			parent[rx/m][rx%m]=ry;
			cntSet--;
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. treeNode 자료구조는 부모 index, 자기 value, 자식 index의 List로 구성됨

  - treeNode의 배열로서 tree를 표현한다

1. 문제의 입력은 0-base지만, 편의상 1-base로 변경. 0은 가상의 head node로서 사용한다

2. 입력을 받으며 자신의 parent에 등록 + parent의 child에 등록해 tree 완성

3. 0번을 parent로 가지는, tree의 root노드로부터 bfs 탐색한다

  - child가 없는 node는 leaf이므로 센다

4. 탐색 노드가 삭제할 node일 경우, 해당 노드로부턴 더 이상 탐색하지 않는다

  - 삭제 node의 parent의 child 갯수가 1개라면 : 이 node의 삭제로 parent노드가 leaf가 되었으니 센다

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 root=0, deadNode=0, cntLeaf=0;
		int N = pint(br.readLine());
		treeNode[]tree = new treeNode[N+1];
		for (int i = 0; i <= N; i++) {
			tree[i]=new treeNode();
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			int p = pint(st.nextToken())+1;
			tree[i].parents=p;
			tree[i].value=i;
			tree[p].children.add(i);
			if(p==0)root=i;
		}
		deadNode=pint(br.readLine())+1;
		
		Queue<Integer>qu = new LinkedList<>();
		qu.offer(root);
		cntLeaf=0;
		while(!qu.isEmpty()) {
			int node=qu.poll();
			if(tree[node].value==deadNode) {
				if(tree[node].parents!=0 && tree[ tree[node].parents ].children.size()==1) {
					cntLeaf++;
				}
				continue;
			}
			
			if(tree[node].children.isEmpty()) {
				cntLeaf++;
			}
			else {
				for (int i = 0; i < tree[node].children.size(); i++) {
					int next=tree[node].children.get(i);
					qu.offer(next);
				}
			}
		}
		System.out.println(cntLeaf);
	}
	static class treeNode{
		int parents;
		int value;
		ArrayList<Integer>children=new ArrayList<>();
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 사방 처리를 위해 외곽을 1로 감쌌다

1. 전체를 탐색하면서 0, 빈공간을 만날 경우 BFS 진행

  - BFS에서 거쳐가는 모든 칸을 index로 칠해 재탐색 방지 + 추후 이용

  - BFS의 결과로 반환된 size를 ArrayList에 저장한다

  - ( 0은 빈칸, 1은 벽이므로 area index는 2부터 시작, index 유지를 위해 0 2개 삽입)

2. 전체를 탐색하면서 벽을 만날 경우 4방향에 대해

  - 1이 아니면 빈 공간이 index로 칠해진 것. 해당 index의 size를 ArrayList로부터 가져와 누적한다.

  - 1이면 벽, 무시한다

3. 각 방향의 area index가 같다면, 두번 더해선 안된다.

  - 4개의 값이므로, 각각 이전 값들과 다를 경우에만 누적한다 ( 가독성, 확장성은 좋지 않지만, 성능 효율적 )

  - set에 다 던져넣고 하나씩 꺼내며 쓴다 ( 가독성, 확장성은 좋지만, 성능 비효율적)

4. 출력할 때 println등을 이용하면 최악 1000*1000번 출력하게되므로, buffer 이용이 필수적이다

+ 4번 print구간은 3번 반복문에 그대로 삽입할 수 있다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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());
		
		map=new int[n+2][m+2];
		int[][]ansMap=new int[n+2][m+2];
		//외곽 padding
		for (int i = 0; i < n+2; i++) {
			map[i][0]=1;map[i][m+1]=1;
		}
		for (int i = 0; i < m+2; i++) {
			map[0][i]=1;map[n+1][i]=1;
		}
		// 1. input
		for (int i = 1; i <= n; i++) {
			String s = br.readLine();
			for (int j = 1; j <= m; j++) {
				map[i][j]=s.charAt(j-1)-'0';
			}
		}
		//2. get size by bfs for each area + tagging
		ArrayList<Integer>area=new ArrayList<>();
		area.add(0);area.add(0);
		int idx=2;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(map[i][j]==0) {
					int size=search(idx++, i, j);
					area.add(size);
				}
			}
		}
		//3. check four-dir of each wall + add if area
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(map[i][j]==1) {
					ansMap[i][j]+=1;
					if(map[i+1][j]!=1)
						ansMap[i][j]+=area.get(map[i+1][j]);
					if(map[i][j+1]!=1 && map[i+1][j]!=map[i][j+1])
						ansMap[i][j]+=area.get(map[i][j+1]);
					if(map[i-1][j]!=1&& map[i+1][j]!=map[i-1][j] && map[i-1][j]!=map[i][j+1])
						ansMap[i][j]+=area.get(map[i-1][j]);
					if(map[i][j-1]!=1 && map[i][j-1]!=map[i+1][j]&& map[i][j-1]!=map[i][j+1] && map[i][j-1]!=map[i-1][j])
						ansMap[i][j]+=area.get(map[i][j-1]);
				}
			}
		}
		//4.print
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < m+1; j++)sb.append(ansMap[i][j]%10);
			sb.append("\n");
		}System.out.println(sb);
	}
	static int[][]map;
	static int search(int idx, int x, int y) {
		int size=1;
		map[x][y]=idx;
		if(map[x+1][y]==0)size+=search(idx,x+1,y);
		if(map[x-1][y]==0)size+=search(idx,x-1,y);
		if(map[x][y+1]==0)size+=search(idx,x,y+1);
		if(map[x][y-1]==0)size+=search(idx,x,y-1);
		return size;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. disjoint set 문제

1. A에서 B로 선분을 그으려 할 때, 이미 A와 B가 같은 집합에 속한다면 사이클이 생성된다

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());
		
		init(n);
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken());
			int y = pint(st.nextToken());
			if(!union(x,y)) {
				System.out.println(i+1);
				break;
			}
			else if(i==m-1) {
				System.out.println(0);
			}
		}
		
	}
	static int[] parents;
	
	static void init(int n) {
		parents=new int[n];
		for (int i = 0; i < n; i++) {
			parents[i]=i;
		}
	}
	
	static int find(int n) {
		if(parents[n]!=n)return parents[n]=find(parents[n]);
		return n;
	}
	
	static boolean union(int x, int y) {
		int px=find(x), py=find(y);
		if(px==py)return false;
		
		parents[px]=py;
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 알파벳은 26자이므로, 32bit int를 사용해 bit-masking으로 등장 정보를 저장한다

1. chk변수에는 모든 알파벳 정보를 저장해, 등장하는 알파벳들에 대해서만 검사하도록 한다

2. a,n,t,i,c 5자는 반드시 등장하므로, 기본적으로 지워두고 시작한다

3. m이 5보다 작으면, 위 5자를 지울수 없으므로 즉시 실패, 아니라면 남은 알파벳의 모든 조합을 구한다

4. 모든 가능한 조합에 대해 알파벳을 지워보면, 모든 알파벳이 가르쳐진 단어는 그 값이 0이된다

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

public class Main{
	
	static int n,m,chk,max;
	static int[]word;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
		word = new int[n];
		//기본으로 지워줘야하는 단어들
		int[]base=new int[] { 1<<'a'-'a', 1<<'n'-'a', 1<<'t'-'a', 1<<'i'-'a', 1<<'c'-'a'};
		
		//bit로 저장
		chk=0;
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < s.length(); j++) {
				word[i] = word[i] | 1<<(s.charAt(j)-'a');
				chk=chk | 1<<(s.charAt(j)-'a');
			}
		}
		
		//기본 5개 삭제
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 5; j++) {
				word[i] = word[i] & ~base[j];
				chk = chk & ~base[j];
			}
		}
		m-=5;
		
		max=0;
		if(m>=0)combi(0,0);
		System.out.println(max);
	}
	
	static void combi(int cnt, int prev) {
		if(cnt>=m || chk==0) {
        	//n개의 단어를 다 가르쳤을때
			int readCnt=0;
			for (int i = 0; i < n; i++) {
				if(word[i]==0)readCnt++;
			}
			max=Math.max(max, readCnt);
			return;
		}
		int[]temp = word.clone();
		int tempchk=chk;
		
		for (int i = prev; i < 26; i++) {
			if( (chk & 1<<i) != 0 ) {
				word=temp.clone();
				chk=tempchk;
				
				chk = chk & (~(1<<i));
				for (int j = 0; j < n; j++) {
					word[j] = word[j] & (~(1<<i));
				}

				combi(cnt+1, i+1);
			}
		}
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 구현문제.. 구현한다...

1. 왼쪽으로 회전 = 오른쪽으로 회전 3번과 같다

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[]color=new char[] {'w','g','r','b','o','y'};
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			//주사위 만들기
			cube=new char[6][3][3];
			
			for (int i = 0; i < 6; i++) {
				for (int j = 0; j < 3; j++) {
					Arrays.fill(cube[i][j], color[i]);
					
				}
			}
			int N = pint(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for (int i = 0; i < N; i++) {
				String oper = st.nextToken();
				//1:시계, 0:반시계
				int dir = oper.charAt(1)=='+'?1:0;
				
				switch (oper.charAt(0)) {
				case 'U':
					rotate_0();
					if(dir==0) {
						rotate_0();
						rotate_0();
					}
					break;
				case 'L':
					rotate_1();
					if(dir==0) {
						rotate_1();
						rotate_1();
					}
					break;
				case 'F':
					rotate_2();
					if(dir==0) {
						rotate_2();
						rotate_2();
					}
					break;
				case 'R':
					rotate_3();
					if(dir==0) {
						rotate_3();
						rotate_3();
					}
					break;
				case 'B':
					rotate_4();
					if(dir==0) {
						rotate_4();
						rotate_4();
					}
					break;
				case 'D':
					rotate_5();
					if(dir==0) {
						rotate_5();
						rotate_5();
					}
					break;
				default:
					break;
				}
				
				
			}//end of oper

			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					System.out.print(cube[0][i][j]);
				}
				System.out.println();
			}
		}//end of tc
		
	}
	static char[][][]cube;
	static int[][]pos = new int[][] {
		{0,0},{0,1},{0,2},{1,2},{2,2},{2,1},{2,0},{1,0}
	}; 
	static void rotate(int n) {
		//자기 판 회전
		char[] backup=new char[] {cube[n][0][0],cube[n][0][1]};
		for (int i = 7; i >=0; i--) {
			cube[n][ pos[(i+2)%8][0] ][ pos[(i+2)%8][1] ] =
					cube[n][ pos[i][0] ][ pos[i][1] ];
		}
		cube[n][0][2]=backup[0];
		cube[n][1][2]=backup[1];
	}
	
	static void rotate_0() {
		//1234 다 위쪽
		rotate(0);
		char[]backup=cube[1][0].clone();
		//4개의 주변 판 회전
		cube[1][0]=cube[2][0].clone();
		cube[2][0]=cube[3][0].clone();
		cube[3][0]=cube[4][0].clone();
		cube[4][0]=backup.clone();
	}
	
	static void rotate_1() {
		//0왼 2왼 5왼 4오
		rotate(1);
		char[]backup=new char[] {cube[0][0][0],cube[0][1][0],cube[0][2][0]};
		//2->5->4->0
		cube[0][0][0]=cube[4][2][2];
		cube[0][1][0]=cube[4][1][2];
		cube[0][2][0]=cube[4][0][2];
		
		cube[4][2][2]=cube[5][0][0];
		cube[4][1][2]=cube[5][1][0];
		cube[4][0][2]=cube[5][2][0];
		
		cube[5][0][0]=cube[2][0][0];
		cube[5][1][0]=cube[2][1][0];
		cube[5][2][0]=cube[2][2][0];
		
		cube[2][0][0]=backup[0];
		cube[2][1][0]=backup[1];
		cube[2][2][0]=backup[2];

	}
	static void rotate_2() {
		//0아 3왼 5위 1오
		rotate(2);
		char[]backup=new char[] {cube[0][2][0],cube[0][2][1],cube[0][2][2]};
		//3-5-1-0
		cube[0][2][0]=cube[1][2][2];
		cube[0][2][1]=cube[1][1][2];
		cube[0][2][2]=cube[1][0][2];
		
		cube[1][0][2]=cube[5][0][0];
		cube[1][1][2]=cube[5][0][1];
		cube[1][2][2]=cube[5][0][2];
		
		cube[5][0][0]=cube[3][2][0];
		cube[5][0][1]=cube[3][1][0];
		cube[5][0][2]=cube[3][0][0];
		
		cube[3][2][0]=backup[2];
		cube[3][1][0]=backup[1];
		cube[3][0][0]=backup[0];
	}
	static void rotate_3() {
		//0오 5왼 6오 3오
		rotate(3);
		char[]backup=new char[] {cube[0][0][2],cube[0][1][2],cube[0][2][2]};
		//4-5-2-0
		cube[0][0][2]=cube[2][0][2];
		cube[0][1][2]=cube[2][1][2];
		cube[0][2][2]=cube[2][2][2];

		cube[2][0][2]=cube[5][0][2];
		cube[2][1][2]=cube[5][1][2];
		cube[2][2][2]=cube[5][2][2];

		cube[5][0][2]=cube[4][2][0];
		cube[5][1][2]=cube[4][1][0];
		cube[5][2][2]=cube[4][0][0];
		
		cube[4][2][0]=backup[0];
		cube[4][1][0]=backup[1];
		cube[4][0][0]=backup[2];
	}
	static void rotate_4() {
		//1위 2왼 6아 4오
		rotate(4);
		char[]backup=new char[] {cube[0][0][0],cube[0][0][1],cube[0][0][2]};
		//1-5-3-0
		cube[0][0][0]=cube[3][0][2];
		cube[0][0][1]=cube[3][1][2];
		cube[0][0][2]=cube[3][2][2];
		
		cube[3][0][2]=cube[5][2][2];
		cube[3][1][2]=cube[5][2][1];
		cube[3][2][2]=cube[5][2][0];
		
		cube[5][2][2]=cube[1][2][0];
		cube[5][2][1]=cube[1][1][0];
		cube[5][2][0]=cube[1][0][0];
		
		cube[1][2][0]=backup[0];
		cube[1][1][0]=backup[1];
		cube[1][0][0]=backup[2];
	}
	static void rotate_5() {
		//4321 다 아래쪽
		rotate(5);
		char[]backup=cube[1][2].clone();
		//2-3-4-1
		cube[1][2]=cube[4][2].clone();
		cube[4][2]=cube[3][2].clone();
		cube[3][2]=cube[2][2].clone();
		cube[2][2]=backup.clone();
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 1번집의 색 != N번집의 색이어야 한다

1. 1번집을 단색으로 제한한 후 RGB값을 각각 구한다

  - 1번집을 R로 설정 -> N번집이 G/B로 끝나는 최솟값 구하기

  - 1번집을 G로 설정 -> N번집이 R/B로 끝나는 최솟값 구하기

  - 1번집을 B로 설정 -> N번집이 R/G로 끝나는 최솟값 구하기

2. 전체 결과 6가지 중 최솟값이 정답

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));
		
		N = pint(br.readLine());
		cost = new int[N][3];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			cost[i][0]=pint(st.nextToken());
			cost[i][1]=pint(st.nextToken());
			cost[i][2]=pint(st.nextToken());
		}
		
		min=Integer.MAX_VALUE;
		
		temp=new int[N][3];
		temp[0][0]=cost[0][0];temp[0][1]=2000000;temp[0][2]=2000000;
		run(0);
		
		temp=new int[N][3];
		temp[0][0]=2000000;temp[0][1]=cost[0][1];temp[0][2]=2000000;
		run(1);

		temp=new int[N][3];
		temp[0][0]=2000000;temp[0][1]=2000000;temp[0][2]=cost[0][2];
		run(2);
		
		System.out.println(min);
	}
	static int[][] temp;
	static int[][] cost;
	static int min,N;
	static void run(int notPick) {
		for (int i = 1; i < N; i++) {
			temp[i][0]=Math.min(temp[i-1][1], temp[i-1][2])+cost[i][0];
			temp[i][1]=Math.min(temp[i-1][0], temp[i-1][2])+cost[i][1];
			temp[i][2]=Math.min(temp[i-1][1], temp[i-1][0])+cost[i][2];
		}
		for (int i = 0; i < 3; i++) {
			if(i!=notPick && temp[N-1][i]<min)min=temp[N-1][i];
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}