고양멍멍이

[문제링크]

0. 현재 파이프의 모양 - 인접 파이프의 모양 에 따라 갈수 있는지 없는지 여부가 결정된다

  - 총 4방향이므로, 4개의 bit에 bitmask로 저장해 정보를 나타낸다.

1. 입력값(0~7)에 따라 해당하는 bitmask정보를 부여한다

2. 시작점에서 time만큼 bfs를 돌며

  - 현재 노드에서 상/하/좌/우 통로가 존재하고 + 진행 노드에서 하/상/우/좌 통로가 존재한다면

  - 진행 가능, 큐에 넣는다

  - 방문체크 대신 큐에 넣을때 자기 위치의 값을 0으로 바꿔 재방문을 방지한다

3. time이 다 지났다면 (혹은 도중에 탐색을 마쳐 qu가 비었다면)

  - 방문할때마다 1씩 증가시켜준 cnt를 출력, 종료한다

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

public class Solution{
	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 testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int x = pint(st.nextToken())+1;
			int y = pint(st.nextToken())+1;
			int t = pint(st.nextToken());
			
			int[][] map = new int[n+2][m+2];
			
			for (int i = 1; i < n+1; i++) {
				st=new StringTokenizer(br.readLine()," ");
				for (int j = 1; j < m+1; j++) {
					int temp = pint(st.nextToken());
					if(temp==1)map[i][j]=0b1111;
					else if(temp==2)map[i][j]=0b1100;
					else if(temp==3)map[i][j]=0b0011;
					else if(temp==4)map[i][j]=0b1001;
					else if(temp==5)map[i][j]=0b0101;
					else if(temp==6)map[i][j]=0b0110;
					else if(temp==7)map[i][j]=0b1010;
				}
			}
			
			Queue<int[]> qu = new LinkedList<int[]>();
			qu.add(new int[] {x,y});
			int cnt=0;
			int time=0;
			while(time++<t && !qu.isEmpty()) {
				int len = qu.size();
				
				for (int i = 0; i < len; i++) {
					int[] cur=qu.poll();
					int temp = map[cur[0]][cur[1]];
					if(temp==0)continue;
					
					if((temp&1<<3)!=0 && (map[cur[0]-1][cur[1]]&1<<2)!=0)
						qu.offer(new int[] {cur[0]-1,cur[1]});
					if((temp&1<<2)!=0 && (map[cur[0]+1][cur[1]]&1<<3)!=0)
						qu.offer(new int[] {cur[0]+1,cur[1]});
					if((temp&1<<1)!=0 && (map[cur[0]][cur[1]-1]&1<<0)!=0)
						qu.offer(new int[] {cur[0],cur[1]-1});
					if((temp&1<<0)!=0 && (map[cur[0]][cur[1]+1]&1<<1)!=0)
						qu.offer(new int[] {cur[0],cur[1]+1});
					
					cnt++;
					map[cur[0]][cur[1]]=0;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
		}//end of tc
		System.out.println(sb);
	}

	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 슬라이딩 윈도우로, 다음 초밥을 넣고, 첫 초밥은 빼가며 종류를 센다 (큐 사용)

  - 회전초밥벨트이므로, 시작한 K개의 초밥이 마지막 초밥에 이어진다 

  - [시작부분] - [나머지] - [시작부분] 의 순서로 저장해서 처리

1. end포인터를 1씩 늘려가며 k개의 초밥을 받고, 종류를 센다

2. end포인터가 N+k가 될 때까지, end포인터의 초밥을 포함시키고, fst포인터의 초밥을 내보내는것을 반복한다

3. 위 과정중 구해진 가장 큰 cnt를 출력

개선점 : 모든 입력을 받고 시작하게 되면, 초밥을 큐로 관리할 필요가 없다

  - 큐 대신 포인터변수 2개만 사용해도 된다.

  - 반영함

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 = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		//d+1개의 배열 생성.
		int[] count = new int[d+1];
		count[Integer.parseInt(st.nextToken())]=1;//쿠폰은 항상 먹는다
		
		//초밥 종류 cnt변수
		int cnt=1, max=0;
		
		//처음 K개 저장할 배열 생성
		int[] saveFst = new int[N+k];
		for (int i = 0; i < N; i++) {
			saveFst[i]=Integer.parseInt(br.readLine());;
			if(i<k)saveFst[N+i]=saveFst[i];
		}
		
		int fst=0, end=0;
		for (; end < k; end++) {
			if(++count[saveFst[end]]==1)cnt++;
		}
		max=cnt;
		for (; end < N+k; end++) {
			if(++count[saveFst[end]]==1)cnt++;
			
			if(--count[saveFst[fst++]]==0)cnt--;
			
			if(max<cnt)max=cnt;
		}
		System.out.println(max);
		
	}
}

[문제링크]

