1️⃣ 1번 외톨이 알파벳
charAt 과 for 문 사용
import java.util.*;
public class Solution {
public static String solution(String input_string) {
String answer = "";
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < input_string.length(); i++) {
char current = input_string.charAt(i);
// 새로운 구간이 시작될 때만 카운트
if (i == 0 || current != input_string.charAt(i - 1)) {
if (map.containsKey(current)) {
map.put(current, map.get(current) + 1);
} else {
map.put(current, 1);
}
}
}
StringBuilder sb = new StringBuilder();
for (char c = 'a'; c <= 'z'; c++) {
if (map.containsKey(c) && map.get(c) >= 2) {
sb.append(c);
}
}
if (sb.length() == 0) {
answer = "N";
} else {
answer = sb.toString();
}
return answer;
}
public static void main(String[] args) {
System.out.println(solution("edeaaabbccd")); // de
System.out.println(solution("eeddee")); // e
System.out.println(solution("string")); // N
System.out.println(solution("zbzbz")); // bz
}
}Queue 사용
import java.util.*;
public class Solution {
public static String solution(String input_string) {
String answer = "";
char tempChar;
int tempCnt = 0;
int repeatCnt = 0;
Queue<Character> q = new LinkedList<>();
HashMap<Character, Integer> originHm = new HashMap<>();
HashMap<Character, Integer> repeatChkHm = new HashMap<>();
ArrayList<Character> list = new ArrayList<>();
for (int i = 0; i < input_string.length(); i++) {
q.offer(input_string.charAt(i)); // e d e a a a b b c c d
}
while (!q.isEmpty()) {
tempChar = q.poll();
if (originHm.get(tempChar) == null) {
originHm.put(tempChar, 1);
repeatChkHm.put(tempChar, 1);
} else {
tempCnt = originHm.get(tempChar) + 1;
originHm.put(tempChar, tempCnt);
}
if (!q.isEmpty()) {
if (tempChar == q.peek()) { // 연속되는 알파벳이라면
repeatCnt = repeatChkHm.get(tempChar) + 1;
repeatChkHm.put(tempChar, repeatCnt);
}
}
}
for (char key : originHm.keySet()) {
if (originHm.get(key) != repeatChkHm.get(key) && originHm.get(key) > 1) {
list.add(key);
}
}
if (list.size() == 0) {
answer = "N";
} else {
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
}
answer = sb.toString();
}
return answer;
}
public static void main(String[] args) {
String input_string = "edeaaabbccd";
System.out.println(solution(input_string));
}
}2️⃣ 2번 체육대회
class Solution {
// 최댓값을 저장할 변수
private int maxScore = 0;
private int numStudents;
private int numSports;
private boolean[] visited;
public int solution(int[][] ability) {
int answer = 0;
numStudents = ability.length; // 학생 수
numSports = ability[0].length; // 종목 수
visited = new boolean[numStudents]; // 학생 선발 여부 체크 배열
// 0번 종목, 현재 점수 0점부터 시작
backtrack(0, 0, ability);
return answer;
}
private void backtrack(int sportIdx, int currentSum, int[][] ability) {
// 기저 사례: 모든 종목의 대표를 다 뽑았다면 최댓값 갱신 후 종료
if (sportIdx == numSports) {
maxScore = Math.max(maxScore, currentSum);
return;
}
// 모든 학생을 순회하며 현재 종목(sportIdx)의 대표로 세워봄
for (int studentIdx = 0; studentIdx < numStudents; studentIdx++) {
// 아직 대표로 선발되지 않은 학생인 경우
if (!visited[studentIdx]) {
visited[studentIdx] = true; // 대표로 선발 (방문 체크)
// 다음 종목(sportIdx + 1)의 대표를 뽑으러 재귀 호출
backtrack(sportIdx + 1, currentSum + ability[studentIdx][sportIdx], ability);
visited[studentIdx] = false; // 다른 경우의 수를 위해 선발 취소 (백트래킹)
}
}
}
}3️⃣ 3번 유전 법칙
class Solution {
public String[] solution(int[][] queries) {
// 1. 쿼리 개수만큼 결과 배열의 크기를 지정합니다.
String[] answer = new String[queries.length];
// 2. 반복문을 돌며 각 쿼리([n, p])에 대한 dfs 결과를 answer 배열에 담습니다.
for (int i = 0; i < queries.length; i++) {
int n = queries[i][0];
long p = (long) queries[i][1]; // p가 최대 4의 15제곱이므로 long 타입 변환이 안전합니다.
answer[i] = dfs(n, p);
}
return answer;
}
public String dfs(int n, long p) {
if (n == 1) return "Rr";
long parentP = (p - 1) / 4 + 1;
String parentType = dfs(n - 1, parentP);
if (parentType.equals("RR")) return "RR";
if (parentType.equals("rr")) return "rr";
long groupIdx = (p - 1) % 4;
if (groupIdx == 0) return "RR";
else if (groupIdx == 3) return "rr";
else return "Rr";
}
}4️⃣ 4번 운영체제
import java.util.*;
class Solution {
public long[] solution(int[][] program) {
// answer[0]: 모든 프로그램이 종료되는 시각
// answer[1]~answer[10]: 각 점수(1~10)별 프로그램들의 대기시간 합
long[] answer = new long[11];
// 대기 중인 프로그램을 관리할 우선순위 큐 (실행 대기 큐)
// 정렬 기준: 1순위 - 프로그램 점수 오름차순, 2순위 - 호출 시각 오름차순
PriorityQueue<int[]> waitingQueue = new PriorityQueue<>((o1, o2) -> {
if (o1[0] != o2[0]) {
return Integer.compare(o1[0], o2[0]);
}
return Integer.compare(o1[1], o2[1]);
});
// 1. 전체 프로그램을 호출 시각 기준으로 오름차순(작은값→큰 값) 정렬
Arrays.sort(program, (o1, o2) -> Integer.compare(o1[1], o2[1]));
long currentTime = 0; // 현재 시각
int programIdx = 0; // program 배열을 순회할 인덱스
int totalPrograms = program.length;
// 2. 모든 프로그램을 처리할 때까지 반복
while (programIdx < totalPrograms || !waitingQueue.isEmpty()) {
// 3. 현재 시각 이하로 호출된 모든 프로그램을 대기 큐에 입장하는 조건문
while (programIdx < totalPrograms && program[programIdx][1] <= currentTime) {
waitingQueue.add(program[programIdx]); // 대기실에 넣기
programIdx++; // 인덱스 1씩 증가
}
// 만약 대기 큐가 비어있다면 시간을 건너뛰는 조건문
// 첫번째 배열의 호출시간이 0보다 늦거나, 한 배열이 끝나고 다음 배열이 들어올 때까지 시간 공백이 길 때 필요
if (waitingQueue.isEmpty()) {
currentTime = program[programIdx][1];
continue; // 아래의 코드를 실행하지 않고 반복문의 처음 조건 검사 단계로 건너뜀
}
// 4. 대기 큐에서 우선순위가 높은 프로그램을 꺼내서 쪼개서
int[] currentProgram = waitingQueue.poll();
int score = currentProgram[0]; // 이 프로그램의 점수/우선순위
int callTime = currentProgram[1]; // 이 프로그램의 호출 시간
int executionTime = currentProgram[2]; // 수행하는데 걸리는 시간
// 5. 대기 시간 = 현재 시간 - 호출 시간
long waitTime = currentTime - callTime;
answer[score] += waitTime; // 해당 점수의 대기시간 누적
// 6. 프로그램이 수행되고 종료된 시간으로 현재 시간 업데이트
currentTime += executionTime;
}
// 마지막. 모든 while 문을 탈출한 직후 0번 방에 최종 마감 시각 저장
answer[0] = currentTime;
return answer;
}
}
개발일지