java 코딩테스트 준비 (기본)

원래 나는 python으로 코딩테스트를 준비하고 있는데, 요새들어 종종 코딩테스트 언어가 java로만 제한된 기업들이 있어 java로 코딩테스트를 급하게 준비할 일이 생기곤 했다. (...) 이번에도 그런 일이 생겨서, java 코딩테스트 작성법을 아예 포스트로 정리를 하고자 한다.

기본 입출력

우선 기본적인 입출력을 할 줄 알아야 할 것이다.

• 입력 받기

    import sys
    a = int(input())
    a, b= map(int,input().split())
    tmp = list(map(int,input().split()))
    
    input = sys.stdin.readline

  이건 파이썬으로 코딩테스트를 칠때 사용하는 입력 방식이다. 자바에서는 다음과 같은 방식을 사용한다.

    import java.io.*;
    import java.util.*;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readline();
    String[] input = br.readline().split(" ");
    StringTokenizer st = new StringTokenizer(br.readLine());
    String A = st.nextToken();

  Scanner이나 System.in.read를 사용하는 것이 일반적이나, 코딩테스트용으로 빠르게 입력받기 위해서는 BufferedReader을 사용하며, StringTokenizer은 공백이 있는 경우 문자열이 공백처리를 땡겨 채우도록 하여 BufferedReader보다 더 빠르다고 한다. BufferedReader, InputStreamReader은 java.io에 속하고 StringTokenizer은 java.util에 속한다.

• 출력

    print(a)

  파이썬으로 출력은 다음과 같이 매우 간단하게 할 수 있다. 자바에서는 다음과 같은 방식을 사용한다.

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String str = "abc"; //출력 문자열
    bw.write(str);
    bw.newLine(); //줄바꿈
    bw.flush(); //남은 데이터 모두 출력
    bw.close(); //출력 스트림 아예 닫힘
    
    StringBuilder sb = new StringBuilder();
    sb.append("a");
    sb.append("b").append("\n");
    System.out.println(sb);

  System.out.println()이 일반적인 방법이나, StringBuilder을 활용해서 출력을 할 수도 있고 BufferedWriter을 활용해서 출력을 할 수도 있다.

• 비교
  n행 m열짜리 배열을 입력받고 그대로 출력한다고 가정하자. 먼저 python으로는 다음과 같을 것이다.

    n,m = map(int,input().split())
    graph=[list(map(int,input().splilt())), for _ in range(n)]
    
    for i in range(n):
    	for j in range(m):
      	print(graph[i][j], end=' ')
      print()

  이걸 java로 바꾸면 다음과 같다.

    import java.io.*;
    import java.util.*;
    
    public class main{
    	static int[][] arr = new int[301][301];
      public static void main(String[] args) throws IOException{
      	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer stk = new StringTokenizer(br.readLine()," ");
          
          int n = Integer.parseInt(stk.nextToken());
          int m = Integer.parseInt(stk.nextToken());
          
          //n, m 입력 받음
          
          for(int i=0; i<n; i++){
          	stk = new StringTokenizer(br.readLine(), " ");
              for(int j=0; j<m; j++){
              	arr[i][j] = Integer.parseInt(stk.nextToken());
              }
          }
       
       StringBuilder sb = new StringBuilder();
       for (int i=0; i<n; i++){
       	for (int j=0; j<m; j++){
          	sb.append(arr[i][j]);
          }
          sb.append('\n');
       }
       System.out.println(sb);
    }
    
  }

  java로 작성하니 정말 길다... 하지만 그나마 다행인건 프로그래머스에서 코테를 치면 입력부는 크게 신경쓰지 않아도 된다는 점인 것 같다(...)

    //1
    BufferedReader br = new BufferedReader(new InputStreamReadr(System.in));
    String [] input = br.readLine().split(" ");
    n = Integer.parseInt(input[0]);
    m = Integer.parseInt(innput[1]);
    
    for(int i=0; i<n; i++){
    	String input2 = br.readLine().split(" ");
      for(int j=0; j<m; j++){
      	graph[i][j]=Integer.parseInt(input2[j]);
      }
    }
    
    //2
    Scanner sc = new Scanner(System.in);
    
    n = sc.nextInt();
    m = sc.nextInt();
    sc.nextLine();
    
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
      	graph[i][j] = sc.nextInt();
      }
    }

  너무 길어서 앞 부분은 다 생략헀다(..) 아무튼 이런 방식으로 입력 받는 것도 가능하다. 위 방식은 띄어쓰기가 있는 경우인데, 만약 띄어쓰기 없이 들어간다면 바깥 for문에서 sc.nextLine()이나 br.readline()으로 전체 문자열을 받아준 후에, 안쪽 for문에서 graph[i][j] = str.charAt(j) - '0'을 해주면 된다.

문자열 다루기

python의 가장 강점이라함은 문자열 다루기에 있다고 할 수 있겠다. 그래서 문자열 문제는 항상 간단하게 풀었었는데(...) java로 풀려니 문자열을 어떻게 다룰지부터 걱정이 앞서서, java에서는 문자열 문제를 어떻게 다루는지 찾아봤다.

