My Dev Blog

import java.util.Stack;

public class Solution {
	
	// 압축 문자열 풀기
	
	public static String solution(String compressed) {
		String answer = ""; // 최종 문자열을 담을 변수
		Stack<Character> charStack = new Stack<>(); // 영단어와 '(' 괄호를 담을 스택
		Stack<Integer> numStack = new Stack<>(); // 숫자를 담을 스택
		String tempStr = ""; // 임시 문자열을 담을 변수
		int tempNum = 0; // 임시 숫자를 담을 변수
		String repeatStr = ""; // 반복 문자열을 담을 변수
		StringBuilder sb = new StringBuilder(); // 문자열을 보다 효율적으로 이어주기 위한 StringBuilder
		
		for (int i = 0; i < compressed.length(); i++) { // compressed 한 글자씩 체크
			
			tempNum = 0; // 초기화
			
			if (compressed.charAt(i) >= '0' && compressed.charAt(i) <= '9') { // 1. 숫자라면
				
				while (compressed.charAt(i) >= '0' && compressed.charAt(i) <= '9') {
					tempNum = tempNum * 10 + compressed.charAt(i) - '0'; // 하나의 연속된 숫자라면 이전 숫자의 단위를 * 10하여 올리고 현재 숫자를 일의 자리로 더함
					i++; // 하나의 연속된 숫자라면 i 증가
				}
				
				i--; // while문 빠져나오기 전 마지막 i++가 있었으므로 다시 i--
				numStack.push(tempNum); // 숫자를 넘버 스택에 담기
			} else if (compressed.charAt(i) == '(') { // 2. 여는 괄호라면
				
				if (compressed.charAt(i - 1) >= '0' && compressed.charAt(i - 1) <= '9') { // 여는 괄호 전에 숫자가 있다면
					charStack.push(compressed.charAt(i)); // 여는 괄호 담기
				} else { // 여는 괄호 전에 숫자가 없다면 이것은 1이 생략된 것
					numStack.push(1); // 1을 넘버 스택에 담기
					charStack.push(compressed.charAt(i)); // 여는 괄호 담기
				}
			} else if (compressed.charAt(i) == ')') { // 3. 닫는 괄호라면
				
				tempStr = ""; // 초기화
				tempNum = 0; // 초기화
				sb.setLength(0); // 초기화
				
				if (!numStack.isEmpty()) {
					tempNum = numStack.pop(); // 가장 마지막에 들어온 숫자 꺼내기
				}
				
				while (!charStack.isEmpty() && charStack.peek() != '(') { // 여는 괄호가 아니면
					tempStr = charStack.pop() + tempStr; // 스택에서 꺼내며 임시 문자열 앞에 붙이기 // hi
				}
				
				if (!charStack.isEmpty() && charStack.peek() == '(') { // 여는 괄호면
					charStack.pop(); // 버리기
				}
				
				for (int j = 0; j < tempNum; j++) {
					sb.append(tempStr); // hihihihihihihihihihi
				}
				
				repeatStr = sb.toString();
				
				for (int k = 0; k < repeatStr.length(); k++) { // hihihihihihihihihihi
					charStack.push(repeatStr.charAt(k));
				}
				
				repeatStr = ""; // 초기화
				
			} else { // 4. 영단어라면
				charStack.push(compressed.charAt(i));
			}
		}
		
		while (!charStack.isEmpty()) {
			answer = charStack.pop() + answer;
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String compressed = "2(10(hi)co)";
		
		System.out.println(solution(compressed)); // hihihihihihihihihihicohihihihihihihihihihico
	}
}

프로그래머스 압축된 문자열 풀기 문제 풀이 Java

import java.util.HashMap;
import java.util.HashSet;

public class Solution {
	
	// 아이디 추천
	// S(3 ~ 6 길이 영 소문자) + N(0 ~ 6 길이 숫자) 조합의 아이디를 추천한다.
	
