고양멍멍이

[문제링크]

0. 관리인은 오른쪽의, 자기보다 낮은 건물만 볼 수 있다

1. 빌딩들이 스택에 들어있을 때, 새로운 빌딩이 들어왔다면 2가지 경우가 된다

• 이전 빌딩에서 관측 가능 : 이전 빌딩이 새 빌딩보다 높다
• 이전 빌딩에서 관측 불가 : 이전 빌딩이 새 빌딩보다 낮다

2. 관측 가능한 빌딩을 만날때까지, 관측 불가능한 빌딩들은 다 스택에서 버린다

• 스택에 [9,8,7,3,2,1] 이 있었다면, 5가 들어왔을때 3,2,1이 버려진다

3. 그 후 스택에 남아있는 빌딩들이 새 빌딩을 관측 가능한 빌딩들이다

• 3,2,1을 버린 후 [9,8,7] 이 빌딩들은 5를 관측 가능하다

4. 스택의 크기만큼 관측 카운트를 누적시킨 후 새 빌딩 높이를 스택에 넣는다

※ 건물의 갯수는 최대 8만이므로, 최대 가능한 관측 수는 1+2+.... +79999+80000이다

• 이는 (80000*80001)/2 = 대략 32억이므로, int 범위를 초과하니 long이나 uint 변수를 사용해야한다
• JAVA에는 uint가 마땅히 없으므로 long을 사용

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));
		
		int N = pint(br.readLine());
		long cnt=0;
		Stack<Integer> stack = new Stack<>();
		
		for (int i = 0; i < N; i++) {
			int h = pint(br.readLine());
			while(!stack.isEmpty() && stack.peek()<=h)stack.pop();
			cnt+=stack.size();
			stack.add(h);
		}
		System.out.println(cnt);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 같은 열에서, 아래에 있는 값은 항상 윗 값보다 크다 = 해당 열의 최댓값은 가장 아래있는 값이다

1. 각 열마다 최댓값을 구해서 저장하고, 그중 가장 큰 값부터 하나씩 제외한다

• 쉽고 효율적으로 최댓값을 구하기 위해 우선순위 큐 사용

2. 최댓값을 제외할 때 같은 열의 그다음 큰 값, 즉 바로 위의 값을 대신 저장한다

3. N번째 제외되는 최댓값이 곧 N번째로 큰 수이므로 구하려는 답이다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
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));		
		
		int N = pint(br.readLine());
		int[][] num = new int[N][N];
		int[] idx = new int[N]; //각 열의 idx 관리
		int cnt=0;
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o2[1]-o1[1];
			}
		});
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			idx[i]=N-1;
			for (int j = 0; j < N; j++) num[i][j]=pint(st.nextToken());
		}
		
		for (int i = 0; i < N; i++) pq.add(new int[] {i, num[ idx[i]-- ][ i ]});
		
		while(cnt<N-1) {
			int[] cur = pq.poll();
			int i = cur[0];
			if(idx[i]>=0) { //더이상 값이 없을경우 처리
				int newV = num[ idx[i]-- ][i];
				pq.add(new int[] {i, newV});
			}
			
			cnt++;
		}
		System.out.println(pq.poll()[1]);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 스네이크 게임에서 생존 시간을 구하는 문제

1. 초기 방향은 항상 오른쪽이므로, 주어지는 방향 전환 데이터를 통해 몇초에, 어떤 방향으로 변하는지 미리 저장한다

2. 머리가 진행할 때, 해당 지점에 이동 방향 정보를 저장해 두어, 꼬리가 당겨질 때의 방향을 알 수 있도록 한다

3. 매 초 머리를 향하는 방향으로 이동하며,

• 사과가 나온다면 - 길이를 1 늘린다, 즉 꼬리의 길이를 줄이지 않는다
• 빈 공간이라면 - 꼬리를 이동시킨다
• 벽이라면 - 종료한다

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

public class Main{
	
	static int[][] d={
		{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}
	};
	static int[][]map;
	static int[][]move;
	static int N;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		
		map=new int[N+2][N+2];
		for (int i = 0; i < N+2; i++) {
			map[0][i]=-1;
			map[N+1][i]=-1;
			map[i][0]=-1;
			map[i][N+1]=-1;
		}
		
		int k = pint(br.readLine());
		
		for (int i = 0; i < k; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			map[ pint(st.nextToken()) ][ pint(st.nextToken()) ]=5; // 사과 위치 표시
			
		}
		int L = pint(br.readLine());
		move = new int[L][2]; // 몇초에, 어떤 방향으로 바꿀지 저장
		int dir = 3; // 초기 방향
		for (int i = 0; i < L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			move[i][0]=pint(st.nextToken());
			//현재 방향을 보고 다음 방향 계산
			switch (st.nextToken()) {
			case "D":
				dir++;
				if(dir==5)dir=1;
				move[i][1]=dir;
				break;
			case "L":
				dir--;
				if(dir==0)dir=4;
				move[i][1]=dir;
				break;
			default:
				break;
			}
		}
		
