팁 ***

문제 유형

1. 네트워크 문제 : List<ArrayList<>>를 활용한 DFS (배열로는 단방향 이슈 해결하기 복잡)

2. 단어 한글자씩 변화 문제 : List<ArrayList<>>를 활용한 BFS 

3. 2차원 배열의 최단 경로 수 구하기 : DP(점화식) - 해당 위치의 경로 수 = 상측 경로 수 +  좌측 경로 수

4. 2차원 배열을 이용한 지도 문제 : DFS, BFS (상하좌우 이용)

 

치환

- 포함여부 확인 : st.contains(st)

- 문자열 치환 : st = st.replace(",", "/")

String[] arr = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
for(int i=0; i<10; i++) {
	if(s.contains(arr[i])) {
		s = s.replace(arr[i], StringUtil.fixNull(i));
	}
}

 

소문자인지 숫자인지 (정규식)

- "^[.]|[.]$" dot을 두번 뺀게 아니라 ^은 first index가 dot일 경우, |(이거나) $은 last index가 dot일 경우를 표현

//1번-------------------------------------------
char a1 = (a.charAt(0));
        	
if(Character.isLowerCase(a1)) continue;
else if(Character.isDigit(a1)) continue;

//2번-(정규식)------------------------------------
temp = temp.replaceAll("[^-_.a-z0-9]","");
System.out.println(temp);
temp = temp.replaceAll("[.]{2,}",".");
temp = temp.replaceAll("^[.]|[.]$","");

//정규식 비교
if (Character.toString(ch).matches("[a-zA-Z]")) {} // 한글자인경우
if ((st).matches("[a-zA-Z]+")) {} // 여러글자인경우
if(!Pattern.matches("^[0-9]*$", value1)) {}

//졍규식 분할
String tmp = st.split("[0-9]")[0];

//전화번호
String check = "\d{2,3}[- ]?\d{3,4}[- ]?\d{4}";

//이메일
String check = "^[A-Za-z0-9_\\.\\-]+@[A-Za-z0-9\\-]+\\.[A-Za-z0-9\\-]+$"

 

배열, 리스트 변환

//배열 -> 리스트
List<String> list = Arrays.asList(arr);

//리스트 -> 배열
String[] arr = list.toArray(new String[list.size()]);

//List<Integer> -> int[]로 변환
int[] arr = list.stream().mapToInt(i -> i).toArray();

//String -> char배열
char[] arr = st.toCharArray();
---------------------------------------------------------------------

//배열 정렬
Arrays.sort(arr);

//리스트 정렬
Collections.sort(list);
---------------------------------------------------------------------

//배열 출력하기
System.out.println(Arrays.toString(arr));

//리스트 출력하기
System.out.println(list.toString());
---------------------------------------------------------------------

//list에서 가장 큰 값 꺼내기
int max = Collections.max(list);
---------------------------------------------------------------------

//map의 value만 list로 만들기
ArrayList<Integer> list = new ArrayList<Integer>(map.values());

//map에 동일한 키가 있다면 value+1 없다면 0 (누적값 계산시 사용)
map.put(key, map.getOrDefault(key, 0) + 1);

조합 : nCr

// 백트래킹 사용
public class main {
	public List<String> resultList = new ArrayList<String>();
	
	@Test
	public void solution() {
		int[] arr         = {0,1,2,3,4};             // 배열 
		boolean[] visited = new boolean[arr.length]; //방문배열
		
		for(int r=1; r<arr.length; r++) { // 조합할 갯수 1개씩 증가하며 호출 1,2,..N개
			combination(arr, visited, 0, arr.length, r);
//			combination(배열, 방문배열, 시작위치, 배열길이, 조합갯수);
		}
		
		System.out.println(resultList.toString());
	}
	
	// nCr
	public void combination(int[] arr, boolean[] visited, int start, int length, int r) {
		
		if(r == 0) { // 조합할 갯수(r)를 다 돌았다면
			String combinationIndex = "";
			for(int i = 0; i < visited.length; i++) { // visited[true,false,true,false]
				if(visited[i]) { // 방문표시 참인것들의 모음 (0,1,...,12,012,..)
					combinationIndex += i;
				}
			}
			resultList.add(combinationIndex);
			//[0, 1, 2, 3, 4, 01, 02,..., 0124, 0134, 0234, 1234]
		}
		
		for(int s = start; s < length; s++) { // 시작위치 하나 증가하면, 조합갯수도 하나 줄인다.
			visited[s] = true;
			combination(arr, visited, s+1, length, r-1); // 한개를 선택한 상태로 나머지중에서 조합을 한다.
			visited[s] = false;
		}
	}
}

조합 >  비트연산자 사용

class Solution {
	public int solution(String[][] relation) {
		int col = relation[0].length;
		ArrayList<Integer> keyList = new ArrayList<Integer>();
		
		for(int key=1 ; key < (1<<col); key++) { // 1000(16) = 경우의 수 구하기 (1~15)
			System.out.println("key = " + key);
			if(!isMinimal(key, keyList)) {
				continue;
			}
			if(isUnique(key, relation)) {
				keyList.add(key);
			}
		}
		return keyList.size();
	}

	public boolean isUnique(int key, String[][] relation) {
		HashMap<String, Object> map = new HashMap<String, Object>();
		
		for(String[] record : relation) {
			String str = "";
			
			for(int i = 0; i < record.length; i++) {
				if((key & (1<<i)) !=0 ) { // key = 1010 / 자릿수 1,10,100,1000 일치하는지 확인
					str += record[i] +" ";
				}
			}
			
			if(!map.containsKey(str)) { // 중복여부 체크
				map.put(str, str);
			}else {
				return false;
			}
		}

		return true;
	}

	public boolean isMinimal(int key, ArrayList<Integer> list) {
		for (int item : list) {
			if ((item & key) == item) // 이미 존재하는 key라면 패스 (비트연산후 자기자신이 나와야 완전히 일치한 값이다.)
				return false;
		}
		return true;
	}

 

 

 

재귀함수(스택, DFS) 주의사항

public static void mathCal(int in) { //in 현재값
		for(int i=0; i<3; i++) {
			int tmp = in - baseArr[i]; //다음에 넘길값 (재귀들어가면 현재값으로 사용함)

			if(tmp == 0) { //종료조건
				count++;
				return;
			}
			
			if(tmp > 0) {
				mathCal(tmp); //재귀
			}
		}
		return;
	}

 

입력하기 위한 명령어

Scanner sc = new Scanner(System.in);
		
int num = sc.nextInt();

String text = sc.next(); //문자는 배열로 입력됨
text.charAt(0);

 

Collection, Map

Map을 for문 (EntrySet())

HashMap<String, Object> map = new HashMap<String, Object>();
for(Map.Entry<String, Object> e : map.entrySet()) {
    e.getKey();
    e.getValue();
}

문자열을 숫자, 문자 구분이 필요하며, 추가로 한자리/두자리 숫자 구분도 필요할 경우

숫자를 문자열로 생각하여, 숫자가 연속 두번 나올경우 붙여서 사용한다.

ex) 10S2D*3T

for(한글자씩){
   if(숫자라면){
      String st += 한글자(숫자) // "1" + "0" = "10"
   }else if(문자라면){  // "10S"
   }
}