• 대문자, 소문자 판별

  Character.isLowerCase(x)
  Character.isUpperCase(x)
  
  Character.toUpperCase(x)
  Character.toLowerCase(x)

• Character 타입 판별

  Character.isAlphabetic(x)
  Character.isDigit(x)

• 특정 단어의 인덱스 값, 인덱스 값에 위치한 단어

  str.indexOf('W');
  str.charAt(idx);

• 알파벳만 필터링

  str = str.toUpperCase().replaceAll("[^A-Z]", "");

• 문자열 거꾸로

  String tmp = StringBuilder(str).reverse().toString();

• 문자열 나누기

  str = str.subString(7); //7 이후부터
  str = str.subString(5,12); //5부터 12까지

• StringBuffer

  StringBuffer sb = new StringBuffer();
  sb.append("abcdef");
  sb.insert(0, "a"); //해당 인덱스에 해당값 삽입
  sb.substring(0,4); //문자열 나누기 0부터 4까지
  sb.reverse(); //뒤집기
  sb.toString(); //String 형태로 변경

• 필터 조건 : Character타입으로 변환 후에 is 함수 또는 if 조건문 사용

• 중복 문자: indexOf() 활용하면 맨 처음에 발견한 것을 가져옴 -> 중복 제거에 유리함

• String : 불변객체, 새로 참조할때마다 새 메모리 참조. <-> StringBuilder : 가변객체.

• replace : chain형으로 여러번 사용 가능함 ex) tmp.replace("#","1").replace("*","0")

• String -> char : charAt(idx);(한 글자만) or toCharArray()(전체) 다만, 이때 특수문자나 공백도 인덱스에 포함되므로 주의할 것.

• char -> String : valueOf(변수); (char, char[] 둘 다 들어갈 수 있음) or Character.toString(변수); (이때는 char[]은 불가능함)

• StringBuilder의 경우 삭제는 deleteCharAt(인덱스)를 사용할 수 있다. delete(시작인덱스, 끝인덱스)를 사용해서 삭제할 수도 있다. 값을 변경하려면 setCharAt(인덱스, 문자)를 사용할 수 있다. 값을 삽입하는 것은 insert(인덱스, 문자)를 쓸 수 있고, setLength()를 사용해서 문자열 길이를 줄이거나 늘일(뒤가 공백으로 채워진다)수도 있다.

자료구조

• Array

  int[] arr = new int[5]; -> 빈 배열
  int[] arr = new int[]{1,2,3,4,5}; -> 값 넣어 초기화
  int[][] a = new int[2][4] -> 2차원 빈 배열

  Array의 경우가 길이가 고정된다. (length)
  배열의 복제는 clone()을 사용해줌. 정렬은 sort 사용.
  Arrays.copyOfRange(배열명, 시작점, 끝점)으로 배열에서 특정 범위를 자르고 다른 배열에 저장할 수 있음. (시작점 이상 끝점 미만)

  String str = "12345";
  String[] arr = str.split("");
  //[1,2,3,4,5]

  이런 방법으로 string -> array도 가능함.

• ArrayList

  	ArrayList<Integer> ArrList = new ArrayList<Integer>();

  복사되는배열.addAll(복사할배열) 을 사용해서 깊은 복사가 가능함. 인덱스가 있어서 검색에 용이함. 하나ㅏ씩 가져와서 배열에 넣는 경우, int는 list.get(i).intValue()를 사용해야함.

• List

  List<String> arrList = new ArrayList<>();

  add, get, size, contains, remove를 사용할 수 있음. 길이가 가변적.
  Collections.sort()를 이용해서 정렬 가능함.

• LinkedList
  addFirst, addLast, add, removeFirst, removeLast, remove, clear, size, hasNext, contains를 사용할 수 있다. 검색에는 부적합함.

• Set
  중복 허용하지 않음.
  hashSet : 순서필요x, treeSet : 정렬된값. LinkedHashSet : 저장순서유지함

  TreeSet<String> ts = new TreeSet<>();
  HashSet<String> hs = new HashSet<>(ts);

  add, contains, equals, isEmpty, size를 사용할 수 있다.

  • Set<String> set = new HashSet<String>();
    List<String> menuList = new ArrayList<>(set); 

    으로 set->list 변환 가능

• Iterator
  반복을 위해서 사용할 수 있음. -> set, map, queue에서 사용 가능

• Stack

  	Stack<Integer> stk = new Stack<>();

• Heap
  Priority Queue 생성자 -> Heap Tree의 형태 구현 가능

  PriorityQueue<Item> queue = new PriorityQueue<>(new Comparator<Item>(){
  public int compare(){(중략)
  }
  });
  
  	PriorityQueue<Integer> pq = PriorityQueue<Integer>(); //오름차순
  	PriorityQueue<Integer> pq = PriorityQueue<Integer>(Collections.reverseOrder()); //내림차순

  add, remove(가장 앞 원소)를 사용함. minHeap, maxHeap에 접근할때는 peak을 사용함.