		int time=0; //생존 시간(구하려는 답)
		int cnt=0; // 회전 횟수
		dir=3;//초기방향
		int headX=1, headY=1;
		int tailX=1, tailY=1;
		while(true) {
			time++;
			//head이동
			map[headX][headY]=dir;
			headX+=d[dir][0];
			headY+=d[dir][1];

			if(map[headX][headY]==5) {//사과면 꼬리가 한칸 늘어나는효과 = 꼬리를 줄이지 않는다
			}
			else if(map[headX][headY]!=0) {//벽이면 죽음
				break;
			}
			else {//빈칸이면 꼬리를 한칸 당긴다
				int temp = map[tailX][tailY];
				map[tailX][tailY]=0;
				tailX+=d[temp][0];
				tailY+=d[temp][1];
			}
			
			//회전
			if(cnt<L && time == move[cnt][0]) {
				dir=move[cnt][1];
				cnt++;
			}
		}
		System.out.println(time);
	}
	
	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. 위 그림과 같이 높이를 하나씩 받으며 스택에 저장하고, 해당 입력으로 인해 발생한 빗물 공간을 구해 누적한다

1. 입력 x가 들어왔을때, 스택에 자기보다 작은 값이 있다면, 빗물 공간이 발생할 수 있다

• 위 그림처럼 6 0 4 0 3 0 0 5 순으로 입력이 들어왔을때, 3과 5 사이에는 공간이 발생한다 (빨강)
• 그 다음 4와 5 사이에도 공간이 발생했는데, 이전에 3까지의 높이는 처리했으므로 4 높이에 대해서만 공간이 생긴다 (노랑)
• 이전에 처리한 높이를 prevCnt로 저장, 사용한다
• 공간이 계속해 발생할 수 있으므로, 스택을 계속 따라간다

2. 스택에 자기보다 큰 값이 있다면, 역시 공간이 발생할 수 있다

• 6과 4 사이에서 공간이 발생한다 (파랑)
• 이때 생성되는 공간의 높이는 입력 x에서 이전 처리값 prevCnt를 뺀 값이다
  • 위 그림에서 초록색 부분은, 입력 x는 5이고 prevCnt는 4이므로 높이는 1이다
• 자기보다 큰 값을 만났으므로, 공간이 계속해서 발생할 수 없으니 종료한다

3. 위 방식으로 공간의 높이는 구할 수 있다

