2812:큰수만들기
시도1
처음 이문제를 봤을땐 stack으로 왜풀어야하는지 잘모르겠었다.
가장큰숫자가 되려면
각 숫자를 num[]에 저장한다고 가정했을떄
num[i-1] 과 num[i]를 비교하여 만약에 뒤에나오는것이 더 크다면
isPrint[i-1] = false;를 춰서 후에 이 boolean값이 true인 값들만 출력을 하려고했다.
O(n)으로가능하기에 이 풀이가 될줄알았다. 하지만
이렇게하면 순간순간만 비교하기때문에 나중가서 정말 큰값이 나오면 그 값을
무시해버리게된다. 그래서 stack을써야하는구나 라고 생각이 들었다.
큰값이 나올때까지 계속넣다가 큰값이 들어오면 이전값을 없애가면서
큰값과 비교를 하는것이 오큰수의 풀이방법과 비슷했다.
이풀이방법을쓰면 o(n)에 해결이 가능했었다
시도2
출력부분을 아래와 같이 작성했었다
while(!stack.isEmpty()){
result.push(stack.pop());
}
아래와 같이 코드를 짜게되면 stack에 들어간 모든 수가 출력된다
앞에서부터 n-k개만 출력해야한다
while(!result.isEmpty()){
bw.write(result.pop() + "");
}코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;
public class Main{
public static void main(String[] args) throws IOException {
//System.out.println과 bw은 속도차이가 꽤많이난다
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String input[] = br.readLine().split(" ");
//n자리의 숫자가 입력으로 들어올것이다
int n = Integer.parseInt(input[0]);
//k만큼 제거해라
int k = Integer.parseInt(input[1]);
//숫자를 char배열로 저장했다. 자리수가 배우크기때문에, int로 받으면 숫자 하나하나빼오기가 좀 불편하기에 char array로 받았다
char ch[] = br.readLine().toCharArray();
//stack을 선언하였다. 이전에 stack을 사용하여 이런문제를 o(n)으로 해결한 기억이 남아있어서 떠올릴 수 있었다
Stack<Integer> stack = new Stack<>();
//ch의 배열을 돌면서 체크를한다
for(int i=0;i<ch.length;i++){
// n-i: 미완료된 요소들의 수, stack.size() + n-i: 내가 지금까지 완성한, 출력으로 내보낼 글자 >= n-k: 채워야하는 수
// 예를들어 4자리를 채워야하는데 스택엔 두개있고 n-i가 2다 그상태에서 pop을 해버리면 4자리를 완성할 수 없기때문
//char -> int로 변환하여 값을 저장한다
int value = ch[i]-'0';
//비어있을떄 pop해선 안되며, peek에 접근하기 위해서도 empty여부를 체크해야한다
//현재value가 더 큰경우에만 pop을 해가며, 또한 자릿수가 부족하지 않은상황에서만 pop을 한다
//그렇게하면 큰수만을 앞에 위치시킬 수 있다
while(!stack.isEmpty()&& stack.peek() < value && stack.size() + n-i > n-k){
stack.pop();
}
//value가 peek보다 크든 작든 stack에는 넣어주어야한다. 그래야 그 다음값이랑도 비교할 수 있을테니깐
stack.push(value);
}
//n-k개만 출력을 해야한다
//stack에는 이상한값들도 쌓일수있다. 그렇기때문에 n-k개만 출력해야한다
//4 2
//1111 이 예시로주어지면 stack에는 1111이 모두 쌓이기때문이다
//그렇다고 stack의 최대사이즈를 2개로 정할수도없다. 그 뒤에 뭐가들어올지 모르기때문이다.
//우린 stack맨밑부터 n-k개를 출력하면된다
for(int i=0;i<n-k;i++){
bw.write(stack.get(i)+"");
}
bw.flush();
bw.close();
}
}개선할점
stack.size() + n-i > n-k 보단 cnt라는 변수 두고 pop할때마다 cnt++하는게 훨씬 간결하고 보기좋다
18258: 큐 구현
import java.io.*;
public class Main{
public static class Queue{
//입력조건에 맞추어 배열 최대 idx설정
final int MAX_IDX = 2000000+1;
int back = 0;//arr[back] = 입력을 여기에 받음
int front = 0;//arr[front] = 가장 첫값
//Queue를 구현할 자료구조
int arr[];
//생성자를 통해 동적할당해준다
Queue(){
arr = new int[MAX_IDX];
}
// 좌우로 긴 막대기를 상상하고 그 막대기에 값을 넣는다고 생각하자.
// 다음 입력을 받기위해선 back의 값을 추가시켜주어야한다
public void push(int x){
arr[back++] = x;
}
// 초기에 size=0인데 back-front = 0-0 = 0이다
public int size(){
return back - front;
}
// front는 긴 막대기의 왼쪽부분을 확인하는것을의미한다
// 긴 막대기의 왼쪽부분을 담당하는 변수가 front
// 긴 막대기의 오른쪽 부분을 담당하는 변수가 back
public int front(){
if(isEmpty()==1) return -1;
return arr[front];
}
// back method는 긴 막대기의 오른쪽 부분을 확인하는것을 의미한다
// 단, arr[back] = 입력들어올곳 이기때문에 이보다 한칸 이전을 확인해야한다
public int back(){
if(isEmpty()==1) return -1;
return arr[back-1];
}
// pop은 긴막대기의 왼쪽 부분의 값을 꺼내는 것을 의미한다
// arr[front]를하면 왼쪽 부분의 값을 가리키는것이기때문에 이를 꺼내올수있고
// ++을 통해 다음값을가리키도록 한다
public int pop(){
if(isEmpty()==1) return -1;
return arr[front++];
}
//back = front 같은 경우, 비어있다는 의미이다.
public int isEmpty(){
if(back == front) return 1;
else return 0;
}
}
public static void main(String[] args) throws IOException {
//System.out.println과 bw은 속도차이가 꽤많이난다
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Queue q = new Queue();
for(int i=0;i<n;i++){
String input[] = br.readLine().split(" ");
switch (input[0]){
case "push":
q.push(Integer.parseInt(input[1]));
break;
case "front":
bw.write(q.front() + "\n");
break;
case "back":
bw.write(q.back() + "\n");
break;
case "size":
bw.write(q.size() + "\n");
break;
case "pop":
bw.write(q.pop() + "\n");
break;
case "empty":
bw.write(q.isEmpty() + "\n");
break;
default:
break;
}
}
bw.flush();
bw.close();
}
}2164: 카드
입력이 500000까지라 q에 사용되는 배열도 500000 + 1 정도만 선언을했는데, push하는 과정에서 그 이상의 idx에 접근을 하게된다. 그래서 500000 * 2 +1만큼 배열을 선언해야했다.
import java.io.*;
public class Main{
public static class Queue{
//입력조건에 맞추어 배열 최대 idx설정
final int MAX_IDX = 1000000+1;
int back = 0;//arr[back] = 입력을 여기에 받음
int front = 0;//arr[front] = 가장 첫값
//Queue를 구현할 자료구조
int arr[];
//생성자를 통해 동적할당해준다
Queue(){
arr = new int[MAX_IDX];
}
// 좌우로 긴 막대기를 상상하고 그 막대기에 값을 넣는다고 생각하자.
// 다음 입력을 받기위해선 back의 값을 추가시켜주어야한다
public void push(int x){
arr[back++] = x;
}
// 초기에 size=0인데 back-front = 0-0 = 0이다
public int size(){
return back - front;
}
// front는 긴 막대기의 왼쪽부분을 확인하는것을의미한다
// 긴 막대기의 왼쪽부분을 담당하는 변수가 front
// 긴 막대기의 오른쪽 부분을 담당하는 변수가 back
public int front(){
if(isEmpty()==1) return -1;
return arr[front];
}
// back method는 긴 막대기의 오른쪽 부분을 확인하는것을 의미한다
// 단, arr[back] = 입력들어올곳 이기때문에 이보다 한칸 이전을 확인해야한다
public int back(){
if(isEmpty()==1) return -1;
return arr[back-1];
}
// pop은 긴막대기의 왼쪽 부분의 값을 꺼내는 것을 의미한다
// arr[front]를하면 왼쪽 부분의 값을 가리키는것이기때문에 이를 꺼내올수있고
// ++을 통해 다음값을가리키도록 한다
public int pop(){
if(isEmpty()==1) return -1;
return arr[front++];
}
//back = front 같은 경우, 비어있다는 의미이다.
public int isEmpty(){
if(back == front) return 1;
else return 0;
}
}
public static void main(String[] args) throws IOException {
//System.out.println과 bw은 속도차이가 꽤많이난다
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Queue q = new Queue();
// 12345...n
for(int i=1;i<=n;i++){
q.push(i);
}
//q사이즈가 1보다 큰 경우는 2부터시작이 되는데 아래에 pop을 두번하기때문에 최소 2보다는커야한다
//1이되는순간 출력한다
while(q.size()>1){
//카드를 버린다
q.pop();
//앞에있는 카드를 뒤로옮기는 작업을 진행한다
int val = q.pop();
q.push(val);
}
//마지막 남은 카드를 출력한다
bw.write(q.pop()+"");
bw.flush();
bw.close();
}
}덱
양쪽에서 삽입, 삭제가 가능한 자료구조
시도1
이런식으로 코드를짜면 양쪽에서 삽입/삭제가 제대로안된다
front에다 추가하고 back에다가도 추가하면 이동이되는게아니라
값이 덮어씌워진다
긴막대기가아닌, 긴막대기로 원을 만든다고 생각해보자
public static class Deque{
final int MAX_IDX = 100000+1;
int front = 0;
int back =0;
int arr[];
Deque(){
arr = new int[MAX_IDX];
}
public void push_front(int x){
arr[front++] = x;
}
public void push_back(int x){
arr[back++] = x;
}
public int isEmpty(){
if(front == back) return 1;
else return 0;
}
public int pop_front(){
if(isEmpty()==1) return -1;
return arr[front++];
}
public int pop_back(){
if(isEmpty()==1) return -1;
return arr[back--];
}
public int size(){
return back - front;
}
public int front(){
if(isEmpty()==1) return -1;
return arr[front-1];
}
public int back(){
if(isEmpty()==1) return -1;
return arr[back-1];
}
}덱 만들기
- size변수따로 만들기
- idx를 마이너스 해줄경우에는 결과가 마이너스될경우를 대비하여
+MAX_SIZE추가 arr[front]에 삽입하면됨.arr[front+1]front다음칸이 가장 첫번째 요소라고 할 수 있음arr[rear]에 가장마지막 요소가 있음arr[rear+1]에 삽입하면됨
코드
public static class Deque{
final int MAX_IDX = 100000+1;
// front와 rear가 값은 같지만 front는 front+1에 삽입,
// rear는 rear에 삽입하므로 값이 덮어씌워질 일 없다
int front = 0;
int rear = 0;
//size는 따로 선언하는게 직관적임
int size = 0;
int arr[];
//초기화
Deque(){
arr = new int[MAX_IDX];
}
//가로로 긴막대기에서 왼쪽에 삽입을 하려고한다
public void push_front(int x){
//front는 새로 삽입될 곳을 가리킨다
arr[front] = x;
//front-1을했을때 음수가 나올수있으므로 MAX_SIZE를 더해서 막는다
front = (front-1+MAX_IDX)%MAX_IDX;
//push를 했으니 덱의 size는 증가할것이다
size++;
}
public void push_back(int x){
//arr[rear]은 마지막 요소를 의미하니 그 다음칸에 추가를 시켜주고
//rear의 값을 업데이트해주어야한다
arr[(rear+1)%MAX_IDX] = x;
rear = (rear+1)%MAX_IDX;
//값을 넣었으니 size를 증가시켜준다
size++;
}
public int isEmpty(){
//rear 오른쪽으로 증가하고 front는 왼쪽으로 증가한다
//그래서 만나게 되면 비어있다고 본다.
if(rear == front) return 1;
else return 0;
}
//왼쪽에있는 요소를 빼려고한다
public int pop_front(){
if(isEmpty()==1) return -1;
//front값을 오른족으로 이동시킨다 -> 이전값 삭제가 됨
front = (front+1)%MAX_IDX;
//pop했으니 size를 줄여준다
size--;
//arr[front]는 원래 삽입될 곳을 가리키지만 이번의 경우
//front를 이동시키고, 이동시키전의 값을 return해야하기때문에 아래와같이 작성해도된다
return arr[front];
}
public int pop_back(){
//비어있는 상태에서 pop할순없으니 예외처리를 해준다
if(isEmpty()==1) return -1;
///마지막값을 출력하면 되지만, 그에따라 rear도 변경을 해주어야한다
int temp = rear;
//오른쪽에있는값을빼냈다고 치면 x좌표만생각했을때 -1이 되는것이 맞다
rear = (rear-1+MAX_IDX)%MAX_IDX;
size--;
return arr[temp];
}
public int size(){
return size;
}
public int front(){
if(isEmpty()==1) return -1;
//front는 추가될곳을 가리키기때문에 그것보다 한칸오른쪽을 출력하는게 맞다
return arr[(front+1)%MAX_IDX];
}
public int back(){
if(isEmpty()==1) return -1;
//rear는 마지막 요소를 가리키기 때문에 그대로 출력하면 된다
return arr[rear];
}
}
1021: 회전하는 수
- 다시풀어보기
import java.io.*;
import java.util.ArrayList;
public class Main{
public static void main(String[] args) throws IOException {
//System.out.println과 bw은 속도차이가 꽤많이난다
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String input[] = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
int arr[] = new int[m];
int count =0;
//ArrayList는 배열바탕이기때문에 remove나 add를 할때 최악의경우 o(n)이 걸리지만
//그래서 시간복잡도가 최대 o(n^2)될수있다. n번반복할테니까(입력수만큼)
//하지만 입력값이 50이하로 매우작기때문에 시간내에 통과할수있다
//이 문제에서는 중간에있는 원소를 삽입/삭제할수있는 자료구조를 찾아야하는게 첫번째 문제이다
String str[] = br.readLine().split(" ");
//입력을 받아놓는다. 받아놓고 매번 삭제,추가할것이기때문에 미리 받아놔야한다
for(int i=0;i<m;i++){
arr[i] = Integer.parseInt(str[i]);
}
//리스트에는 1~n까지의 숫자가 미리들어가있다고 가정한다
ArrayList<Integer> list = new ArrayList<>();
for(int i=1;i<=n;i++){
list.add(i);
}
for(int i=0;i<m;i++){
//list에 값으로 idx를 찾아주는 기능이 있다.o(n)정도 걸릴듯
int target_idx = list.indexOf(arr[i]);
//list.size가 홀수든 짝수든 /2를 해도된다.
//중간지점을 기준으로 잡을때는 항상 홀수와 짝수를 나눠서 생각해보자
int half_idx = list.size()/2;
// 등호를 붙이는 이유
// list.size()가 홀수, 짝수일때 경우를 생각해보자
// 0123 이면 4/2=2여서 왼쪽으로 두칸이나 오른쪽으로 두칸으로 같다
// 하지만 012 여서 3/2 = 1이면 왼쪽으로 한칸이동 오른쪽으로 두칸이동으로
// 왼쪽이 더 빠르다. 그렇기에 등호를 포함시켰다
if(target_idx<=half_idx){
for(int k=0;k<target_idx;k++){
//첫번째원소는 삭제될것이기에 미리 값을 받아놓았다
int temp = list.get(0);
//첫번째 원소 삭제
list.remove(0);
//맨뒤에 추가
list.add(temp);
//2번쨰 연산 count
count++;
}
}
else{
//list.size() - target_idx번 반복문을 돌려야하는이유는 예제를 만들어보면 쉽게 알 수 있다
//size가 4고 0123 일때 3은 한칸만 가면된다. 이를 식으로 만들어보면 아래와같다
for(int k=0;k<list.size() - target_idx;k++){
//맨뒤원소를 잠시 저장한다. 이 값을 삭제할거기때문에 임시저장이 필요하다
int temp = list.get(list.size()-1);
//맨뒤를 제거하고 앞에 추가해주면 한칸 밀린것같은 효과를 얻을 수 있다
list.remove(list.size()-1);
list.add(0, temp);
//3번째 연산 count
count++;
}
}
//앞의 작업들이 완료됐다는것은 idx=0으로 target 요소가 위치한다는 의미다.
//이경우에는 연산1을 통해 pop시킨다
list.remove(0);
}
bw.write(count+"\n");
bw.flush();
bw.close();
}
}
안녕하세요!