https://school.programmers.co.kr/learn/courses/30/lessons/64064
문제
- 입력으로 1차원 String 배열 user_id ( 1 <= user_id.length <= 8, 1 <= user_id[i].length() <= 8 (i = 0~ user_id.length), user_id의 각 원소는 서로 중복되지 않음, 알파벳 소문자와 숫자로만 구성됨)과
- 입력으로 1차원 String 배열 banned_id ( 1 <= banned_id.length <= user_id.length, 1 <= banned_id[i].length() <= 8 (i = 0~ user_id.length), 알파벳 소문자와 숫자와 '*'문자로 이루어짐, 각 아이디는 최소 한 개 이상의 '*'문자를 가짐, 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어갈 수 없음. ) 이 입력으로 들어옴.
- 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 상관 없이 동일하다면 같은 것으로 처리하여 하나로 셈.
- 제재 아이디 목록은 몇 가지의 경우의 수가 가능한지 return.
초기 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int answer = 1;
String[] user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
String[] banned_id = {"fr*d*", "*rodo", "******", "******"};
ArrayList<ArrayList<String>> list = new ArrayList<>();
for (int i = 0; i < banned_id.length; i++) {
ArrayList<String> temp = new ArrayList<>();
for (int j = 0; j < user_id.length; j++) {
for (int k = 0; k < user_id[j].length(); k++) {
if (user_id[j].length() == banned_id[i].length()) {
if ((banned_id[i].charAt(k) != user_id[j].charAt(k))
&& (!Objects.equals(Character.toString(banned_id[i].charAt(k)), "*"))) {
break;
}
if (k == user_id[j].length() - 1) {
temp.add(user_id[j]);
}
}
}
System.out.println();
}
list.add(temp);
}
System.out.println(list);
System.out.println(answer);
}
}예전에 풀었던 코드라 기억은 잘 안 나지만 대충 보고 해석해보자면
버퍼 스트림은 빼야 되는데 왜 안 뺐는지 모르겠다.
이 방법은 ArrayList를 이용해서 문제를 푸는 방법인 것 같다.
banned_id 배열을 기준으로 user_id 원소를 모두 돌며 banned_id 원소와 조건에 맞는 user_id 원소를 ArrayList에 추가해 가능한 모든 user_id를 해당 ArrayList에 추가한 후,
해당하는 banned_id 위치의 ArrayList에 만들어진 ArrayList추가하는 방식인 것 같다.
추가만 하고 이후 방법이 적혀있지 않아 이후 내용은 모르겠다.
또 다른 코드
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int answer = 0;
String[] user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
String[] banned_id = {"fr*d*", "abc1**"};
ArrayList<ArrayList<String>> result = new ArrayList<>();
Arrays.sort(user_id);
Arrays.sort(banned_id);
for (int i = 0; i < banned_id.length; i++) {
ArrayList<String> temp = new ArrayList<>();
ArrayList<String[]> id = new ArrayList<>();
for (int j = 0; j < banned_id[i].length(); j++) {
if (banned_id[i].charAt(j) != '*') {
String[] idTemp = new String[2];
idTemp[0] = String.valueOf(j);
idTemp[1] = String.valueOf(banned_id[i].charAt(j));
id.add(idTemp);
}
}
for (int j = 0; j < user_id.length; j++) {
if (banned_id[i].length() == user_id[j].length() &&
String.valueOf(user_id[j].charAt(Integer.parseInt(id.getFirst()[0]))).equals(id.getFirst()[1])) {
for (int k = 1; k < id.size(); k++) {
if (!String.valueOf(user_id[j].charAt(Integer.parseInt(id.get(k)[0]))).equals(id.get(k)[1])) {
break;
}
if (k == id.size() - 1) {
temp.add(user_id[j]);
}
}
}
}
result.add(temp);
}
String[] resultTemp = new String[result.size()];
for (int i = 0; i < result.getFirst().size(); i++) {
resultTemp[i] = result.getFirst().get(i);
for (int j = 1; j < result.size(); j++){
resultTemp[i] = result.getFirst().get(i);
}
}
System.out.println(answer);
}
}이 코드도 이전 코드와 같이 ArrayList를 이용하는 코드인 것 같다.
이유는 모르겠지만 user_id와 banned_id 배열을 오름차순 정렬한다.
banned_id 원소를 기준으로...
banned_id 원소에서 '*' 문자가 아닐 때만 banned_id 원소와 user_id 원소를 비교하여 ArrayList에 추가한다.
이후 코드는 솔직히 잘 모르겠다 뭐라고 쓴 건지 개판이다.
새로운 코드
import java.util.*;
class Solution {
static HashSet<HashSet<String>> result = new HashSet<>();
public static boolean check(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != '*' && s1.charAt(i) != s2.charAt(i)) {
return false;
}
}
return true;
}
public static void dfs(HashSet<String> hash, ArrayList<ArrayList<String>> list, int num, int size) {
if (hash.size() == size) {
result.add(hash);
}
if (num < size) {
ArrayList<String> temp = list.get(num);
for (int i = 0; i < temp.size(); i++) {
if (!hash.contains(temp.get(i))) {
hash.add(temp.get(i));
dfs(hash, list, num + 1, size);
hash.remove(temp.get(i));
}
}
}
}
public int solution(String[] user_id, String[] banned_id) {
int answer = 0;
ArrayList<ArrayList<String>> list = new ArrayList<>();
for (int i = 0; i < banned_id.length; i++) {
ArrayList<String> temp = new ArrayList<>();
for (int j = 0; j < user_id.length; j++) {
if (check(banned_id[i], user_id[j])) {
temp.add(user_id[j]);
}
}
list.add(temp);
}
dfs(new LinkedHashSet<>(), list, 0, banned_id.length);
answer = result.size();
return answer;
}
}
가장 먼저 나오는 check 함수는 이전에 단어 변환 문제에서 사용했던 함수를 수정하여 재사용했다.
두 문자열의 길이가 다르면 false를 리턴한다.
banned_id 원소의 현재 인덱스 위치의 문자가 '*'가 아닐 경우 user_id 원소의 인덱스 위치에 있는 문자와 비교하고 같지 않을 경우 false를 리턴한다.
모든 것을 통과할 경우 true를 리턴한다.
그리고 dfs 방식을 사용했다 이 코드도 단어 변환 문제에서 사용했던 함수를 가져와 수정했다.
이 함수를 설명하기 전 main 코드를 먼저 설명하겠다.
main 함수에서는 ArrayList를 이용하여 기존에 있는 배열을 간소화하였다.
banned_id 원소마다 ArrayList를 만들어 해당 제재 아이디에 사용될 수 있는 user_id를 check 함수를 이용하여 찾아내 arraylist에 추가한다.
해당 원소에서 사용될 수 있는 user_id를 모두 찾아낸 후에는 전체 ArrayList에 만들어진 ArrayList를 추가한다.
만들어진 ArrayList를 dfs의 매개변수로 이용한다.
dfs함수 설명
매개변수로 HashSet, ArrayList 등을 받는다.
여기서 ArrayList는 main함수에서 만들은 것을 쓴다.
HashSet을 이용하는 이유는 ArrayList를 사용하니까 중복되는 단어가 있는 것 같아서 방법을 바꿨다.
두 군데에 똑같이 들어갈 수 있는 단어가 순서가 바뀌어 나오는 것도 다른 배열로 취급하기 때문에 이 부분 처리를 위해 사용했다.
최종적으로 답이 되는 부분에 추가하는데 이 코드가 중요한 것 같다.
여기서 HashSet을 다시 사용한다.
HashSet<HashSet<String>> result = new HashSet<>();코드들을 모은 HashSet을 다시 한본 HashSet에 넣어 중복을 제거하는 것이다.
이렇게 중복을 두 번 걸쳐 제거하면 중복 없는 결과가 담긴 HashSet을 얻을 수 있다.
이 HashSet에 담긴 것은 중복 없는 결과이기 때문에 HashSet의 크기가 답이 된다.
근데 여기서 테스트 3번만 실패가 떴다.
최종 코드
import java.util.*;
class Solution {
static HashSet<HashSet<String>> result = new HashSet<>();
public static boolean check(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != '*'
&& s1.charAt(i) != s2.charAt(i)) {
return false;
}
}
return true;
}
public static void dfs(HashSet<String> hash, ArrayList<ArrayList<String>> list, int num, int size) {
if (hash.size() == size) {
result.add(new HashSet<>(hash));
}
if (num < size) {
ArrayList<String> temp = list.get(num);
for (int i = 0; i < temp.size(); i++) {
if (!hash.contains(temp.get(i))) {
hash.add(temp.get(i));
dfs(hash, list, num + 1, size);
hash.remove(temp.get(i));
}
}
}
}
public int solution(String[] user_id, String[] banned_id) {
int answer = 0;
ArrayList<ArrayList<String>> list = new ArrayList<>();
for (int i = 0; i < banned_id.length; i++) {
ArrayList<String> temp = new ArrayList<>();
for (int j = 0; j < user_id.length; j++) {
if (check(banned_id[i], user_id[j])) {
temp.add(user_id[j]);
}
}
list.add(temp);
}
dfs(new LinkedHashSet<>(), list, 0, banned_id.length);
answer = result.size();
return answer;
}
}
테스트 3번만 실패해서 찾아보니 hashSet에 만들어진 hash를 추가할 때 그냥 배열에 추가하는 것처럼 했더니 복사가 잘못 된 것 같다.
그래서 복사를 새로운 hastSet에 기존 hashSet 내용을 복사하여 넣었더니 통과가 됐다.
result.add(new HashSet<>(hash));'프로그래머스 문제 풀이 > 프로그래머스 (JAVA)' 카테고리의 다른 글
| JAVA 프로그래머스 Lv.3 표현 가능한 이진트리 (0) | 2025.03.19 |
|---|---|
| JAVA 프로그래머스 Lv.3 110 옮기기 (0) | 2025.03.12 |
| JAVA 프로그래머스 Lv.3 단어 변환 (1) | 2024.12.23 |
| JAVA 프로그래머스 Lv.2 이진 변환 반복하기 (0) | 2024.12.22 |
| JAVA 프로그래머스 Lv.2 JadenCase 문자열 만들기 (1) | 2024.12.21 |