알고리즘 문제
퀵 정렬
시간복잡도평균적인 시간복잡도 = O(nlogn)
최악의 경우 = 이미 오름차순이나 내림차순으로 정렬이 되어있는 경우 = O(n^2)
구현 설계
1.
피벗(기준값)을 정한다 =⇒항상 배열의 [0]
2.
피벗의 왼쪽에는 피벗보다 작은 값이, 피벗 보다 오른쪽에는 피벗 보다 큰 값이 오게 한다.
3.
[작은값] 피벗 [큰값]으로 정렬되었을 때 다시 작은 값과 큰 값을 정렬한다.(재귀함수 이용)
import java.util.Arrays;
public class QuickSort {
public void sort(int[] arr,int st,int en){ //st=0 //en=arr.length-1
if (st>=en){ // st와en이 같다면 배열안에 1개의 값만 들어있다 ==> 탈출조건
return;
}
int pivot = st; //기준값을 각배열의 인덱스0으로 설정
int l = st+1; //st는 기준값이므로 다음인덱스부터 정렬
int r = en;
//엇갈리면 while문 종료
while (l<=r){
while(l<=en && arr[l]<=arr[pivot]){
// 배열의 왼쪽에서부터 pivot보다 큰값을 찾을때까지 l++;
l+=1;
}
while(r>st && arr[pivot]<=arr[r]){
// 배열의 오른쪽에서부터 pivot보다 작은값을 찾을때까지 r--;
r-=1;
}
if(l>r){ // 엇갈렸으면 r과 pivot의 위치를 바꾼다
// [5,4,2,0,3,1,6,9,7,8] ==> [1,4,2,0,3,5,6,9,7,8]
int tem= arr[pivot];
arr[pivot]=arr[r];
arr[r]=tem;
}else { // 엇갈리지 않았으면 l과 r의 위치를 바꾼다
//[5,7,9,0,3,1,6,2,4,8] ==> [5,4,9,0,3,1,6,2,7,8]
int tem=arr[l];
arr[l]=arr[r];
arr[r]=tem;
}
// [2,1,3,4,5,9,7,6,8]
sort(arr,st,r-1); //분할 후 pivot의 왼쪽 부분
sort(arr,r+1,en); //분할 후 pivot의 오른쪽 부분
// [2,1,3,4,5,9,7,6,8]
}
}
public static void main(String[] args) {
int[] arr = {1,3,2,8,6,2,4};
QuickSort q = new QuickSort();
q.sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
// 출력값==> [1, 2, 2, 3, 4, 6, 8]
}
}
Java
복사
spring
•
ArticleRestControllerTest
@WebMvcTest(ArticleRestController.class)
class ArticleRestControllerTest { // [1]
@Autowired //[2]
MockMvc mockMvc; //[3]
@MockBean // [4]
ArticleService articleService;
@Autowired
ObjectMapper objectMapper; //[5]
@Test
@DisplayName("아티클 잘 등록 되는지")
void addArticle() throws Exception {
ArticleAddRequest dto = new ArticleAddRequest("제목입니다","내용입니다");
ArticleAddResponse resp = new ArticleAddResponse(1l,dto.getTitle()
,dto.getContent());
given(articleService.addArticle(any())).willReturn(resp);
mockMvc.perform(post("/api/v1/articles") //[6]
.contentType(MediaType.APPLICATION_JSON)
.content(objectMapper.writeValueAsBytes(dto))
)
.andExpect(status().isOk())
.andExpect(jsonPath("$.id").exists())
.andExpect(jsonPath("$.title").exists())
.andExpect(jsonPath("$.content").exists())
.andDo(print());
}
}
Java
복사
어노테이션 & 메소드 설명
•
ArticleRestController
@RestController // [1]
@RequestMapping("/api/v1/articles")
public class ArticleRestController {
private final ArticleService articleService;
public ArticleRestController(ArticleService articleService) {
this.articleService = articleService;
}
@PostMapping
// [2]
public ResponseEntity <ArticleAddResponse> addArticle(@RequestBody ArticleAddRequest dto){ //ResponseEntity
return ResponseEntity.ok().body(articleService.addArticle(dto)); // entitiy.ok
}
}
Java
복사
어노테이션 & 메소드 설명
•
ArticleService
@Service
public class ArticleService {
private final ArticleRepository articleRepository;
public ArticleService(ArticleRepository articleRepository) {
this.articleRepository = articleRepository;
}
public ArticleAddResponse addArticle(ArticleAddRequest dto){
//dto를 Entity로
Article savedArticle = articleRepository.save(dto.toEntity());
return Article.of(savedArticle);
}
}
Java
복사
어노테이션 & 메소드 설명
•
Article
@Builder
@Getter
@Entity
@Table(name = "article3")
@AllArgsConstructor
@NoArgsConstructor
public class Article {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String title;
private String content;
public static ArticleAddResponse of(Article article){
return new ArticleAddResponse(article.getId(), article.getTitle(), article.getContent());
}
}
Java
복사
어노테이션 & 메소드 설명