	public static String solution(String[] registered_list, String new_id) { // 등록된 아이디 배열, 신규 아이디
		String answer = "";
		int registeredStrEndIdx = 0; // 등록된 아이디의 S + N 조합에서 S의 마지막 인덱스를 담을 변수
		int newStrEndIdx = 0; // 신규 아이디의 S + N 조합에서 S의 마지막 인덱스를 담을 변수
		String tempStr = ""; // S 부분을 담을 변수
		int tempNum = 0; // N 부분을 담을 변수
		int recommendNum = 0; // 신규 아이디가 이미 등록되어 있을 경우 추천할 숫자
        
		HashMap<String, HashSet<Integer>> hmHs = new HashMap<>();
        
		// STEP 1. 등록된 아이디 체크하며 HashMap<String, HashSet<Integer>> 구조로 key와 value 담기
		for (String str : registered_list) { // 등록된 아이디 체크
        	
			for (int i = 0; i < str.length(); i++) {
        		
				if (str.charAt(i) >= '0' && str.charAt(i) <= '9') { // S + N 조합에서 N 시작(숫자 시작) 인덱스 확인
					registeredStrEndIdx = i - 1; // 영 소문자로 구성된 문자열 S의 마지막 인덱스
					break;
				}
			}
        	
			if (registeredStrEndIdx == 0) { // strEndIdx가 그대로라면! 즉, 등록된 이 아이디가 문자열로만 이루어져 있다면(S)
        		
				if (!hmHs.containsKey(str)) { // 이미 key 값으로 갖고있는 문자열 S인지 체크
					hmHs.put(str, new HashSet<Integer>()); // 없다면 문자열 S를 key로 넣고 value값을 담을 HashSet 생성
					hmHs.get(str).add(0); // 최초 card=[0]
				}
			} else { // 등록된 이 아이디가 영 소문자 문자열 + 숫자라면(S + N)
				tempStr = str.substring(0, registeredStrEndIdx + 1); // S
				tempNum = Integer.parseInt(str.substring(registeredStrEndIdx + 1, str.length())); // N
        		
				if (!hmHs.containsKey(tempStr)) { // 이미 key 값으로 갖고있는 문자열 S인지 체크
					hmHs.put(tempStr, new HashSet<Integer>());
					hmHs.get(tempStr).add(tempNum);
				} else {
					hmHs.get(tempStr).add(tempNum);
				}
			}
        	
			registeredStrEndIdx = 0; // 다음 등록된 아이디 확인 전 초기화
		}
        
		// hmHs => {ace=[16, 17, 13, 14], banker=[0], card=[0]}
        
		// STEP 2. 신규 아이디가 사용 가능한지 확인, 사용 불가하다면 아이디 추천받기
		for (int i = 0; i < new_id.length(); i++) {
        	
			if (new_id.charAt(i) >= '0' && new_id.charAt(i) <= '9') { // 숫자 범위라면
				newStrEndIdx = i - 1;
				break;
			}
		}
        
		if (newStrEndIdx == 0) { // newStrEndIdx가 그대로라면! 즉, 신규 아이디가 문자열로만 이루어져 있다면(S)
        	
			if (!hmHs.containsKey(new_id)) { // 신규 아이디이자, 아이디의 S가 등록된 아이디의 key로 존재하지 않아 그대로 사용 가능하다면
				answer = new_id; // 신규 아이디 S를 그대로 사용하도록 함
			} else { // 신규 아이디이자, 아이디의 S가 이미 등록되어 있다면
        		
				HashSet<Integer> tempHs = hmHs.get(new_id); // 뒤에 붙일 숫자 추천을 위해 HashSet 가져오기 // 이 경우 null이 담길 수 없음
        		
				// 1. HashSet은 null 값을 저장할 수 있다. 2. null과 isEmpty는 다르다.

				while(true) { // 숫자 추천을 위해 확인 반복 // 이 경우 신규 아이디가 이미 등록되어 있는 경우이므로 tempHs에는 null이 담겨있을 수 없기 때문에 null인 경우 무시
        			
					if (tempHs.contains(recommendNum)) { // 0부터 체크 // 해당 번호가 있다면
						recommendNum++; // 있다면 1 증가
					} else { // 0부터 체크 // 해당 번호가 없다면
            			
						if (recommendNum == 0) {
							answer = new_id; // S 그대로 사용하도록 함
						} else {
							answer = new_id + Integer.toString(recommendNum); // S + 추천 숫자
						}
						break;
					}
				}
			}
		} else { // 신규 아이디가 영 소문자 문자열 + 숫자라면(S + N)
			tempStr = new_id.substring(0, newStrEndIdx + 1); // S
			tempNum = Integer.parseInt(new_id.substring(newStrEndIdx + 1, new_id.length())); // N
    		
			HashSet<Integer> tempHs = hmHs.get(tempStr); // 없으면 HashSet에 null이 담긴다.
        	
			while(true) { // 숫자 추천을 위해 확인 반복
    			
				if (tempHs == null) { // HashSet은 null 값을 저장할 수 있기 때문에 isEmpty를 써선 안된다. // N을 그대로 사용 가능하다면
					answer = tempStr + Integer.toString(tempNum); // S + N
					break;
				} else {
    				
					if (tempHs.contains(tempNum)) { // 신규 아이디와 숫자가 이미 존재한다면
						tempNum++; // 숫자 1 증가
					} else { // 사용 가능한 숫자라면
						answer = tempStr + Integer.toString(tempNum); // S + N 또는 S + 추천 숫자
						break;
					}
				}
			}
		}
        
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] registered_list = {"card", "ace13", "ace16", "banker", "ace17", "ace14"}; // 배열 길이 1 ~ 100000
		String new_id = "ace15";
		
