잡지식

코딩테스트

클라스하이 2023. 7. 24. 14:44

오랜만에 코테를 풀어 봤는데 몇가지 습관을 들여야 겠다는 생각을 했다. 

 

아래 문제는 시간 0.15초, 메모리 256MB에 제한이 있는 문제다. 그냥 직관적으로 풀면 쉽게 답이 나오지만 사실은 시간초과로 바로 풀리지는 않는 문제다. 그냥 풀어버리면 시간 초과니 따로 모듈러 연산으로 규칙성을 찾으라는 문제인데 몇가지 키워드를 미리 확인했다면 이런 분류의 문제라는 걸 확인할 수 있는데 그냥 막 풀면 놓치기 쉽다. 그래서 뭔가 생각했어야 했다. 기계적으로... 

 

 

아

우선 위 문제를 보면 t가 200.000.000 라는 것을 체크 했어야 했다. 이게 시간 복잡도를 가늠할 수 있는 지표니까 대략 1초 1억개의 기본연산 기준이니까 O(n)이 되버리는 순간 이 문제는 시간초과로 못푼다. 그럼 O(1)로 만들어야 하는데 문제 구조상 뭔가 대칭의 형태가 보이고 반복적인 규칙이 있을거 같으니 이런건 직접 노트에다가 다 적어봐야 한다. 풀이 결과를 보면 X(t) = X(t+2W) 형태의 주기성을 가지고 있었고 주기성을 가지고 있다면 for문의 반복 횟수를 확! 줄일 수 있다. 그 외에도 공간복잡도는  w, h가 40000이니까 이걸 배열로 만들면 1.6GB인데 배열을 굳이 안쓸꺼니까 상관없다는 것도 체크하면 된다. 

 

밑의 내용은 요즘 듣는 강의에서 알려주는 내용인데 조금 정리해본다. 

올바른 문제풀이 순서

  • 읽기
    • 시간, 메모리 제한
    • 문제 전체를 꼼꼼히(키워드 체크)
  • 이해하기
    • 제공되는 정보(변수들) 정리(타입조심하기..)
    • 예제 데이터에 대해 이해(데이터가 어떻게 생겼냐?)
  • 파악하기
    • 가능한 최대, 최소 정답에 맞는 데이터를 직접 생성(데이터를 만들어보기)
    • 키워드가 되는 단어들을 체크
  • 추가로 테스트 케이스 좀 더 다양하게 해서 최종적으로 검증하기

 

자바 속도 쬐금이라도 줄이기

 I/O쪽은 어느 언어든지 시간을 많이 먹는 파트이다. 자바에서는 Scanner 연산을 기본적으로 쉽게 쉽게 사용하는데 이게 BufferedReader  보다 시간을 좀 더 많이 먹는편이라 만약에 반복적으로 입력을 받아야 한다면 Scanner 연산 보다는 BufferedReader 클래스로 입력을 받아야 한다. 

 

그리고 JAVA 8이 JAVA 11보다 조금 빠르다. 예를 들면 어떤 문제에서는 JAVA8에서 String의 덧셈 연산을 한 결과는 시간초과 없이 통과되나 JAVA11은 시간초과가 뜬다. 이것을 StringBuilder로 String 덧셈연산을 대체해서 시간을 줄일 수 있는데 진짜 이렇게 까지해서 풀어야 할 문제는 많이 없긴하다.

 

  • BufferedReader 사용
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int maxX=Integer.parseInt(st.nextToken());
int maxY=Integer.parseInt(st.nextToken());
	
// currPoint
st=new StringTokenizer(br.readLine());
int x=Integer.parseInt(st.nextToken());
int y=Integer.parseInt(st.nextToken());

// try		
st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
  • String + 연산 쓰지 말고 StringBuilder 사용하기
StringBuilder sb = new StringBuilder();
sb.append(x);
sb.append(" ");
sb.append(y);
// String + 연산은 매우 느리다. 
System.out.println(sb);

 

참고 >

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java