본문 바로가기

Coding Test

 (134)
[Java] 프린터 큐 [1966번] https://www.acmicpc.net/problem/1966예제 입력131 054 21 2 3 46 01 1 9 1 1 1예제 출력1125문제 접근중요도는 1 ~ 9까지 존재가장 처음 문서를 0번째로 시작테스트 케이스 첫 번째 줄에는 문서의 개수 N, 몇 번째로 출력 되었는지 궁금한 M번째 문서테스트 케이스 두 번째 줄에는 N개 문서의 중요도가 주어짐문제 해결문서의 번호와 중요도를 저장하는 클래스를 만들어 Queue에 순차적으로 저장맨 앞의 문서의 중요도가 가장 높은 지 큐의 모든 데이터를 순회하며 확인가장 높은 중요도일 경우 꺼내고, 문서 출력 카운트 1증가, M번째 문서라면 반복문 종료가장 높은 중요도가 아닐 경우 가장 높은 중요도가 나올 때까지 뒤로 추가기존 풀이 [메모리 : 16264 KB ..
[Java] 에디터 [1406번] https://www.acmicpc.net/problem/1406예제 입력1abcd3P xLP y예제 출력1abcdyx예제 입력2abc9LLLLLP xLBP y예제 출력2yxabc예제 입력3dmih11BBP xLBBBP yDDP z예제 출력3yxz문제 접근문자열을 자르고 더하는 것으로 시도해보았지만 시간 초과 (0.3초)Stack을 사용하게 되면 시간 복잡도가 O(1)을 갖는다고 함문제 해결2개의 스택을 가지고 하나는 데이터 저장용, 하나는 출력용으로 사용L(커서 왼쪽 이동) 명령 : 1번 → 2번 스택 이동D(커서 오른쪽 이동) 명령 : 2번 → 1번 스택 이동B(커서 왼쪽 삭제) 명령 : 1번 스택 맨 위의 데이터 삭제P ?(? 데이터 삽입) 명령 : 1번 스택 데이터 추가모든 명령이 종료된 뒤 1번..
[Java] 스택 [10828번] https://www.acmicpc.net/problem/10828예제 입력114push 1push 2topsizeemptypoppoppopsizeemptypoppush 3emptytop예제 출력122021-101-103예제 입력27poptoppush 123toppoptoppop예제 출력2-1-1123123-1-1문제 접근제목 그대로 스택 구현 문제문제 해결Stack 클래스와 switch-case문 사용큐 문제처럼 별도로 구현해야하는 명령어는 없음기존 풀이 [메모리 : 21272 KB / 시간 : 220 ms]public static void main(String[] args) throws Exception{ Stack stack = new Stack(); StringBuilder sb = n..
[Java] 큐 [10845번] https://www.acmicpc.net/problem/10845예제 입력115push 1push 2frontbacksizeemptypoppoppopsizeemptypoppush 3emptyfront예제 출력1122012-101-103문제 접근제목대로 Queue를 이용하여 구현문제는 예제의 명령어는 모두 Queue의 메서드로 가능하지만, back의 명령을 처리할 메서드는 존재하지 않음문제 해결Queue와 switch-case문을 이용하여 구현back 명령의 경우 다음의 순서로 구현이 필요가장 마지막에 데이터의 앞에 있는 데이터들, 즉 n-1개의 데이터를 꺼냄(poll)다시 넣음(offer)가장 마지막의 데이터가 오면 출력(peek)가장 마지막 데이터도 다시 꺼내고 넣음 (poll and offer)기존..
[Java] 3의 배수 [1769번] https://www.acmicpc.net/problem/1769예제 입력11234567예제 출력13NO문제 접근알고 있는 3의 배수는 한 자리로 3, 6, 9 밖에 모름즉, X → Y로 변경할 때 10보다 작은 수가 될 때까지 변경을 해야한다는 의미출력10보다 작은 Y가 될 때까지 몇 번의 변경이 일어났는지 출력3의 배수인지 아닌지 YES, NO로 출력문제 해결10보다 클 경우 각 자리수를 모두 더하고 작아질 때까지 반복숫자인 형태로 계산하기 보다 String의 CharAt() 메서드를 이용하는 것이 더 효율적일 것으로 생각 됨기존 풀이 [메모리 : 20100KB / 시간 : 228ms]public static void main(String[] args) throws Exception{ Strin..
[Java] 단어순서 뒤집기 [12605번] https://www.acmicpc.net/problem/12605예제 입력13this is a testfoobarall your base예제 출력1Case #1: test a is thisCase #2: foobarCase #3: base your all문제 접근문자열을 입력 받아 공백 단위로 나눈 뒤 거꾸로 출력하는 문제문제 해결split으로 나눈 뒤 for문을 이용하여 마지막 인덱스부터 출력하는 방법1split으로 나눈 뒤 stack을 이용하여 마지막 알파벳부터 출력하는 방법2위 두 가지 방법으로 풀어보고 메모리, 시간, 구현 시 필요한 라인 수 비교기존 풀이 [메모리 : 13984 KB / 시간 : 116ms]public static void main(String[] args) throws Exc..
[Java] 막대기 [17608번] https://www.acmicpc.net/problem/17608예제 입력16697646예제 출력13예제 입력2554321예제 출력25문제 접근순서대로 막대를 넣은 뒤 가장 마지막에 보았을 때 보이는 막대의 개수를 출력하는 문제즉, 가장 마지막 막대의 높이를 기준으로 그보다 큰 막대들을 출력문제 해결Stack을 이용하여 푸는 간단한 문제Stack에서 pop을 하면서 나온 height와 maxHeight를 비교하여 height가 더 크다면 maxHeight를 height로 바꾸고 개수 카운팅기존 풀이public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamRe..
[Java] N과 M 12 [15666번] https://www.acmicpc.net/problem/15666 예제 입력13 14 4 2예제 출력124예제 입력24 29 7 9 1예제 출력21 11 71 97 77 99 9예제 입력34 41 1 2 2예제 출력31 1 1 11 1 1 21 1 2 21 2 2 22 2 2 2문제 접근 이전 인덱스를 시작값으로 설정하여 현재 인덱스 이전의 값이 나오면 안 됨문제 해결‘N과 M 11’에서 했던 것 처럼 중복 체크 필요Set을 사용할 경우 메모리, 속도의 효율성이 너무 떨어지기 때문에 LastUsed 변수를 사용하여 중복 체크⇒ 입력 받은 숫자들을 오름차순 정렬을 하기 때문에 중복 체크가 가능기존 풀이 [메모리 : 14432 KB / 시간 : 144 ms]static StringBuilder sb = n..

티스토리툴바