		System.out.println(solution(registered_list, new_id)); // ace15 // S(3 ~ 6 길이 영 소문자) + N(0 ~ 6 길이 숫자) 조합의 아이디 추천
	}
}

1. HashSet은 null 값을 저장할 수 있다.

2. null과 isEmpty는 다르다. (null : 인스턴스가 생성되지 않은 상태, isEmpty : 인스턴스는 생성되었으나 비어있는 상태)

HashMap<String, HashSet<Integer>> hmHs = new HashMap<>();

HashSet<Integer> testOneHs = hmHs.get("test"); // 이 경우 isEmpty가 아닌 null

HashSet<Integer> testTwoHs = new HashSet<Integer>(); // 이 경우 null이 아닌 isEmpty

프로그래머스 아이디 추천 문제 풀이 Java

import java.util.*;

public class Solution {
	
	// 애너그램 관계
	
	public static int solution(int[] arr) {
		int answer = 0;
		String tempStr = "";
		HashSet<String> hs = new HashSet<>(); // HashSet 사용
//		HashMap<String, Integer> hm = new HashMap<>(); // HashMap 사용
        
		for (int i = 0; i < arr.length; i++) {
        	
			char[] charArr = Integer.toString(arr[i]).toCharArray();
        	
			Arrays.sort(charArr); // 오름차순 정렬
        	
			tempStr = new String(charArr); // 문자열 생성
        	
			if (!hs.contains(tempStr)) {
				hs.add(tempStr);
				answer++;
			}
        	
//			if (!hm.containsKey(tempStr)) {
//				hm.put(tempStr, 1); // Integer 자리의 경우 1이 아니어도 됨
//				answer++;
//			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {112, 1814, 121, 1481, 1184, 512, 125, 521, 80}; // 단, 자리수는 같아야 함
		
		System.out.println(solution(arr)); // 4 // {112, 121}, {1814, 1481, 1184}, {512, 125, 521}, {80} // 4개의 그룹
	}
}

프로그래머스 애너그램 문제 풀이 Java

public class Solution {
	
