프로그래머스 pccp
절대 남의 풀이를 보지 말고 풀자(풀도록 노력하자!)! 🤔
모의고사 1회 1번
첫번째 시도
문제를 제대로 파악하지 못 함
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 1. 알파벳 카운트
// 2. 연속 여부 체크
import java.util.*;
class Solution {
static class Pointer {
int index = -1;
char pointer = '0';
public Pointer() {
}
public Pointer(int index, char pointer) {
this.index = index;
this.pointer = pointer;
}
public void setPointer(int index, char pointer){
this.index = index;
this.pointer = pointer;
}
public int getIndex() {
return this.index;
}
public char getPointer() {
return this.pointer;
}
public void setPointer() {
this.pointer = pointer;
}
}
public String solution(String input_string) {
String answer = "";
Pointer pointer = new Pointer();
ArrayList<Character> charList = new ArrayList<>();
Map<Character, Integer> map = new LinkedHashMap<>();
char[] charArray = input_string.toCharArray();
boolean flag = false;
for(int index = 0; index < charArray.length; index++){
// flag 상태를 체크해서, 중복이면 Map 포함시킨다.
flag = false;
// 반복문의 시작점인 i=0 인 경우
// 아직 Pointer 객체가 없기 때문에 처음으로 생성한다.
if (pointer.getIndex() == -1) {
pointer.setPointer(index, charArray[index]);
} else {
// 동일한 문자가 중복해서 나타나는 경우
if (pointer.getPointer() == charArray[index]) {
// 중복여부를 체크하는 변수의 상태 변경
flag = true;
}
// 중복된 문자가 아닌 경우
else {
// 현재 가리키고 있는 문자열로 업데이트
pointer.setPointer(index, charArray[index]);
}
}
if (flag) map.put(charArray[index], count(map, charArray[index]));
}
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + " & " + entry.getValue());
}
return answer;
}
public int count(Map<Character, Integer> map, Character pointer) {
int count = 0;
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
if (entry.getKey() == pointer) {
map.replace(entry.getKey(), entry.getValue() + 1);
count = entry.getValue() + 1;
}
break;
}
return count;
}
}
- previous, current 를 비교해야 한다
- 인덱스 값, 현재 값 을 담고 있는 객체를 만들자 😁
- 위 객체를 사용해서 연속하지 않음&중복해서 발생하는 값만을 Map 에 넣자 !
- 여기서 문제 발생 ❗
zczczc는 중복이 있지만 연속되지 않는 지 여부를 체크하지 않는다 😭
수정
- 굳이 Pointer 클래스를 생성할 필요가 없다는 생각
두번째 시도
문제의 조건을 다시 정리할 필요가 있다.
Map하나에 모든 필요한 정보를 담는다.- 불필요한 클래스 생성 금지
- 특정 글자가 현재 몇 번 출현했는지,
- 연속되는 상황인지 아닌지
- 판단하는 메서드를 작성해서 사용한다.
- stream API 를 활용한다.
- 특히 Map 컬렉션 사용 시
sort,filter,map은 코드를 굉장히 짧게 줄여준다. - Pointer 과 같이 필요한 정보를 담은 객체를 생성하고, getter, setter 를 만들어서 풀었을 때 굉장히
- 쉽게 풀리는 문제도 있었어서 끝까지 고집하다가 포기했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.*;
import java.util.stream.Collectors;
class Solution {
static Map<Character, Integer> map = new LinkedHashMap<>();
public String solution(String input_string) {
String answer = "";
char[] charArray = input_string.toCharArray();
char previous = charArray[0];
map.put(previous, 0);
char current = '-';
for (int i=1; i<charArray.length; i++) {
current = charArray[i];
// 연속되는 값이면
if (current == previous) {
calc(current, true);
}
// 불연속 값이면
else {
calc(current, false);
}
previous = current;
}
StringBuilder sb = new StringBuilder();
// map 의 key 를 알파벳 순서대로 정렬
List<Map.Entry<Character, Integer>> entries =
map.entrySet().stream()
// 한번 나왔으면 0, 한번 이상 나왔으면 1 을 저장했기에
// 0 이상, 즉 1인 값들만 filter 한다.
.filter(i -> i.getValue() > 0)
.sorted(Map.Entry.comparingByKey())
.collect(Collectors.toList());
// List 를 반복문을 돌며 StringBuilder 에 append
entries.forEach(entry -> {
sb.append(entry.getKey());
});
// 아무것도 포함되어있지 않다면, 중복되면서 연속적이지 않는
// 경우가 없었다는 뜻이므로 N 을 리턴한다.
if (sb.length() == 0) {
return "N";
} else {
return sb.toString();
}
}
/**
* 문제 기준 2번 이상 출현했고, 떨어져 있는 경우만 카운트하면 되므로
* 0 아니면 1 로 value 값을 저장했다.
* 만약 출현 빈도수 기준 정렬을 하는 문제였다면
* int count 변수를 선언해서, 기존에 map 에 있던 값에 +1 시켜주는 로직을
* 시키면 된다.
*
*/
public void calc(Character current, boolean flag) {
// 1. 기존 map 에 들어있는가?
if (map.containsKey(current)) {
// 2. 연속되는가?
if (flag) {
// 아무것도 하지 않는다.
} else {
map.put(current, 1);
}
}
// 기존 map 에 없다.
else {
// 근데 연속된다.
if (flag) {
map.put(current, 0);
}
// 연속되지 않는다.
else {
map.put(current, 0);
}
}
}
}
모의고사 1회 2번
문제 정리
- 각 반의 해당 종목 대표 1명
- 한 학생은 최대 한개의 종목만 대표
- 능력치의 합을 구해서 가장 최대가 되는 값을 구하라
- 학생 수는 최소 1명, 최대 10명
- 능력치는 최소 1, 최대 10000
정해진 시행횟수 안에서 최대값을 구한다
- DFS 로 완전 탐색?
- 부분합의 최대값?
- 메모이제이션을 활용한 DP?
DFS 채택 👌
이유
- 2차원 부분합 풀이 방법을 모른다.
- 메모이제이션을 활용할 방법이 안 떠오른다.
1차 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
static int answer = 0;
static boolean[] check;
public int solution(int[][] ability) {
// 방문을 체크할 배열
check = new boolean [ability.length];
// DFS 수행함수
permutation(0, ability[0].length, ability, 0);
return answer;
}
/**
* index : 현재 포인터 인덱스
* length : 운동 종목 개수
* ability : 종목 스코어
* sum : 전체 합
*/
public static void permutation(int index, int length, int[][] ability, int sum) {
// [종료조건] 전체 운동 개수에 대해서 탐색을 마친 경우
if(index == length) {
// 이번 시도에서 구해진 총합이 이전에 저장된 값보다 큰 경우
// 최대값을 구하기 문제이기에 최대값으로 갱신시킨다.
if(sum > answer) {
answer = Math.max(answer, sum);
}
return;
}
// 종목 개수만큼 반복한다.
for(int i = 0; i < ability.length; i++) {
// 아직 방문하지 않은 곳만 본다.
// = 아직 더하지 않은 운동 종목
if(!check[i]) {
// 이번 회차에 재방문하지 않기 위해서 방문여부를 true 로 변경한다.
check[i] = true;
// dfs 를 수행하는데,
// 다음 운동을 더해야하니까 index 를 1 만큼 증가시킨다.
// length : 고정값
// ability: 고정값
// sum : 학생 점수의 총합
permutation(index+1, length, ability, sum + ability[i][index]);
// i 번째 이후에 수행되는 모든 계산이 종료된 후
// 다시 i 를 거쳐야 하기에, i 분기점에 대한 계산이 아직 다 안끝난경우를 위해
// 방문여부를 false 로 돌려놓는다.
check[i] = false;
}
}
}
}
DFS 에서 나름 유명한 N-Queen 문제와 유사하다.
index 는 학생을, i 는 종목을 나타낸다.
index 와 i 를 증가시킨다.
문제의 조건에 따라서, 학생은 단 하나의 종목에만 출전이 가능하다. 즉, 어떤 행에 열의 값이 정해지면, 더 이상 그 행에는 값을 더할 수 없다. 결론적으로 Permutation 공식을 구현하되, 주어진 자료에 맞게 자료를 뽑아야 한다.
모의고사 1회 3번
특정한 규칙으로 n번 반복된다.
1차 시도
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.*;
class Solution {
// key: 세대
// value: 자식을 순서대로 담는 리스트
static Map<Integer, List<String>> map = new LinkedHashMap<>();
public String[] solution(int[][] queries) {
String[] answer = {};
// 1st generation data
map.put(1, Arrays.asList("Rr"));
int index = 1;
while (index++ < 4) {
nextGen(index, map.get(index));
}
for(Map.Entry<Integer, List<String>> entry : map.entrySet()) {
System.out.println(entry);
}
return answer;
}
public void nextGen(int n, List<String> gens) {
List<String> res = new ArrayList<>();
for (String gen : gens) {
List<String> t = new ArrayList<>();
switch(gen) {
case "RR": {
t.add("RR");
t.add("RR");
t.add("RR");
t.add("RR");
break;
}
case "Rr" : {
t.add("RR");
t.add("Rr");
t.add("Rr");
t.add("rr");
break;
}
case "rr": {
t.add("rr");
t.add("rr");
t.add("rr");
t.add("rr");
break;
}
default: {
// do nothing
}
}
res.addAll(t);
}
map.put(n, res);
}
}
아예 완벽하게 가게도를 그리고 나서, 찾으려고 한 시도의 흔적
2차 시도
역시 잘 안될때는 손으로 한번 적어봐야한다. 각각의 완두콩에 번호를 붙이니 뭔가 규칙이 좀 보인다. 그리고 항상 주의할 점은 배열의 인덱스는 0 부터 시작이라는 점이다. 문제에서 주어진 p 는 1부터 시작하는 값이라 -1 을 해주어야 배열의 인덱스와 일치 한다.
초록색 박스 안에 4로 나눈 나머지, 몫을 보면 확연한 규칙이 보인다. 4로 나눈 몫은 바로 전 세대 부모의 위치이고, 나머지는 현재 자신의 위치이다. 문제의 조건이 1 : 2 : 1 비율을 반드시 유지하므로, p 값을 4로 나눈 나머지가 0 혹은 3인 경우는 각각 Rr, rr 에 대응하고, 나머지는 Rr 값을 가질 것을 예상할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;
class Solution {
public String[] solution(int[][] queries) {
String[] rule = new String[]{"RR", "Rr", "Rr", "rr"};
String[] answer = new String[queries.length];
int idx = 0;
for(int[] query : queries) {
int level= query[0];
int count = query[1] - 1;
Stack<Integer> stack = new Stack<>();
if (level == 1) {
answer[idx] = "Rr";
idx++;
continue;
}
while (level > 1) {
int pointer = count % 4;
count /= 4;
level--;
stack.push(pointer);
}
while (!stack.empty()) {
String current = rule[stack.pop()];
if (current.equals("RR") || current.equals("rr")) {
answer[idx] = current;
break;
}
answer[idx] = current;
}
idx++;
}
return answer;
}
}
수능 등비급수 문제가 생각난다. 😭
모의고사 1회 4번
1차 시도
문제 정리
- 우선순위, 호출 순서에 따른 실행 순서
- 1~10까지 점수가 매겨져있고, 점수가 낮을수록 우선순위 높음
- 정해진 실행 시간이 정해져있고, 해당 시간 지난 후 프로그램 종료
- 우선순위가 가장 높은 프로그램부터 실행
- 프로그램이 호출되면, 자신보다 우선순위가 높은 프로그램들이 전부 실행되고 나서야 본인 실행
- 단, 본인보다 우선순위가 높은 프로그램이 껴들어도 그대로 실행된다
- 우선순위가 같다면 먼저 호출된 프로그램 실행
- 모든 프로그램이 종료되는 시간, 프로그램의 점수마다 대기시간의 합을 정수 배열에 담아서 리턴하시오
- 순서가 중요하다.
- 먼저 실행되면 먼저 종료된다.
Queue 인데, 순서가 중요하니 PriorityQueue 로 풀어야겠다는 느낌이 온다. 컴퓨터 구조 관련 책 읽었을 때, 실제로 프린터의 인쇄 대기열은 우선순위 큐로 구현되어 있다고 본 적이 있다.
- Comparator 로 배열을 정렬하고, 반복문으로 PQ 에 넣는다.
- 실행 상태인 프로그램을 담을 큐
- 실행 대기 상태인 프로그램을 담을 큐
- 2가지의 우선순위 큐가 필요하다.
- 실행의 종료를 감지하고, 그 다음 프로그램을 실행시키는 로직의 구현에 실패했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
class Solution {
public long[] solution(int[][] programs) {
long[] answer = {};
Queue<int[]> queue = new PriorityQueue<>();
Queue<int[]> waitQueue = new PriorityQueue<>();
Arrays.sort(programs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
int diff = o1[1] - o2[1];
// 호출 시간이 동일하다면, 점수 오름차순 정렬
if (diff == 0) {
return o1[0] - o2[0];
} else {
return diff;
}
}
});
// 우선순위 큐에 추가
// for (int[] program : programs) {
// pq.add(program);
// }
pq.add(pg);
int[] pg = programs[0];
int score = pg[0];
int prior = pg[1];
int time = pg[2];
pq.add(pg);
while(!pq.isEmpty()) {
// 로직
// 실행이 가능한 경우 큐에서 제거
// pq.remove();
}
return answer;
}
}
2차시도
시간에 따른 프로그램 실행 순서를 구현하는 것이 어려웠다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.*;
import java.io.*;
class Solution {
public long[] solution(int[][] program) {
long[] answer = new long[11];
// 실행큐는
// 우선순위 > 호출순서 기준으로 정렬
PriorityQueue<int[]> workingQueue = new PriorityQueue<>((o1, o2) -> {
if (o1[0] - o2[0] == 0) return o1[1] - o2[1];
return o1[0] - o2[0];
});
// 대기큐는 호출순서를 기준으로 정렬
PriorityQueue<int[]> waitQueue = new PriorityQueue<>((o1, o2) -> {
return o1[1] - o2[1];
});
for (int[] p : program) {
// System.out.println(p[0]);
waitQueue.add(p);
}
// 프로그램의 전체 실행시간
// while 문 실행과 동시에 증가해서 0 이 될 수 있도록 -1 로 세팅
// 탈출 조건 만나기 전까지 계속 누적시간 카운트
long totalProgramRunTime = -1L;
// 단일 프로그램의 실행시간
// while 문 내에서 새로운 프로그램 실행 시 업데이트 되는 값
int singleProgramRunTime = 0;
while(true) {
// [탈출조건]
// 실행큐 대기큐가 모두 비었고,
// 어떤 프로그램도 실행중이지 않은 경우
// while 문 종료
if (waitQueue.isEmpty() && workingQueue.isEmpty() && singleProgramRunTime == 0) {
break;
}
// ##### 실행시간 처리 #####
// 전체 프로그램의 실행시간 증가
totalProgramRunTime++;
// 특정 프로그램이 실행 중이므로
// 실행시간을 감소시킨다.
// 따라서 해당 값이 0 이되는 경우, 특정 프로그램이 실행을 마치고 종료된 것이다.
if (singleProgramRunTime > 0) {
singleProgramRunTime--;
} // 실행시간 처리 #####
// 대기큐에 있던
// 특정 프로그램의 호출시간이 현재 시간(누적시간 or 전체 프로그램의 실행시간)과 동일하다면
// 실행차례가 된 것이므로 대기큐에서 실행큐로 옮긴다.
while(!waitQueue.isEmpty() && waitQueue.peek()[1] == totalProgramRunTime) {
workingQueue.add(waitQueue.poll());
}
// 실행되고 있는 프로그램이 없고,
// 아직 실행할 프로그램이 남은 경우 프로그램을 실행한다.
if (singleProgramRunTime == 0 && !workingQueue.isEmpty()) {
// 가장 우선순위가 높은 프로그램을 찾는다.
// 우선순위 큐에 저장시켰기 때문에,
// 우선순위에 따라
int[] currentProgram = workingQueue.poll();
// 프로그램은 방해받지 않고 실행되어야 한다.
// 해당 우선순위를 갖는 프로그램의 실행시간 값을 업데이트한다.
singleProgramRunTime += currentProgram[2];
// answer 에는 프로그램 별 누적 실행시간이 아니라
// 우선순위에 따른 누적 실행시간이 기록되어야 한다.
// 현재까지의 실행시간, 즉 총 누적된 시간의 흐름에
// 프로그램이 호출되는 시간을 빼준다.
answer[currentProgram[0]] += totalProgramRunTime - currentProgram[1];
}
}
answer[0] = totalProgramRunTime;
return answer;
}
}
모의고사 2회
모의고사 2회 1번
풀기 전 메모
- 무조건 1칸씩 움직임
- 전진, 후진과 회전을 어떻게 묶어야 할까
보자마자 생각난 건 아직도 기억나는 행렬의 회전공식이었다. 코마신코코
dx_2 = dx_1 + dx dy_2 = dy_2 + dy
문제에서 주어진 각 상황마다 90, -90, 0, 180도를 대입하고, 이전위치 + 회전을 고려한 단위 이동 으로 점화식으로 풀면 된다고 생각했다.
하지만 행렬 계산을 해볼 필요도 없이, DFS, BFS 문제에서 자주 사용되는 dx, dy 배열을 선언하고 푸는 것과 동일하다.
Right, Left 는 각각 시계방향, 시계반대방향으로 진행하는 거라고 볼 수 있다. 수학적으로 풀면, 각도를 행렬식으로 풀면 일반식 이끌어내는 것은 어려운 일이 아니다. 하지만 프로그래밍에서는 2차원 좌표, x, y 만이 있고 각도에 따라 회전하는 것을 구현해주어야 하기 때문에 이런 간단한 문제에서는 배보다 배꼽이 큰 경우이다.
dx, dy 가 아닌 Map 으로 정의해서 풀거나, 위치 정보를 클래스로 정의하는 등 구현 자체는 여러 방법으로 가능하겠지만, 결국 달성하고자 하는 목적을 생각해보면 모두 번거로운 일이 된다고 생각한다 일반적으로 시계방향(Clock Wise) 를 정방향으로 잡는다. 2차원 좌표계에서는 1, 2, 3, 4 총 4개의 사분면으로 구분지을 수 있다. 따라서 360도를 이동해서 처음 위치로 돌아오면, 동일한 위치로 돌아온다. 다만, 얼마나 회전했는가에 대한 정보가 있어야하는 경우 수학적으로는 각도를 가지고 있으면 된다.
여기서는 각도에 관한 정보를 가지고 있기가 번거로우니 사분면의 정보를 기준으로 얼마나 회전했는지 기록한다.
R 로 이동하는 것을 사분면 이동이라고 보면 +1, L 은 아래 그림과 같이 사분면 3번 이동해야 하기에 +3 을 해야한다. G 는 그대로 직진, B 는 사분면 2개를 이동하기에 +2 를 해준다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int[] solution(String command) {
int x = 0;
int y = 0;
int dir = 0;
char[] comds = command.toCharArray();
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
for (Character com : comds) {
switch(com) {
case 'G':
x += dx[dir];
y += dy[dir];
break;
case 'B':
x += dx[( dir + 2 ) % 4];
y += dy[( dir + 2 ) % 4];
break;
case 'R':
dir = (dir + 1) % 4;
break;
case 'L':
dir = (dir + 3) % 4;
break;
}
}
return new int[]{x, y};
}
}
모의고사 2회 2번
메모
- 간단하게 정렬 -> 0번째, 1번째 원소 더하기 -> 다시 정렬
- 시간초과 ⛔
- Java 가 지원하는 Collection 중에서 순서를 간직한 채로 원소에 대한 접근이 간편한 것
- PriorityQueue ✅
- LinkedList
- LinkedHashMaop
우선순위큐에 어떤 원소를 집어넣으면, 지정한 순서로 원소가 정렬된다.
1
2
3
4
5
6
// (1) 우선순위가 낮은 순서
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// (2) 우선순위가 높은 순서
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
값을 추가하는 방법은 다음과 같다.
1
2
priorityQueue.add(1);
priorityQueue.offer(2);
이 때, 중요한 점은
- 내부 요소는 힙(Heap) 으로 구성
- 이진 트리(Binary Tree)
- 시간 복잡도는 (NLogN)
우선순위 큐는 힙으로 구성되어 있고, 새로운 원소가 추가되는 경우
- 부모와 비교해서 더 작으면 교환(swap) 과정이 이뤄진다.
값을 제거하는 방법은 다음과 같다.
1
2
3
4
5
6
// (1) 첫번째 값 반환, 없다면 null
priorityQueue.poll();
// (2) 첫번째 값 제거
priorityQueue.remove();
// (3) 초기화
priorityQueue.clear();
우선순위가 가장 높은 값을 확인하기 위해서는 peek() 메서드를 사용한다.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;
import java.util.stream.*;
class Solution {
static Queue<Integer> pq = new PriorityQueue<>();
public int solution(int[] ability, int number) {
int answer = 0;
for (int a : ability) {
pq.add(a);
}
while(number-- > 0) {
int a = pq.poll();
int b = pq.poll();
pq.add(a+b);
pq.add(a+b);
}
answer = pq.stream().reduce(0, (a, b) -> a + b);
return answer;
}
}
This post is licensed under CC BY 4.0 by the author.