고양멍멍이

[문제링크]

0. 센서의 위치가 아닌, 센서 사이의 거리에 대한 문제이다

1. 센서가 N개 있다면, 센서 사이의 거리는 N-1개 생성된다

2. 기지국이 1개라면, 해당 기지국은 모든 거리를 포함해야한다

3. 기지국이 2개라면, 어떤 거리 X를 이루는 두 센서를 각각 관리함으로서, 거리 X부분을 포함하지 않아도 된다

4. 기지국이 K개라면, N-1개의 거리들 중 K-1개를 선택하지 않아도 된다

5. 전체 거리들 중 그 값이 큰 순서로 K-1개 선택하지 않으면 요구한 최소 길이의 합이 나온다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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 K = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int minimumArea=0;
		
		int[] sensor = new int[N];
		PriorityQueue<Integer>pq = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			sensor[i] = pint(st.nextToken());
		}
		
		Arrays.sort(sensor);
		
		for (int i = 1; i < N; i++) {
			int distance = sensor[i]-sensor[i-1];
			pq.add(distance);
		}
		
		
		for (int i = 0, len=pq.size(); i < len - (K-1); i++) {
			minimumArea+=pq.poll();
		}
		System.out.println(minimumArea);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. PPAP문자열이란? - P에서 시작해 P를 PPAP로 치환한 문자열

  - 반대로 PPAP를 P로 치환하다 보면 근본인 P로 돌아간다

1. PPAP는 P로만 치환되므로, A에만 집중하면 된다

2. A가 들어왔을때, 앞에는 반드시 P가 2개 이상 존재해야하고, 뒤에도 P가 하나 존재해야만 한다

3. 해당 조건을 위해, 앞에 등장한 P의 갯수를 세서 저장하고 있는다 (curIndex)

  - A가 들어올 때 curIndex가 2 이상이고, A의 뒤에도 P가 있다면 PPAP를 감지, P로 치환한다

  - 결과적으로 curIndex는 (-2+1) 되니 -1 된다

4. 해당 조건을 만족하지 않을 경우 PPAP문자열이 아니므로, 즉시 실패처리 및 break한다

5. 모든 PPAP가 성공적으로 전환된 후에, P 하나만 남아있어야한다

  - curIndex이 1보다 크면 P가 여러개 있는 문자열, 실패처리한다

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));
		
		String s = br.readLine();
		
		int curIndex=0;
		boolean isOK=true;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if(c=='P') {
				curIndex++;
			}
			else {
				//new PPAP or wrong
				if(c=='A') {
					if(curIndex>=2 && i+1 < s.length() && s.charAt(i+1)=='P') {
						curIndex--;
						i++;
					}
					else {
						//wrong
						isOK=false;
						break;
					}
				}
				else {
					//wrong
					isOK=false;
					break;
				}
			}
		}
		if(curIndex>1)isOK=false;
		System.out.println(isOK?"PPAP":"NP");
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 마감일까지 10일남은 과제를 오늘 하는건 괜찮지만, 마감일까지 하루 남은 과제를 10일뒤에 하는것은 불가능하다

  - 가장 먼 마감일부터 그리디하게 최고 점수의 과제를 선택한다

1. 과제를 마감일 내림차순으로 정렬한다

2. 최고 점수의 과제를 빠르게 선택하기 위해 priority queue 사용

3. 각 날짜별로, 해당 날짜 마감의 과제를 priority queue에 넣고, 최고 점수의 하나만 꺼내서 누적한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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[][]assign = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			assign[i][0] = pint(st.nextToken());
			assign[i][1] = pint(st.nextToken());
		}
		
		Arrays.sort(assign, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o2[0]-o1[0];
			}
		});
		
		PriorityQueue<Integer>pq = new PriorityQueue<>(Comparator.reverseOrder());
		int totalScore=0;
		
		int today = assign[0][0];
		int i=0;
		while(today!=0) {
			while(i<N && assign[i][0]==today) {
				pq.add(assign[i][1]);
				i++;
			}
			
			//날짜 갱신
			today--;
			if(!pq.isEmpty())totalScore+=pq.poll();
		
		}
		
		System.out.println(totalScore);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 팰린드롬 수인지 판단하기 : 앞/뒤 양쪽에서 동시에 출발해, 한칸씩 이동하며 수가 같은지 비교

  - 거의 O(1)에 가까운 복잡도를 가진다

1. 에라토스테네스의 체를 이용해 소수를 판별하면서, 소수에 대해서만 팰린드롬 여부를 판단한다