	// 등굣길
	
	static int[][] dp = {};
	
	public static int solution(int m, int n, int[][] puddles) {
		int answer = 0;
		
		dp = new int [n][m]; // n행 m열
		
		dp[0][0] = 1; // 집
		
		for (int[] puddle : puddles) {
			dp[puddle[1] - 1][puddle[0] - 1] = -1; // 웅덩이 -1로
		}
		
		for (int i = 0; i < n; i++) { // 행
			
			for (int j = 0; j < m; j++) { // 열
				
				if (dp[i][j] == -1) { // 웅덩이라면
					dp[i][j] = 0; // 0으로 값 변경 후 continue
					continue;
				}
				
				if (i != 0) {
					dp[i][j] += dp[i - 1][j] % 1000000007;
				}
				
				if (j != 0) {
					dp[i][j] += dp[i][j - 1] % 1000000007;
				}
				
				// dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
			}
		}
		
		answer = dp[n - 1][m - 1] % 1000000007;
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int m = 4; // 열
		int n = 3; // 행
		int[][] puddles = {{2, 2}}; // 웅덩이 좌표 // 열, 행
		
		// (1, 1)에서 (4, 3)까지 최단경로 개수를 1,000,000,007로 나눈 나머지 리턴
		// 무조건 오른쪽 또는 아래쪽으로만 이동 가능 -> 최단 거리가 m + n - 3이라는 것도 알 수 있다.
		System.out.println(solution(m, n, puddles)); // 4
	}
}

프로그래머스 등굣길 문제 풀이 Java

import java.util.*;

public class Solution {
	
	// 단속카메라
	
	public static boolean intersactionCheck(int[] A, int[] B) { // 배열 A와 B가 교집합을 갖는지 확인
		int startA = A[0];
		int endA = A[1];
		int startB = B[0];
		int endB = B[1];
		int startPoint = 0;
		int endPoint = 0;
		
		startPoint = startA <= startB ? startB : startA; // 진입 지점은 둘 중 더 큰 지점
		endPoint = endA <= endB ? endA : endB; // 진출 지점은 둘 중 더 작은 지점
		
		if (startPoint <= endPoint) {
			return true;
		} else {
			return false;
		}
	}
	
	public static int solution(int[][] routes) {
		int answer = 0;
		
		Arrays.sort(routes, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[1] - o2[1]; // 진출 지점 기준 오름차순 정렬
			}
		});
		
		int cam = Integer.MIN_VALUE;
		
		for (int[] route : routes) { // 진출 지점 기준 오름차순 정렬된 상태
			
			if (cam < route[0]) { // 최초 무조건 if문에 걸리게 됨 // 다음 차량의 진입 지점이 카메라 위치보다 전이라면 설치할 필요 없고, 만약 설치한 카메라 이후 진입했다면 다시 설치를 위해 if문
				cam = route[1]; // 가장 작은 진출 지점에 단속용 카메라 설치 // 다음 차량의 진출 지점에 카메라 설치
				System.out.println(cam + "번 지점 단속용 카메라 설치");
				answer++; // 카메라 + 1
			}
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] routes = {{-20, -15}, {-14, -5}, {-18, -13}, {-5, -3}};
		
		System.out.println(solution(routes)); // 2 // -15, -5 설치
	}
}

프로그래머스 단속카메라 문제 풀이 Java

public class Solution {
	
	// 멀리 뛰기
	// 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다.
	// 칸의 수 n이 주어질 때 끝에 도달하는 방법이 몇 가지인지 알아내, 1234567로 나눈 나머지를 리턴하는 함수 solution을 완성하세요
	
	static int[] dpArr = {};
	