0. 내부 공기엔 인접해도 녹지 않으므로, 외곽 공기에 대해서만 bfs를 진행.

  - 0,0은 항상 밖의 공기이다

1. 0,0을 시작점으로, 외곽 공기를 bfs로 순회한다

  - 치즈를 처음 만나면, 표시만 한다

  - 치즈를 2번째로 만나면, 제거 대상 치즈로 판단, 저장한다

2. 1번에서 저장된 제거대상 치즈를 제거한다

3. 위 과정을 치즈가 없어질때까지 반복한다

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

public class Main{
	static int[] dx= {1,0,-1,0};
	static int[] dy= {0,1,0,-1};
	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];
		int chCnt=0;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < m; j++) {
				map[i][j]=pint(st.nextToken());
				if(map[i][j]==1)chCnt++;
			}
		}
		int time=0;
		
		Queue<int[]>qu = new LinkedList<int[]>();
		Queue<int[]>removeCh = new LinkedList<int[]>();
		
		while(chCnt!=0) {
			time++;
			//bfs돌며 제거할 치즈 탐색
			int[][]isV = new int[n][m];
			qu.offer(new int[] {0,0});
			isV[0][0]=1;
			while(!qu.isEmpty()) {
				int[] ch = qu.poll();
				
				for (int i = 0; i < 4; i++) {
					int tx = ch[0]+dx[i], ty=ch[1]+dy[i];
					if(tx<0||tx>=n||ty<0||ty>=m)continue;
					
					//미방문 공기
					if(isV[tx][ty]==0 && map[tx][ty]==0) {
						isV[tx][ty]=1;
						qu.offer(new int[] {tx,ty});
					}
					//치즈 처음 만남
					else if(isV[tx][ty]==0) {
						isV[tx][ty]=1;
					}
					//치즈 2번째 만남
					else if(isV[tx][ty]==1 && map[tx][ty]==1) {
						isV[tx][ty]=2;
						removeCh.offer(new int[] {tx,ty});
					}
					
				}
			}
			
			//녹을 치즈 제거
			chCnt-=removeCh.size();
			while(!removeCh.isEmpty()) {
				int[] ch = removeCh.poll();
				map[ch[0]][ch[1]]=0;
			}
			
		}
		
		System.out.println(time);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 치킨집의 총 개수를 모르므로 arraylist로 관리

  - 살릴 치킨집의 개수는 알고 있으므로 배열로 관리

1. 가능한 모든 살릴수 있는 치킨집의 조합을 구한다 (combi 함수)

2. 각 조합에 대해, 치킨집 위치를 시작으로 bfs를 돌려 모든 집까지의 최소 거리를 구한다 (bfs함수)

