구르는 돌에는 이끼가 끼지 않는다

www.acmicpc.net/problem/1260

dfs와 bfs를 이해하기에 정말 좋은 문제였다. 

문제의 핵심은 각 알고리즘을 이해하고 이를 구현하는 방법을 이해 하는것이었다. 

dfs = stack 이고, 크게 재귀함수를 이용하거나, java에서 제공하는 stack 컬렉션을 사용한다. 

일반적으로는 재귀를 쓰는 것이 코드가 깔끔하여 재귀를 많이 쓴다. 

bfs = queue 이고, queue는 보통 java에서 제공하는 queue 인터페이스 사용하여 많이 사용한다. 

package com.ji.beakjoon;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class DfsAndBfs02 {
	
	static int nodeNum, edgeNum, startNode;
	static int[][] graph;
	static boolean[] DFSisVisited, BFSisVisited;
	static ArrayList<Integer> DFSvisitArr, BFSvisitArr ;
	static Queue<Integer> queue;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		nodeNum = sc.nextInt(); // 점갯수
		edgeNum = sc.nextInt(); // 선갯수
		startNode = sc.nextInt(); // 시작노드
		graph = new int[nodeNum + 1][nodeNum +1];
		
		DFSisVisited = new boolean[nodeNum +1];
		BFSisVisited = new boolean[nodeNum +1];
		DFSvisitArr = new ArrayList();
		BFSvisitArr = new ArrayList();
		queue = new LinkedList<Integer>();
		
		for( int i = 0 ; i < edgeNum ; i++ ) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph[a][b] = 1;
			graph[b][a] = 1;
		}
		
		for( int i = 0 ; i < nodeNum+1 ; i++) {
			DFSisVisited[i] = false;
			BFSisVisited[i] = false;
		}
		
		dfs(startNode);
		bfs(startNode);

		for( int i = 0 ; i < DFSvisitArr.size() ; i++ ) {
			System.out.print(DFSvisitArr.get(i) + " ");
		}
		System.out.println();
		for( int i = 0 ; i < BFSvisitArr.size() ; i++ ) {
			System.out.print(BFSvisitArr.get(i) + " ");
		}

	}
	
	static void bfs(int node) {
		// 방문한 노드 처리
		BFSisVisited[node] = true;
		// 방문한 노드 번호 리스트 저장
		BFSvisitArr.add(node);
		for( int i = 1 ; i <= nodeNum ; i++) {
			//간선이면서, 방문한 노드가 아니고, 검색해야할 노드 큐에 저장해준다.
			if( graph[node][i] == 1 && BFSisVisited[i] == false && queue.contains(i)==false) {
				queue.add(i);
			}
		}
		
		//검색 큐가 비어있지 않으면 검색 큐에서 삭제해준 후 제 검색
		if(!queue.isEmpty())
			bfs(queue.poll());
	}
	
	static void dfs(int node) {
		//방문한 노드 번호에 대한 boolean 처리
		DFSisVisited[node] = true;
		//방문한 순서에 대한 노드 정보 리스트 저장
		DFSvisitArr.add(node);
		for( int i = 1 ; i <= nodeNum ; i++ ) {
			if(graph[node][i] == 1 && DFSisVisited[i] == false) {
				dfs(i);
			}
		}
	}

}

https://programmers.co.kr/learn/courses/30/lessons/42584

문제 풀이에서 제일 어려웠던 부분은 

마지막 가격이 유지 안됬을 때의 예외 처리였습니다. 

테스트 케이스를 돌리면 한 끗차리로 결과가 맞지 않았습니다. 

이번에 풀면서 느낀 건 문제를 종이에 써가면 이해하려고 하니 조금 더 이해가 쉽게 되었다. 

마치 손으로 디버깅 하듯이 문제를 풀어 나갈 수 있어서 좋았던거 같습니다. 

앞으로 문제를 깊이 있게 이해하려는 노력을 해야겠습니다.

package com.ji.study;

import static org.junit.Assert.assertEquals;

import org.junit.jupiter.api.Test;

public class StockPriceTest {
	@Test
	void test() {

		StockPrice test = new StockPrice();

		assertEquals(new int[] { 4, 3, 1, 1, 0 }, test.solution(new int[] { 1, 2, 3, 2, 3 }));
		assertEquals(new int[] { 2, 1, 1, 0 }, test.solution(new int[] { 498, 501, 470, 489 }));

	}

}

public static int[] solution(int[] prices) {
		int[] answer = new int[prices.length];
		int count = 0;

		for (int i = 0; i < prices.length - 1; i++) {
			count = 0;
			for (int j = i + 1; j < prices.length; j++) {
				if (prices[i] <= prices[j]) {
					count++;
				} else {
					// 반대의 경우 값 유지 했기 때문에 count
					count++;
					break;
				}
			}
			answer[i] = count;
		}

		// 마지막 가격에 대한 상승/하강은 검사할 필요없음!!
		answer[prices.length - 1] = 0;

		return answer;
	}

1. jpql

String jpql = "select a from AccountLog a where ";
if (!vo.getSearchType().equalsIgnoreCase("all"))
jpql += JpqlQueryUtil.getWhereQueryByFileName(vo.getSearchType());

jpql += " a.logTime >= :startDate and a.logTime <= :endDate";

TypedQuery<AccountLog> typedQuery = em.createQuery(jpql, AccountLog.class);

if (!vo.getSearchType().equalsIgnoreCase("all")) {
typedQuery.setParameter("searchWord", vo.getSearchWord());
}

typedQuery.setParameter("startDate", DateUtils.parseDateFormatHHMMSS(vo.getStartDate() + " 00:00:00"));
typedQuery.setParameter("endDate", DateUtils.parseDateFormatHHMMSS(vo.getEndDate() + " 23:59:59"));

result = typedQuery.setFirstResult(vo.getPageNumber() - 1)
				   .setMaxResults(vo.getPageSize())
				   .getResultList();

2. QueryDSL

JPAQuery query = new JPAQuery(em);
QAccountLog accountLog = new QAccountLog("accountLog");

Date startDate = DateUtils.parseDateFormatHHMMSS(vo.getStartDate() + " 00:00:00");
Date endDate = DateUtils.parseDateFormatHHMMSS(vo.getEndDate() + " 23:59:59");

com.querydsl.core.types.Predicate condition = makeWhereQuery(vo, accountLog, startDate, endDate);

FetchableQueryBase queryBase = (FetchableQueryBase) query.from(accountLog)
														.where(condition)
                                                        .limit(vo.getPageSize())
                                                        .offset(vo.getPageNumber() - 1);
                                                                                            
result = queryBase.fetch();