	// solve 함수는 solve(n) == solve(n - 1) + solve(n - 2) 조건을 만족한다.
	// 구하고자 하는 값이 solve(n) % 1234567 이고
	// (A + B) % C => ((A % C) + (B % C)) % C 이므로
	// (solve(n - 1) + solve(n - 2)) % 1234567 => ((solve(n - 1) % 1234567) + (solve(n - 2) % 1234567)) % 1234567 을 구하면 된다.
	
	public static int solve(int n) {
		
		if (n == 1 || n == 2) { // solve(1) == 1, solve(2) == 2
			return n;
		}
		
		if (dpArr[n] != 0) {
			return dpArr[n];
		}
		
		dpArr[n] = (solve(n - 1) % 1234567) + (solve(n - 2) % 1234567);
		
		return dpArr[n];
	}
	
	public static long solution(int n) {
		long answer = 0;
		
		dpArr = new int[2001]; // n은 1 이상, 2000 이하인 정수
		
		answer = (solve(n) % 1234567);
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(solution(4)); // 5
	}
}

(A + B) % C => ((A % C) + (B % C)) % C

프로그래머스 멀리 뛰기 문제 풀이 Java

import java.util.HashMap;

public class Solution {
	
	public static int[] solution(int[][] orders) {
		int[] answer = {};
		int studentCnt = orders.length; // 5
		int tempCnt = 0; // 후보의 현재 특표 수를 담을 임시 변수
        
		HashMap<Integer, Integer> nomineeHm; // 후보 번호 : 득표 수 담을 해시맵
		HashMap<Integer, Integer> dropHm = new HashMap<>(); // 탈락한 후보 번호 담을 해시맵
        
		int halfNum = 0; // 반수
        
		answer = new int[2]; // 회차, 후보 번호
        
		if (studentCnt % 2 == 0) {
			halfNum = studentCnt / 2; // 짝수일 경우 반수는 (학생 수 / 2)
		} else {
			halfNum = (studentCnt + 1) / 2; // 홀수일 경우 반수는 ((학생 수 + 1) / 2)
		}
        
		int checkCnt = 0; // 선거 카운트
        
		int rowNum = 0; // 탈락한 학생을 제외한 0순위 후보를 가져오기 위한 변수 (0부터 증가하며 체크)
        
		for (int j = 0; j < studentCnt; j++) { // 선거 회수 증가를 위한 반복문
        	
			nomineeHm = new HashMap<>();
        	
			for (int k = 0; k < studentCnt; k++) {
        		
				if (dropHm.get(k) != null) continue; // 후보에서 탈락한 학생이 있다면 그 학생을 제외하고 후보 등록
        		
				nomineeHm.put(k, 0); // 후보 등록 // 표를 얻지 못했더라도, 탈락된 후보가 아니라면 이번 회차의 당선 또는 탈락의 대상이 됨
			}
        	
			for (int i = 0; i < studentCnt; i++) { // 행
        		
				rowNum = 0; // 0순위 후보
        		
				while (dropHm.get(orders[i][rowNum]) != null) { // 0순위 후보가 탈락한 학생이라면 그 다음 순위 학생 체크 (탈락하지 않은 최대 우선 순위까지 체크)
					rowNum++;
					if (rowNum > studentCnt - 1) break;
				}
        		
				tempCnt = nomineeHm.get(orders[i][rowNum]);
				nomineeHm.put(orders[i][rowNum], tempCnt + 1); // 후보의 득표 수 증가
			}
        	
			checkCnt++; // 선거 카운트 증가
        	
			int[] dropNum = new int[2]; // 이번 회차에서 탈락할 후보의 번호, 득표 수를 담을 배열
        	
			dropNum[1] = studentCnt; // 5
        	
			for (int i = 0; i < studentCnt; i++) {
        		
				if (nomineeHm.get(i) == null) { // 이미 탈락한 후보라면 continue
					continue;
				} else { // 정상 후보라면
        			
					if (nomineeHm.get(i) >= halfNum) { // 반수를 넘었다면 최종 당선 후보(단, 반수를 넘은 학생이 2명 이상일 경우 후보 번호가 큰 학생이 당선 => 작은 번호부터 체크하기 때문에 이후에 반수를 넘은 다른 학생이 있다면 최종 당선 후보 변경)
						answer[0] = checkCnt; // 최종 선거 회차 담기
						answer[1] = i; // 당선 후보 번호 담기
					} else {
        				
						if (nomineeHm.get(i) < dropNum[1]) { // 현재 후보보다 득표 수가 적다면 탈락 후보 변경
							dropNum[0] = i;
							dropNum[1] = nomineeHm.get(i);
						}
					}
				}
			}
        	
			if (answer[0] == checkCnt) { // 최종 선거 회차가 담겼다면
				System.out.println(answer[0] + " " + answer[1]);
				return answer; // 선거 회차, 당선 번호 리턴
			}
        	
			dropHm.put(dropNum[0], 1); // 탈락한 후보의 번호 담기
		}
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] orders = {{2,3,4,0,1}, {1,4,3,2,0}, {4,1,0,2,3}, {3,2,1,4,0}, {0,3,2,1,4}}; // 4, 3
//		int[][] orders = {{2,1,0,3}, {3,2,0,1}, {3,0,2,1}, {2,3,0,1}}; // 1, 3
//		int[][] orders = {{2,1,0,3,4}, {4,2,0,1,3}, {3,0,4,2,1}, {2,4,3,0,1}, {4,1,3,2,0}}; // 4, 4 // {{2,1,3,4}, {4,2,1,3}, {3,4,2,1}, {2,4,3,1}, {4,1,3,2}} // 1차에 0 탈락 // {{2,3,4}, {4,2,3}, {3,4,2}, {2,4,3}, {4,3,2}} // 2차에 1 탈락 // {{2,4}, {4,2}, {4,2}, {2,4}, {4,2}} // 3차에 3 탈락 // 4차에 4 당선
		