• 공간의 너비를 구하기 위해, 스택에 저장할 때 값뿐 아닌 해당 지점의 x좌표도 함께 저장한다
• 두 좌표를 비교해 너비를 구하여, 높이와 곱해 총 빗물 공간의 면적을 구한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
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 H = pint(st.nextToken());
		int W = pint(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		
		Stack<int[]> stack = new Stack<>();
		int area=0;
		
		for (int i = 0; i < W; i++) {
			int input = pint(st.nextToken());
			
			int prevMax=0, sum=0;
			while(!stack.isEmpty() && stack.peek()[0]<=input) {
				int[] tmp = stack.pop();
				
				if(tmp[0]>prevMax) {
					int height = tmp[0]-prevMax;
					prevMax=tmp[0];
					sum+= height*( i-tmp[1]-1 );
				}
				
			}
			
			if(!stack.isEmpty()) {
				int[] tmp = stack.peek();
				int height = input - prevMax;
				sum+= height*(i-tmp[1]-1);
			}
			
			area+=sum;
			// 스택에 넣기
			stack.add(new int[] {input,i});
			
		}
		System.out.println(area);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 번갈아가며 양쪽 끝에서 한장씩 집을때 최대한 많은 점수를 얻는 방법

1. x~y까지의 카드에서 최대한 많은 점수를 얻으려면 card[y] + (x~y-1) 혹은 card[x] + (x+1~y)중 큰 값으로 고를 수 있다

2. 이때, 각자 서로의 점수를 위해 최선의 전략을 사용하고, 서로 가져갈수 있는 카드의 총합은 동일하다

• 따라서, 후 플레이어의 최선의 전략 = 선 플레이어의 점수를 가능한 낮추는 전략 과 같다

3. DP테이블을 2중으로 만들어, (x, y) 만큼의 카드 상태에서 선 플레이어/후 플레이어 각각의 최선의 결과를 저장한다

• 후 플레이어의 선택은 선 플레이어의 점수와는 관계없으므로 저장하지 않는다

4. 모든 테이블이 완성된 후, 모든 카드에 대해 선 플레이어의 점수를 출력한다

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 tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			int N = pint(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int[] card = new int[N];
			int[][][]dp = new int[N+1][N+1][2];
			
			for (int i = 0; i < N; i++) {
				card[i]=pint(st.nextToken());
			}
			
			for (int i = 0; i < N; i++) {
				dp[i][i][0]=card[i];
				dp[i][i][1]=0;
			}
			
			//i~i+len 까지의 카드를 고려했을때, 근우가 얻을수 있는 최대 점수
			for (int len = 1; len < N; len++) {
				
				for (int i = 0; i < N-len; i++) {
					//i : 시작점, len : 길이
					int j = i+len;
					//근우턴일때 근우 최대점수 = 왼/오 각 경우중 최댓값 + 카드 선택값
					dp[i][j][0]=Math.max(card[j]+dp[i][j-1][1], card[i]+dp[i+1][j][1]);
					//명우턴일때 근우 최대점수 = 왼/오 각 경우중 최솟값 (카드 선택 못함)
					dp[i][j][1]=Math.min(dp[i+1][j][0], dp[i][j-1][0]);
				}
			}
			System.out.println(dp[0][N-1][0]);			
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 두 상자에 x,y개의 구슬이 있고, b1,b2,b3 중 하나만큼 구슬을 꺼낼 수 있을때, 최종 승자를 찾는 문제

1. (x, y)에서 시작해 b1, b2, b3를 빼는 경우의 수 전체를 고려했을때, 단 하나라도 승리하는 경우가 있다면 승리한다

2. 반대로, 모든 경우의 수가 패배라면, 패배한다

3. 선제공격이 이기는 경우를 true, 지는 경우를 false로 둔다

4. 최소 선택 단위인 b1보다 구슬의 수가 적다면 선택할수 없으므로 패배한다, 이를 기초로 DP 진행

5. 선공인 A가 어떠한 선택을 하여 구슬 상태가 (x', y')로 변했는데, DP[x'][y']가 선공 승리인 상태라면, A는 패배한다

• (x', y')상태에서는 턴이 넘어가 B가 선공이 되기 때문
• 즉, DP[x'][y']로 진행할 경우 현재 상태인 DP[x][y]에서의 결과는 !DP[x'][y']가 된다

6. DP 테이블이 완성되면 구한 결과 출력

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 b1 = pint(st.nextToken());
		int b2 = pint(st.nextToken());
		int b3 = pint(st.nextToken());
		
		boolean[][]dp = new boolean[501][501];
		
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp.length; j++) {
				if(i>=b1&&j>=b1) {
					//어떤 선택을 하더라도 상대 승리
					if(dp[i-b1][j] && dp[i][j-b1])dp[i][j]=false;
					//내가 이기는 선택지가 존재
					else dp[i][j]=true;
				}
				else if(i>=b1)dp[i][j]=!dp[i-b1][j];
				else if(j>=b1)dp[i][j]=!dp[i][j-b1];

				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b2&&j>=b2) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b2][j] && dp[i][j-b2])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b2)dp[i][j]=!dp[i-b2][j];
					else if(j>=b2)dp[i][j]=!dp[i][j-b2];
				}
				
				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b3&&j>=b3) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b3][j] && dp[i][j-b3])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b3)dp[i][j]=!dp[i-b3][j];
					else if(j>=b3)dp[i][j]=!dp[i][j-b3];
				}
			}
		}
		 
		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int k1 = pint(st.nextToken());
			int k2 = pint(st.nextToken());
			
			System.out.println(dp[k1][k2]?'A':'B');
			
		}
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. n글자 이내로 이루어진 가장 긴 연속된 문자열 찾기

• 투 포인터로 n글자를 유지하면서 진행한다

1. n+1글자가 되어 읽을 수 없을때까지 snd 포인터를 진행, 문자열을 늘린다

• 최장 문자열 길이를 갱신한다

2. 다시 n글자가 되어 읽을 수 있을때까지 fst 포인터를 진행, 문자열을 줄인다

3. snd가 끝에 도달하여 종료되었을때, 가장 길었던 문자열의 길이가 정답

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		String s = br.readLine();
		
		int maxLen=0;
		int len = 0;
		int[] cnt = new int[26];
		int kindCnt=0;
		
		int fst=0, snd=0;
		
		while(fst<=snd && snd<s.length()) {
			//1. N글자+1까지 snd 늘리면서 len 비교저장
			while(snd<s.length() && kindCnt<=N) {
				int cur = s.charAt(snd++)-'a';
				if(cnt[cur]==0)kindCnt++;
				cnt[cur]++;
				len++;
				//N+1글자일 때는 len을 갱신하면 안된다 
				if(kindCnt<=N)maxLen=Math.max(maxLen, len);
			}
			//2. N글자까지 fst 줄이기
			
			while(fst<=snd && kindCnt>N) {
				int cur = s.charAt(fst++)-'a';
				cnt[cur]--;
				if(cnt[cur]==0)kindCnt--;
				len--;
			}
			
		}
		System.out.println(maxLen);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}