2. 입력 값 이상의 소수&팰린드롬이 발견되면 소수 판별을 종료하고, 출력한다

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

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 range=2000000;
		int ans=0;
		boolean[] notPrime = new boolean[range];
		for (int i = 2; i < range; i++) {
			if(!notPrime[i]) {
				for (int j = i; j < range; j+=i) {
					notPrime[j]=true;
				}
				if(isPalin(i)) {
					if(i>=N) {
						ans=i;
						break;
					}
				}
			}
		}
		System.out.println(ans);
		
	}
	static boolean isPalin(int n) {
		String str = Integer.toString(n);
		int s = 0, e = str.length()-1;
		
		while(s<=e) {
			if(str.charAt(s++)!=str.charAt(e--)) {
				return false;
			}
		}
		return true;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 주어진 문자로 만들수 있는 모든 순열 중, 조건을 만족하는 갯수를 구하는 문제

  - 조건 1. 인접한 문자는 달라야 한다

  - 조건 2. 최종 결과가 달라야 한다 (a 2개로 aa', a'a을 만들수 있지만, 둘은 같은것으로 취급한다)

1. 순열의 i번째 자리를 정할 때 이전 문자정보를 참고해 다른 문자만 사용한다면, 조건 1번은 해결할 수 있다

  - 0번째 자리에서 참조할 값으로는 입력값(알파벳)이 아닌 아무 문자나 주면 된다

2. 조건 2번의 경우, 여러번 등장하는 같은 문자를 다른 문자로서 사용하기 때문에 발생한다.

  - 즉, i번째 자리에 한번 a 문자를 사용했다면 a가 또 등장해도 사용하지 않으면 해결할 수 있다

3. 이를 위해, 한번 사용한 문자의 정보를 저장해두어 중복 사용하는것을 막았다 (bitmask)

4. 2/3번에서 걸러지지 않고 끝까지 완료된 순열만 count해주면 된다

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		s = br.readLine().toCharArray();
		isC=new boolean[s.length];
		cntLuck=0;
		lucky(0, ' ');
		System.out.println(cntLuck);
	}
	
	static char[] s;
	static boolean[] isC;
	static int cntLuck;
	
	static void lucky(int cnt, char prev) {
		if(cnt==s.length) {
			cntLuck++;
			return;
		}
		int bitMask=0;
		for (int i = 0; i < s.length; i++) {
			if(!isC[i] && s[i]!=prev && ( (bitMask&1<<(s[i]-'a')) == 0)) {
				//not used + not same with prev
				isC[i]=true;
				bitMask|=1<<(s[i]-'a');
				lucky(cnt+1, s[i]);
				isC[i]=false;
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. C++ 등 일부 언어에서 내장 라이브러리로 제공하는 next permutation 문제

  - 알파벳 순서대로 만들어진 조합의 다음 모습 구하기

1. next permutation을 구하는 방법은?

• 뒤에서부터 탐색해, 증가하지 않는 첫 부분의 위치를 구한다
  • 126543 을 예시로 하면, 3-4-5-6-2-1 이므로 2가 구하려는 위치이다
• 다시 뒤에서부터 탐색해, 2보다 큰 수들 중 처음 나오는 수의 위치를 구한다
  • 3-4-5-6-2-1 순서이므로 3이 2보다 큰 수이면서 가장 처음 나오는 수이다
• 1/2에서 구한 두 위치의 수를 바꾼다
  • 126543은 2/3이 바뀌며 136542가 된다
• 1번에서 구한 위치 뒤쪽의 수들을 정렬한다
  • 2번째 수였으므로 3~끝까지 정렬한다
  • 136542에서 132456이 된다

2. 실제 풀이 방법

• 앞부분 - 뒷부분 2개의 stringbuilder를 둔다
• 뒤에서부터 탐색해, 증가하지 않는 첫 위치(이하 A위치)를 구하며 큐에 넣는다
• 해당 위치 앞은 변하지 않을 것이니, 앞부분 builder에 넣는다
• 큐에 들어가 있는 부분은 오름차순으로 진행하며 차례대로 넣는 뒷부분이니, 그대로 꺼내도 정렬되어 있다
• 큐에서 하나씩 꺼내면서 뒷부분 builder에 넣되, A위치 수보다 커질때 한번 따로 처리해야한다
• 커지는 순간 큐에서 꺼낸 수는 앞부분 builder에, A위치의 수는 뒷부분 builder에 넣는다 (swap의 역할)
• 큐의 나머지는 다 뒷부분에 넣는다

• 최종적으로 합치면 종료

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

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++) {
			StringBuilder sb = new StringBuilder();
			StringBuilder sb_back = new StringBuilder();
			char[] str = br.readLine().toCharArray();
			
			Queue<Character> qu = new LinkedList<>();
			int len = str.length-1;
			while(len>0 && str[len-1] >= str[len]) {
				qu.add(str[len]);
				len--;
			}
			if(len==0) {
				//다음 단어가 없다
				System.out.println(str);
			}
			else {
				qu.add(str[len]);
				len--;
				
				//정상인 앞부분 넣기
				for (int i = 0; i < len; i++) {
					sb.append(str[i]);
				}
                
				//바뀔 위치 탐색
				char temp=' ';
				while(qu.peek() <= str[len]) {
					temp=qu.poll();
					sb_back.append(temp);
				}
                
				//바꾼다
				sb.append(qu.poll());
				sb_back.append(str[len]);
                
				//나머지 넣기
				while(!qu.isEmpty()) {
					sb_back.append(qu.poll());
				}

				System.out.print(sb);
				System.out.println(sb_back);
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 국경선을 여는, 연합을 구한 다음, 연합 국가들의 인구를 공통 배분한다

  - 더이상 연합이 형성되지 않을때까지 반복

1. L 이상 R 이하일때 진행하는 DFS로 연합과 그 인구를 구한다

  - 인구는 DFS 결과로 반환, 연합은 tempMap 배열에 idx를 작성한다

2. 연합이 형성되지 않았다면, 즉 DFS가 호출된 횟수가 국가의 횟수와 같다면 종료 후 소요된 day 출력

3. 연합이 형성되었다면, 인구수를 골고루 분배해 갱신한다 (소숫점은 버리므로 int 간 나눗셈)

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));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		 n = pint(st.nextToken());
		L = pint(st.nextToken());
		R = pint(st.nextToken());
		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());
			}
		}
		
		int day=0;
		while(true) {
			union = new ArrayList<>();
			tempMap=new int[n][n];
			
			int cnt=1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(tempMap[i][j]==0) {
						//union을 찾아서,
						//전체 합계와 나라 갯수를 저장한다
						num=0;
						union.add(new int[] {find(i,j,cnt++), num});
					}
				}
			}
			
			if(cnt==n*n+1)break;//union이 없으면 끝, 탈출한다
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					//찾은 union정보를 바탕으로 각 나라별 새 인구를 채워넣는다
					map[i][j]=union.get(tempMap[i][j]-1)[0] / union.get(tempMap[i][j]-1)[1];
				}
			}
			day++;
			
		}
		System.out.println(day);
		
	}
	static int n,L,R, num;
	static ArrayList<int[]> union;
	static int[][]map;
	static int[][]tempMap;
	
	static int find(int x, int y, int cnt) {
		tempMap[x][y]=cnt;
		num++;
		int popul=map[x][y];
		if(x>0 && tempMap[x-1][y]==0
				&& Math.abs(map[x-1][y]-map[x][y])>=L
				&& Math.abs(map[x-1][y]-map[x][y])<=R) {
			popul+=find(x-1,y,cnt);
		}
		if(x<n-1 && tempMap[x+1][y]==0
				&& Math.abs(map[x+1][y]-map[x][y])>=L
				&& Math.abs(map[x+1][y]-map[x][y])<=R) {
			popul+=find(x+1,y,cnt);
		}
		if(y>0 && tempMap[x][y-1]==0
				&& Math.abs(map[x][y-1]-map[x][y])>=L
				&& Math.abs(map[x][y-1]-map[x][y])<=R) {
			popul+=find(x,y-1,cnt);
		}
		if(y<n-1 && tempMap[x][y+1]==0
				&& Math.abs(map[x][y+1]-map[x][y])>=L
				&& Math.abs(map[x][y+1]-map[x][y])<=R) {
			popul+=find(x,y+1,cnt);
		}
		
		return popul;
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 단순한 구현 문제

  - 2-b 수행하기 전 2-c,d먼저 조건 체크/수행해야한다

1. 현재 위치를 청소하며 clean 수치를 1씩 증가시킨다

2. 2-c,d 조건 체크를 위해 4방향 탐색

3. 4방향 다 벽/청소가 끝났다면 현 위치의 뒤를 확인하여 벽이라면 종료한다 (2-d)

4. 벽이 아니라면, 뒤로 물러난다 (2-c)

5. 왼쪽에 빈공간이 있다면, 회전 후 1칸 진행한다 (2-a)

4. 없다면, 회전한다 (2-b)

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

public class Main{
	
	static int[][]left= {
			{0,-1},//북쪽 기준 왼쪽
			{-1,0},//동쪽 기준 왼쪽
			{0,1},//남쪽기준
			{1,0}//서쪽기준
	};
	static int[][]back= {
			{1,0},//북쪽 기준 뒤쪽
			{0,-1},//동쪽 기준 뒤쪽
			{-1,0},//남쪽 기준 뒤쪽
			{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());
		
		st = new StringTokenizer(br.readLine(), " ");
		int r = pint(st.nextToken());
		int c = pint(st.nextToken());
		int d = pint(st.nextToken());
		
		int[][]map = new int[n][m];
		
		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());
			}
		}
		
		int clean=0;
		while(true) {
			//1
			if(map[r][c]==0) {
				map[r][c]=2;
				clean++;
			}
			//2-c
			//2-d
			boolean isDone=true;
			for (int i = 0; i < 4; i++) {
				if(map[ r+left[i][0] ][ c+left[i][1] ]==0) {
					isDone=false;
				}
			}
			if(isDone) {//4방에 0이 없으면
				if(map[r+back[d][0]][c+back[d][1]]==1) {
					//2-D, 뒤가 벽
					break;
				}
				else {
					//2-C, 물러남
					r+=back[d][0];
					c+=back[d][1];
					continue;
				}
			}
			
			//2-a
			//왼쪽에 청소 안했으면
			if(map[r+left[d][0]][c+left[d][1]]==0) {
				r+=left[d][0];
				c+=left[d][1];
				d=(d+4-1)%4;
			}
			//2-b
			else {
				d=(d+4-1)%4;
			}
		}
		System.out.println(clean);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}