		System.out.println(solution(orders));
	}
}

선거 회차 수가 증가할 때마다 탈락 또는 당선이 결정된다.

득표 수가 반수를 넘은 학생이 있다면 그 학생이 당선 후보가 되며, 반수를 넘은 학생이 2명 이상일 경우

번호가 더 뒤인 학생이 당선되는 룰을 따른다. 당선자가 결정되면 선거를 종료한다.

★이미 탈락한 후보가 아니라면, 표를 얻지 못했을 경우에도 이번 선거의 후보이며,

득표 수를 0으로 체크해야 한다는 점을 놓치면 안된다.★

프로그래머스 자비스앤빌런즈 2022 코딩테스트 선거 문제 풀이 Java

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	
	// 올바른 괄호
	
	static boolean solution(String s) {
		boolean answer = true;
		char tempChar;
        
		Queue<Character> q = new LinkedList<>();
        
		for (int i = 0; i < s.length(); i++) {
			
			tempChar = s.charAt(i);
			
			if (tempChar == '(') { // '('라면
				
				q.offer(tempChar); // 큐에 넣기
				
			} else { // ')'라면
        		
				if (q.isEmpty()) { // 이 시점에 큐가 비어있는 상태라면 짝이 맞지 않는 것이므로 answer = false 후 break
					answer = false;
					break;
				}
        		
				q.poll(); // 큐에 있는 '(' 괄호 꺼내기
			}
		}
        
		if (!q.isEmpty()) { // 짝이 맞았다면 '(' 괄호가 모두 제거되었어야 한다. 큐가 비어있는 상태가 아니라는 것은 짝이 맞지 않았다는 뜻이므로 answer = false
			answer = false;
		}
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "(())()";
		
		System.out.println(solution(s));
	}
}

큐 자료구조를 이용해 문제를 풀면 쉽게 풀리는 문제

프로그래머스 올바른 괄호 문제 풀이 Java