코딩테스트 힌트 문제 풀기 (프로그래머스, 백준) 자바
프로그래머스 짝수는 싫어요
IntStream을 활용해서 문제 해결
range()로 범위를 설정 -> 1부터 n까지 범위 설정을 위해 (1, n + 1)
filter()로 홀수만 선택 -> 하나씩 꺼내서 2로 나눈 나머지가 0이 아닌 수 (x -> x % 2 != 0)
toArray()로 배열에 담아 return
import java.util.stream.IntStream;
/**
* 프로그래머스
* 짝수는 싫어요
*/
public class Solution1 {
public int[] solution(int n) {
int[] answer = IntStream
.range(1, n + 1) // 범위 설정
.filter(x -> x % 2 != 0) // 필터로 홀수 선택
.toArray(); // 배열에 담기
return answer;
}
public static void main(String[] args) {
int[] answer;
Solution1 solution1 = new Solution1();
answer = solution1.solution(10);
for (int num : answer) {
System.out.print(num + " "); // 1 3 5 7 9
}
System.out.println();
answer = solution1.solution(15);
for (int num : answer) {
System.out.print(num + " "); // 1 3 5 7 9 11 13 15
}
System.out.println();
}
}
프로그래머스 숫자 문자열과 영단어
알파벳 문자열 배열을 생성 후 "zero" 부터 "nine"까지 담는다.
입력받은 문자열 s를 contains() 함수를 이용해 알파벳 배열에서 일치하는 값이 있는지 확인해서
일치한다면 replace() 함수를 이용해서 알파벳을 알파벳 배열에서의 index로 교체
/**
* 프로그래머스
* 숫자 문자열과 영단어
*/
public class Solution2 {
public int solution(String s) {
String[] alphabet = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
// 알파벳 배열에 알바벳 index가 영단어의 숫자와 동일하기 때문에
// 입력받은 문자열 s를 contains() 함수로 알파벳 배열에서 일치하면
// replace() 함수로 알파벳을 해당 알파벳 인덱스로 교체
// ex) 알파벳 "zero" 는 0번 인덱스이기 때문에 0으로 교체
for (int i = 0; i < alphabet.length; i++) {
if (s.contains(alphabet[i])) {
s = s.replace(alphabet[i], Integer.toString(i));
}
}
return Integer.parseInt(s);
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
String s1 = "one4seveneight";
System.out.println(solution2.solution(s1)); // 1478
String s2 = "23four5six7";
System.out.println(solution2.solution(s2)); // 234567
String s3 = "2three45sixseven";
System.out.println(solution2.solution(s3)); // 234567
String s4 = "123";
System.out.println(solution2.solution(s4)); // 123
}
}
백준 9012번 괄호
입력 데이터의 수 T가 주어졌기 때문에
반복문 for문으로 T 횟수 만큼 메소드를 동작시켜 진행
str.charAt(i)로 '(' 여는 괄호 일 때는 스택에 담고
stack.isEmpty()로 스택이 비어 있을 때 -> ')' 닫는 괄호 인데 스택에 '(' 여는 괄호가 없을 때 "NO" 리턴
이외에는 스택에서 '(' 여는 괄호 제거
마지막으로 스택이 비어 있으면 "YES", 입력 데이터가 '(' 여는 괄호만 들어와 스택이 비어 있지 않으면 "NO"
출력을 위한 삼항 연산자 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
// 문제 입력을 위한 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 출력을 위한 StringBuilder
StringBuilder sb = new StringBuilder();
// 입력 데이터의 수 T
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
sb.append(solve(br.readLine()));
if (i < T - 1) {
sb.append('\n');
}
}
System.out.println(sb);
br.close();
}
/**
* 스택에 담아서 문제 해결
*
* @param str 문자열
* @return "YES" or "NO"
*/
public static String solve(String str) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < str.length(); i++) {
char p = str.charAt(i);
if (p == '(') {
// 문자가 '(' 여는 괄호일 때 스택에 담기
stack.push(p);
} else if (stack.isEmpty()) {
// 스택에 비어 있을 때
// 즉, ')' 괄호가 나왔는 데 스택에 '(' 여는 괄호가 없을 때
return "NO";
} else {
// 그 외에 Stack에서 '(' 여는 괄호 하나 씩 제거
stack.pop();
}
}
// 스택에서 괄호를 모두 제어했으면 "YES",
// '(' 여는 괄호만 있어서 제거가 안 됐으면 "NO"
return (!stack.isEmpty()) ? "NO" : "YES";
}
}
백준 2830번 행성 X3
XOR 비트 연산을 하는 문제로 두 수의 XOR 연산은 쉬운 문제다.
하지만 해당 문제는 행성의 모든 거주민들의 친밀도의 합을 구하는 문제로
두 명이면 1번 연산으로 쉽지만, 세명일 경우 주민이 A, B, C라고 할 때 A와 B의 친밀도, A와 C의 친밀도, B와 C의 친밀도를 구해 더해야 하는 문제다.
예제 입력 2에서 보면 N = 3이고 행성의 주민은 7, 3, 5 이고, 이들의 친밀도 총 합은 12 이다.
7의 2진수는 = 111
5의 2진수는 = 101
3의 2진수는 = 011
행성 주민들의 XOR 연산은
(7, 5) = 010 => 2,
(5, 3) = 110 => 6,
(7, 3) = 100 => 4,
친밀도의 총 합은 12가 나온다.
행성 주민들의
2의 0승 자리는 1이 3개
2의 1승 자리는 1이 2개, 0이 1개
2의 2승 자리는 1이 2개, 0이 1개인걸 알 수 있다.
2의 0승 자리는 1이 3개이기 때문에 XOR 연산을 진행하면 모두 0이 나온다.
2의 1승 자리는 1이 2개, 0이 1개이기 때문에 XOR 연산을 진행하면 1이 나올 경우가 2개, 0이 나올 경우가 1개이다.
2의 2승 자리도 1이 2개, 0이 1개이기 때문에 XOR 연산을 진행하면 1이 나올 경우가 2개, 0이 나올 경우가 1개이다.
따라서 XOR 연산으로 1이 나오는 경우는 각 자리의 1의 개수와 0의 개수를 곱하면 구할 수 있게 된다.
2의 0승 자리는 1이 3개이기 때문에 1의 개수 = 3, 0의 개수 = 0으로 3 X 0 = 0,
2의 1승 자리는 1이 2개, 0이 1개이기 때문에 1의 개수 = 2, 0의 개수 = 1으로 2 X 1 = 2,
2의 2승 자리도 1이 2개, 0이 1개이기 때문에 1의 개수 = 2, 0의 개수 = 1으로 2 X 1 = 2
따라서 친밀도의 합은 다음과 같이 구할 수 있다.
(2의 0승 * 0) + (2의 1승 * 2) + (2의 2승 * 2) = 12
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main1 {
public static void main(String[] args) throws IOException {
// N의 범위가 1 <= N <= 1,000,000
// 1,000,000은 2진수 20자리기 때문에 배열 사이즈를 20으로 설정
int[] arr = new int[20];
long answer = 0L;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 행성 거주민의 수 N
// 행성 거주민의 수 만큼 반복문을 돌려서 연산
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine()); // 거주민 이름
int idx = 0; // 배열 자리 수
int tmp = 0;
while (num != 0) {
tmp = num % 2;
num /= 2;
// XOR 연산으로 1일 경우만 체크
if (tmp == 1) {
arr[idx]++;
}
idx++;
}
}
for (int i = 0; i < arr.length; i++) {
// (1L << i) 2의 i승
// arr[i] = 1의 개수
// (N - arr[i] = 0의 개수
answer += (1L << i) * arr[i] * (N - arr[i]);
}
System.out.println(answer);
br.close();
}
}
비트 연산인 1L << i 를 알지 못했다면 못 풀었을 것 같다.
다른 블로그들을 참고해서 겨우 풀 수 있었다.
백준 10807번 개수 세기
해시 테이블을 이용해서 문제해결
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Hashtable;
public class Main2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 정수의 개수 N
int N = Integer.parseInt(br.readLine());
// 입력 값 정수를 받을 배열
int[] arr = Arrays
.stream(br.readLine().split(" ")) // 공백으로 정수 구분
.mapToInt(Integer::parseInt) // int형으로 형변환
.toArray(); // 배열에 담기
int v = Integer.parseInt(br.readLine()); // 입력으로 주어지는 정수 V
// 해시테이블을 이용해서 문제 해결
// Key에는 입력 받은 정수들을 담고, Value에는 해당 정수가 몇 개 인지 count
Hashtable<Integer, Integer> ht = new Hashtable<>();
for (int i = 0; i < arr.length; i++) {
if (!ht.containsKey(arr[i])) {
// 배열에 있는 정수가 해시테이블에 Key로 존재하지 않을 때
// 해시테이블에 담고, count 는 1로 설정
ht.put(arr[i], 1);
} else {
// 배열에 있는 정수가 이미 해시테이블에 Key로 존재할 경우
// 해시테이블에 Value 값을 + 1
ht.replace(arr[i], ht.get(arr[i]) + 1);
}
}
// 삼항 연산자를 이용해 해시테이블에 Key가 존재하면 Value 출력
// Key가 존재하지 않으면 0 출력
System.out.println(ht.containsKey(v) ? ht.get(v) : 0);
br.close();
}
}