[JAVA] 백준 data structures - 골드모음(1351 무한 수열, 2493 탑, 5430 AC, 6198 옥상 정원 꾸미기)

 

1351 무한 수열 - 골드5

https://www.acmicpc.net/problem/1351

1351번: 무한 수열

 

일반적인 재귀방식은 시간이 너무 많이 들 것 같아 고민을 해봤다

1. 재귀방식으로 필요한 값들을 일단 찾음
2. 이미 구한 값들은 map으로 저장하여 다시 계산하지 않도록 함

 

class Main {
  private static Map<Long, Long> map = new HashMap<>();
  private static int p;
  private static int q;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    long N = Long.parseLong(st.nextToken());
    p = Integer.parseInt(st.nextToken());
    q = Integer.parseInt(st.nextToken());

    map.put(0L, 1L);

    System.out.println(dfs(N));
  }

  private static long dfs(long N) {
    if (map.get(N) != null)
      return map.get(N);

    long a = (long)Math.floor(N/p);
    long b = (long)Math.floor(N/q);

    if (map.get(a) == null)
      map.put(a, dfs(a));

    if (map.get(b) == null)
      map.put(b, dfs(b));

    return map.get(a)+map.get(b);
  }
}

 

• map에 0일 때 1이라는 걸 일단 저장
• dfs함수로 필요한 값을 재귀호출로 구하도록 한다
• 만약 map에 있는 값이라면 재활용하고, map에 없으면 dfs로 다시 들어간다

 

 

구글링을 해보니 대부분 나와 같은 풀이로 풀었다.

하나 알아낸 것: map.containsKey로 해당 값이 있는지 확인할 수 있음 -> null인지 체크없어도 된다

다음엔 이걸 써봐야겠다

 

 

 

2493 탑 - 골드5

https://www.acmicpc.net/problem/2493

2493번: 탑

 

• 왼쪽범위에서 나보다 높은 높이를 가지는 애 찾기
• 각각 자신의 왼쪽으로 가도 되겠지만 찾다가 시간초과가 날 것 같다
• 이 문제는 스택을 사용해야한다는게 바로 눈에 보여야함 (저는 안보였음 ㅎㅎ)

 

• 이렇게 정답을 구할 때마다 나보다 작은 애들을 삭제해주며 stack에 넣으면 된다
• 이유: 나보다 작은 탑이 왼쪽을 스캔할 때 어차피 나한테서 막힘
  • 나보다 앞에있고, 높이가 나보다 작은 애들한테 갈 일은 없음
  • 앞에있는 나보다 작은 애들을 삭제해도 상관이 없다
• stack에는 탑 높이와 탑의 번호를 저장하면 된다

 

풀이

class Building {
  int num;
  int height;

  public Building(int num, int height) {
    this.num = num;
    this.height = height;
  }
}

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Stack<Building> stack = new Stack<>();
    StringBuffer sb = new StringBuffer();

    int num = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());

    for (int i =1; i<=num; i++) {
      int h = Integer.parseInt(st.nextToken());
      int result = 0;

      while (!stack.isEmpty() && stack.peek().height <= h)
        stack.pop();

      if (!stack.isEmpty())
        result = stack.peek().num;

      stack.push(new Building(i, h));

      sb.append(result).append(" ");
    }

    System.out.print(sb.toString().strip());
  }
}

• 탑 높이와 번호를 저장할 Building 객체를 만들어줌
• Stack에 넣고 빼기를 반복
  • 스택이 비거나 && 나보다 큰 값을 만날 때까지 stack pop()
  • 마지막에 나를 push

 

 

5430 AC -  골드5

https://www.acmicpc.net/problem/5430

5430번: AC

 

• 배열느낌으로 값을 저장하고, 양 끝에서 데이터를 뺀다 -> deque 냄새가 남
• 앞에서부터 읽을지(삭제할지) 뒤에서 부터 읽을 지 저장하는 변수를 하나 저장하고
• deque로 조회 및 삭제를 수행하면 될 것 같다

 

풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();

    int tcCnt = Integer.parseInt(br.readLine());
    for (int t=0; t<tcCnt; t++) {
      String func = br.readLine();
      int cnt = Integer.parseInt(br.readLine());
      String numString = br.readLine();
      StringTokenizer st = new StringTokenizer(numString.substring(1, numString.length()-1),",");

      Deque<Integer> deque = new ArrayDeque<>();
      for (int i=0; i<cnt; i++)
        deque.add(Integer.parseInt(st.nextToken()));

      boolean isFirst = true; //deque 앞에서 뺄지 뒤에서 뺄 지 결정변수
      boolean isError = false;

      //연산 수행
      for (int i=0; i<func.length(); i++) {
        if (func.charAt(i) == 'R') { //뒤집기
          isFirst = !isFirst;
        } else { //버리기
          if (deque.isEmpty()) {
            isError = true;
            break;
          }

          if (isFirst)
            deque.removeFirst();
          else
            deque.removeLast();
        }
      }

      //출력
      if (isError)
        sb.append("error").append("\n");
      else {
        StringBuffer result = new StringBuffer();
        result.append("[");
        int size = deque.size();
        if (isFirst) {
          for (int i =0; i<size; i++) {
            result.append(deque.removeFirst());
            if (i != size-1)
              result.append(",");
          }
        } else {
          for (int i =0; i<size; i++) {
            result.append(deque.removeLast());
            if (i != size-1)
              result.append(",");
          }
        }
        result.append("]");

        sb.append(result).append("\n");
      }
    }

    System.out.print(sb);
  }
}