• Queue

  	Queue<Integer> queue = new LinkedList<>();

  add, poll(꺼내기)을 사용할 수 있다.

• Deque

  	Deque<String> stack = new ArrayDeque<>();

  addFirst()(용량 제한이면 exception), fferFirst() (용량 제한이면 false), addLast, add, offerLast, removeFirst(비어있으면 exception), pollFirst(비어있으면 null), removeLast, pollLast,remove(첫번째 제거), poll(첫번째 제거), getFirst(제거x, 비어있으면 exception), peekFirst(제거x, 비어있으면 null), getLast, peekLast,peek(첫번쨰), removeFirstOccurrence(Object o) (앞에서부터 탐색해서 o와 동일한 첫 엘리먼트 제거.), removeLastOccurrence(Object o), element(첫번째 제거), addAll, push(앞에 추가), pop(앞을 제거), remove(Object o), contain(Object o)

• Map

  HashMap<String, String> map = new HashMap<String, String>

  put, get, containsKey, remove, size를 사용하라 수 있다.
  만약 배열의 인덱스를 int가 아니라 String이나 char으로 지정하고 싶을때는 다음과 같은 방법을 쓸 수 있음.

  Map<String, List<Integer>> map = new HashMap<>();
  if(map.containsKey(str) == false){
  	List<Integer> list = new ArrayList<>();
  	list.add(Integer.parseInt(info[4]));
  	map.put(str, list);
  }else{
  	map.get(str).add(Integer.parseInt(info[4]));
  }

  HashMap을 Value 기준으로 정렬하는 방식은 다음과 같다.

  • Entry 내장 함수

    Map<String, Integer> map = new HashMap<>();
    map.put("a"", 3);
    map.put("b", 2);
    map.put("c", 1);
    List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
    entryList.sort(Map.Entry.comparingByValue());

  • comparator

     List.sort(new Comparator<Map.Entry<String, Integer>>(){
     @Override
     public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2){
         return o1.getValue() - o2.getValue(); //오름차순
     }
     }

  • lambda

     entryList.sort((o1,o2) -> map.get(o1.getKey()) - map.get(o2.getKey())));

• Collections
  max, min, sort, reverse, frequency(갯수), binarySearch(리스트, 숫자) (최초로 검색된 인덱스, 없다면 숫자보다 큰 최초의 위치를 찾아서 -1을 곱하고 1을 빼서 반환)

정렬

python에서는 sort(key=lambda x:~)을 이용해서 정렬할 수 있는데, java에서는 comparator을 통해서 compare 함수를 override해주거나 lambda를 써주면 된다. (혹은 Collections를 활용할 수 있음)

• comparator

  Integer[] arr = {1,2,3,4,5};
  Arrays.sort(arr, new Comparator<Integer>(){
  	@Override
  	public int compare(Integer i1, Integer i2){
  		return i2-i1;
  	}
  });

• lambda
  이쪽이 더 간단하다.

  Integer[] arr = {1,2,3,4,5};
  Arrays.sort(arr,(i1,i2) -> i2-i1);

둘 다 return값은 음수, 양수, 0이 될 수 있다. 음수가 리턴되면 오른쪽 인자가 아래로 내려간다. 만약 s1,s2에 대해 s1-s2를 반환한다고 해보자. 이때 s1<s2라면 음수가 리턴되고, 이때 s2가 s1보다 밑으로 내려간다. s1>s2라면 양수가 리턴되고, 그렇다면 s1이 s2보다 밑으로 내려간다. 즉, 오름차순으로 정렬되는 것이다. 내림차순으로 정렬하고 싶다면 반대로 s1,s2에 대해 s2-s1을 반환하면 될 것이다.

• compareTo
  비교에는 compareTo를 사용할 수도 있다. 숫자를 사용하면 크다(1), 같다(0), 작다(-1)을 반환하나, 문자의 경우 다양하다.

  Integer x= 3;
  Integer y = 3;
  x.compareTo(y) //-1
  x.compareTo(3) //0
  x.compareTo(2) //1
  
  String str = "abcd";
  str.compareTo("abcd") //0
  str.compareTo("ab") //2
  str.compareTo("a") //3
  str.compareTo("c") //-2
  "".compareTo(str) //-4
  str.compareTo("zefd") //-25
  str.compareTo("zEFd") //-25
  str.compareTo("ABCD") //32

  문자열의 경우, 기준값에 비교대상이 포함되어있다면 문자열 길이의 차이값을 리턴해주는데, 같은 위치의 문자끼리만 비교하므로 다른 경우에는 아스키값을 기준으로 비교처리를 한다. 전혀 다른 문자열인 경우에도 아스키값을 기준으로 비교처리를 한다. 만약 대소문자를 무시하고 비교해주길 원한다면 compareToIgnorecase()를 사용하면 된다.