3. bfs함수에서 구한 최소 거리가 더 작다면 min을 갱신

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{

	static boolean[][]isV;//방문체크
	static int[][]map;
	static int[][]select;//살릴 치킨집
	static List<int[]>chicken;//모든 치킨집
	static int ans,n,m;
	static Queue<int[]> qu;
    
	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());
		
		map = new int[n+2][n+2];
		chicken = new ArrayList<>();
		//-1 패딩
		for (int i = 0; i < n+2; i++) {
			map[i][0]=-1;map[i][n+1]=-1;
			map[0][i]=-1;map[n+1][i]=-1;
		}
		
		//입력받기 + 치킨집 저장
		for (int i = 1; i <= n; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				map[i][j]=pint(st.nextToken());
				if(map[i][j]==2)chicken.add(new int[] {i,j});
			}
		}
		
		ans=Integer.MAX_VALUE;
		select=new int[m][2];
		combi(0, 0);
		System.out.println(ans);
        
	}
    
	static void combi(int cnt, int prev) {
		if(cnt==m) {
			qu = new LinkedList<int[]>();
			for (int i = 0; i < m; i++) {
				qu.offer(new int[] {select[i][0], select[i][1], 0});
			}
			ans = Math.min(ans, bfs());
			return;
		}
		
		for (int i = prev, len = chicken.size(); i < len; i++) {
			select[cnt][0]=chicken.get(i)[0];
			select[cnt][1]=chicken.get(i)[1];
			combi(cnt+1, i+1);
		}
	}
	
	static int bfs() {
		isV = new boolean[n+2][n+2];
		int dist=0;
		while(!qu.isEmpty()) {
			int[] cur = qu.poll();
			
			if(map[cur[0]][cur[1]]==1) {
				dist+=cur[2];
			}
			
			if(!isV[cur[0]+1][cur[1]] && map[cur[0]+1][cur[1]]>=0) {
				isV[cur[0]+1][cur[1]]=true;
				qu.offer(new int[] {cur[0]+1, cur[1], cur[2]+1});
			}
			if(!isV[cur[0]-1][cur[1]] && map[cur[0]-1][cur[1]]>=0) {
				isV[cur[0]-1][cur[1]]=true;
				qu.offer(new int[] {cur[0]-1, cur[1], cur[2]+1});
			}
			if(!isV[cur[0]][cur[1]+1] && map[cur[0]][cur[1]+1]>=0) {
				isV[cur[0]][cur[1]+1]=true;
				qu.offer(new int[] {cur[0], cur[1]+1, cur[2]+1});
			}
			if(!isV[cur[0]][cur[1]-1] && map[cur[0]][cur[1]-1]>=0) {
				isV[cur[0]][cur[1]-1]=true;
				qu.offer(new int[] {cur[0], cur[1]-1, cur[2]+1});
			}
			
		}
		
		return dist;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. shoot함수 : n번째 구슬을 모든 경우의 수에 대해 쏴보고, n+1번째로 재귀하는 함수

  - remove함수 : x, y좌표의 벽돌이 깨졌을 경우 모든 벽돌을 재귀로 깨는 함수

  - getDown함수 : 벽돌을 깬 후 모든 벽돌을 빈공간 없이 아래로 쌓는 함수

1. shoot함수가 모든 경우의 수에 대해 remove -> getDown 해본다

2. n번 구슬을 쐈을때 남아있는 ball값과 min을 비교, 갱신

* ball(remain)값을 인자로 넘기지 말고 전역변수로 관리할 수 있을것같은데, 피곤해서 포기

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

public class Solution{
	
	static int n,w,h,ball,min;
	static int[][]map;
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	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 testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = pint(st.nextToken());
			w = pint(st.nextToken());
			h = pint(st.nextToken());
			ball = 0;
			map = new int[h][w];
			
			for (int i = 0; i < h; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < w; j++) {
					map[i][j]=pint(st.nextToken());
					if(map[i][j]!=0)ball++;
				}
			}
			min=ball;
			shoot(0,ball);
			
			sb.append("#").append(testcase).append(" ").append(min).append("\n");
		}
		System.out.println(sb);
	}
	
	static void shoot(int cnt, int remain) {
		if(cnt==n) {
			min=Math.min(min, remain);
			return;
		}
		//현재 정보 백업
		int[][]backup = new int[h][w];
		for (int x = 0; x < h; x++) {
			for (int y = 0; y < w; y++) {
				backup[x][y]=map[x][y];
			}
		}
		int ballBackup=ball;

		for (int i = 0; i < w; i++) {
			// 정보 원상복구
			for (int x = 0; x < h; x++) {
				for (int y = 0; y < w; y++) {
					map[x][y]=backup[x][y];
				}
			}
			ball=ballBackup;

			for (int j = 0; j < h; j++) {
				if(map[j][i]!=0) {
					remove(j,i); // 제거하고
					getDown(); // 아래로 정렬하고
					break;
				}
			}
			shoot(cnt+1, ball); // 다음 발사로 재귀
			
		}
	}
	
	static void remove(int x, int y) {
		int c = map[x][y];
		map[x][y]=0;
		--ball;
		for (int j = 0; j < 4; j++) {
			int tx=x, ty=y;
			for (int i = 1; i < c; i++) {
				tx += dx[j];
				ty += dy[j];
				if(tx<0 || tx>=h || ty<0 || ty>=w)break;
				if(map[tx][ty]!=0)remove(tx,ty);
			}
		}
	}
	
	static void getDown() {
		for (int i = 0; i < w; i++) {
			int cnt=h-1;
			for (int j = h-1; j >=0 ; j--) {
				if(map[j][i]!=0) {
					int t = map[j][i];
					map[j][i]=0;
					map[cnt--][i]=t;
				}
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 폭탄 진행현황을 index로 검사한다

1. 현재 index에 맞는 문자가 들어오면 : 누적 후 index+1

2. 현재 index와 다른 문자가 들어오면

  - 폭탄의 첫 문자이다 : 새 폭탄의 시작점일 가능성, 현재 index정보를 백업하고 누적, index=1부터 다시 시작

  - 일반 문자이다 : 폭탄이 아니므로 모든 index를 제거, 누적된 문자들을 출력 문자열에 추가하고 index=0

  - 폭탄의 마지막 문자이다 : 폭탄이 터진다. 누적한 문자를 제거하고 백업한 index복구, 없으면 index=0

3. 모든 문자를 순회 후 : 누적한 문자가 있다면 출력 문자열에 추가

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringBuilder sb2;
		
		String s = br.readLine();
		String boom = br.readLine();
		
		int idx=0;
		Stack<Character> charStack = new Stack<>();
		Stack<Integer> idxStack = new Stack<>();
		
		for (int i = 0; i < s.length(); i++) {
			char cur = s.charAt(i);
			
			if(cur==boom.charAt(idx)) {
				//폭탄이 순조롭게 진행중
				idx++;
				charStack.add(cur);
				if(idx == boom.length()) {
					//폭탄의 완성
					//charStack에서 완성한 boom 비우기
					
					for (int j = 0; j < idx; j++) {
						charStack.pop();
					}
					//idx가 존재한다면, 복구하기
					if(!idxStack.isEmpty()) {
						idx = idxStack.pop();
					}else {
						idx = 0;
					}
				}
			}
			else {
				if(cur==boom.charAt(0)) {
					//새 폭탄의 시작
					idxStack.add(idx);
					charStack.add(cur);
					idx=1;
				}
				else {
					//평범한 문자열일 경우
					//쌓은 idx 다비우고
					idxStack.clear();
					
					//쌓인 char들은 boom이 아니므로 다 넣는다
					sb2 = new StringBuilder();
					while(!charStack.isEmpty()) {
						sb2.append(charStack.pop());
					}sb.append(sb2.reverse());
					//마지막에 현재 문자 반영
					sb.append(cur);
					idx=0;
				}
			}
		}
		sb2 = new StringBuilder();
		while(!charStack.isEmpty()) {
			sb2.append(charStack.pop());
		}sb.append(sb2.reverse());
		if("".equals(sb.toString())) System.out.println("FRULA");
		else System.out.println(sb);
        
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 그리디를 이용해 가격 구하기

  - n번 동전의 가치가 w이고, n-1번 동전까지 사용하여 w-1 금액까지는 옳은 해가 구해져 있다면

  - w원 이후의 가격 x에 대해선 ( (x%w)의 최적해 + (x/w) ) 이 최적해이다

  - ex) 한국 동전에 대해, w가 500원일때 650원의 최적해는 (150원의 최적해 + 1) 이다

  - DP는 이 문제에서 항상 옳은 해를 구할 수 있다

  - DP를 이용해 구한 해와 그리디를 이용해 구한 해가 일치한다면, 그리디가 최적해를 구하는 것

  - 그리디를 통해 w ~ 2*w까지 최적해를 구할수 있다고 하면, 2*w ~ 이후에 대해서도 최적해가 보장된다

  - n+1번째 동전의 가치가 2*w보다 작다면 n+1번 동전까지만 최적해를 증명해도 된다

  - 즉, n번째 동전에 대해, min( 2*w(n) , w(n+1) ) 까지 최적해 여부를 검증

1. 정답은 기본값 Yes로 두고, 모든 동전에 대해 최적해 일치 여부를 검사한다

2. 현재 금액 i가 n번 코인의 화폐가치 w보다 작을 경우, w까지 진행한다

3. w부터 min( w*2, w[n+1] ) 금액까지 그리디 방식으로 해를 만든다

4. w부터 min( w*2, w[n+1] ) 금액까지 DP방식으로 해를 만들며, 그리디의 해와 비교한다

  - 중간에 불일치하는 값이 존재하면, 답을 No로 바꾸고, break한다

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));
		
		int N = pint(br.readLine());
		int[] coin = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			coin[i]=pint(st.nextToken());
		}
		int[] valid = new int[coin[N-1]*2+1];//최대 20만 1
		valid[1]=1;//1원은 항상 1.
		
		String answer = "Yes";
		
		int coinIdx=1;
		for (int i = 1; i < coin[N-1]*2+1 && coinIdx<N; i++) {

			i = Math.min(2*i-1, coin[coinIdx]-1);
			//coin[i]번의 화폐가치까지 정상진행
			while(i<coin[coinIdx]) {
				int realcosti=Integer.MAX_VALUE;
				for (int k = 0; k < coinIdx; k++) {
					if(1 + valid[i-coin[k]] < realcosti)realcosti=1 + valid[i-coin[k]];
				}valid[i++]=realcosti;
			}
			
			//valid[i] ~ 2 i까지 그리디로, +1해서 제작
			int destination = i*2;
			if(coinIdx<N-1)destination = Math.min(i*2, coin[coinIdx+1]);
			for (int j = i; j <= destination; j++) {
				valid[j]=valid[j-i]+1;
			}
			
			//직접 계산해가면서 valid[j]와 계산값이 같은지 비교. 다르면 바로 탈출
			//i-1번까지의 동전만 사용해서 i ~ 2*i의 값들을 계산해보기
			for (int j = i; j <= destination; j++) {
				int realcosti=Integer.MAX_VALUE;
				for (int k = 0; k <= coinIdx; k++) {
					if(1 + valid[j-coin[k]] < realcosti)realcosti=1 + valid[j-coin[k]];
				}
				if(realcosti != valid[j]) {
					answer = "No";
					i=coin[N-1]*2+1;//for문 종료 목적
					break;
				}
			}
			coinIdx++;
		}
		System.out.println(answer);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

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);
	}
}