• 일단 deque에 입력값을 다 받는다
• 뒤집기와 버리기 연산을 수행한다
  • 뒤집기 -> boolean isFirst 변수를 다른 값으로 바꿔준다
  • 버리기 -> isFirst에 따라 앞에서 뺄 지 뒤에서 뺄 지 결정한다
  • 버리려고할 때 deque가 비어있으면 error를 true로 만들어주고 반복문을 끝낸다
• error나 deque에 있는 값을 isFirst 방향에 따라 읽어서 출력한다

 

 

출력코드가 좀 더러운 것 같다. (사람들도 출력하다 ac 하시는듯)

그래서 구글링 해보고 가장 좋은 방법을 찾아봤다.

=> 값을 하나 추가 후 [ "," + 값 ] 을 계속 추가하는 방법이 deque의 마지막 값인지 확인하는 과정을 거치지 않아도 되고 가독성도 좋음

 

 

 

 

6198 옥상 정원 꾸미기 - 골드5

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

• 사진이 있는 특이한 문제다! (나도 자런 옥상정원이 있는 곳에서 살고싶다)
• 빌딩 문제 -> 읽자마자 바로 스택냄새가 난다
• 오른쪽으로만 볼 수 있다 -> 이건 스택이다!

 

풀이법 설계

• 일단 빌딩들을 배열에 다 넣고, 역순으로 스택에 하나씩 넣는다
• 스택에는 (1)내 빌딩 높이와 (2)내가볼 수 있는 옥상 수를 가진 빌딩객체를 넣을 생각이다 
• 만약 스택에 나보다 작은 값이 있을 경우 계속 pop을 하고, 내가 볼 수 있는 옥상 수에 [ pop한 빌딩이 볼 수 있는 옥상 수 + 1 ]을 더한다
• 그림으로 그려보면 이런 느낌이다 

• 나보다 작은 빌딩이 스택에 있으면 < 빌딩이 볼 수 있는 옥상 수 + 1 > 을 내가 볼 수 있는 옥상 수에 추가
• 나를 스택에 push

 

• 계속 내가 볼 수 있는 옥상 수에 추가해준다~

 

풀이

class Building{
  int height;
  long canSee;

  public Building(int height, long canSee) {
    this.height = height;
    this.canSee = canSee;
  }
}

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int buildingCnt = Integer.parseInt(br.readLine());
    Building[] building = new Building[buildingCnt];
    for (int b=0; b<buildingCnt; b++)
      building[b] = new Building(Integer.parseInt(br.readLine()), 0L);

    Stack<Building> stack = new Stack<>();
    long result = 0;

    for (int b=buildingCnt-1; b>=0; b--) {
      Building tmp = building[b];
      while (!stack.isEmpty() && stack.peek().height < tmp.height) {
        Building pop = stack.pop();
        tmp.canSee += (pop.canSee + 1);
      }

      result += tmp.canSee;

      stack.push(tmp);
    }

    System.out.print(result);
  }
}

• 주의점:
  1. 같은 높이의 빌딩 옥상은 볼 수 없음 -> 같거나 높은 빌딩에서 끊기고, 같은 높이 옥상은 결과에 추가하지 않는다
  2. 볼 수 있는 빌딩의 수는 최대 80000+7999+7998+... == 6400000000 -> 절대 작은 숫자가 아님!

 

1. Building객체를 만들어 높이와 볼 수 있는 빌딩 수를 저장한다.
2. 빌딩을 다 받아서 배열에 저장한다
3. 배일 마지막 인덱스의 빌딩부터 스택넣기를 시작한다
   • 스택 peek() 의 높이가 나보다 작으면 pop()을 하면서 (pop빌딩이 볼 수 있는 옥상 수 + 1)을 내가 볼 수 있는 옥상 수에 추가한다
   • 스택 peek()의 높이가 나보다 크거나 같으면 pop을 종료한다
   • 옥상 수가 갱신된 현재 빌딩을 스택에 넣는다
   • 현재 빌딩이 볼 수 있는 옥상 수를 result에 추가한다
4. result를 출력