백준 6198 < 옥상 정원 꾸미기 > JavaScript

2023. 3. 17.·☕️ 커리어 & 인터뷰 준비/코딩 테스트

📍문제 링크

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

6198번: 옥상 정원 꾸미기

문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으

www.acmicpc.net

 

📍알고리즘 분류

- 자료구조
- 스택
 

📍문제 풀이

문제 요구사항은 쉽지만, N이 최대 8만에 달하기 때문에, O(N^2) 로는 해결할 수 없다
- 시간복잡도를 낮추기 위한 방법이 필요하다
 
배열을 순회하며
 
stack 길이만큼 반복문 수행
스택의 최신 값이 현재값보다 같거나 작으면, pop 실행,
아니면(가려져서 안보이므로) 종료
 
반복문 종료후 스택의 길이를 답에 더한다
그리고 스택에 현재 값을 push한다
 
이 과정에서 현재값마다, 이전 수들이 현재값보다 높으면 그만큼 답에 더해준다
즉,

/*
10  3  7  4  12  2
   +1  +1 +2     +1
   10  10  7     12
           10
*/

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const N = +input[0];
  const stack = [];
  let answer = 0;
  // 1부터 N까지 순회
  for (let i = 1; i < N + 1; i++) {
    while (stack.length > 0) {
    // 스택에 원소가 있고, 현재값이 스택 맨 위 값보다 크면, pop 실행을 반복
      if (stack[stack.length - 1] <= +input[i]) stack.pop();
      else break;
    }
    // 남은 스택 길이만큼 더하기
    answer += stack.length;
    // 스택에 현재값을 push
    stack.push(+input[i]);
  }
  console.log(answer);
});

 

📍리뷰

- Bigint를 사용하지 않아도 가능하다. 8만 * 8만 해도 64억이므로 커버 가능!
- number 원시값의 최대 (max integer)
2^53 - 1 : 약 900조

'☕️ 커리어 & 인터뷰 준비/코딩 테스트' 카테고리의 다른 글
  • 백준 2636 < 치즈 > JavaScript
  • 백준 14889 < 스타트와 링크 > JavaScript
  • 백준 14891 < 톱니바퀴 > JavaScript
  • 백준 1094 < 막대기 > JavaScript
지식물원
지식물원
지식이 자라는 식물원!
  • 지식물원
    지식물원
    지식물원
  • 전체
    오늘
    어제
    • 분류 전체보기 (510)
      • 🎨 프론트엔드 공부 (247)
        • JS & TS (86)
        • HTML & CSS (22)
        • React & Next (49)
        • Vue & Nuxt (22)
        • 기타 (68)
      • 🤓 기술 학습 & 공부 기록 (116)
        • Node.js (0)
        • Python (37)
        • 백엔드 (0)
        • 딥러닝 (1)
        • 컴퓨터 일반 (72)
        • 개발 인프라 (6)
      • 👨‍💻 프로젝트 경험 (6)
        • Work (0)
        • Toy (6)
      • ⚙️ 개발 팁 & 노하우 (21)
        • 프론트엔드 (6)
        • 기타 (15)
      • ☕️ 커리어 & 인터뷰 준비 (88)
        • 코딩 테스트 (88)
      • 📰 기술 트렌드 & 생각 정리 (4)
      • 📚 기타 (25)
        • 마케팅 (15)
        • 비개발서적 (10)
  • 블로그 메뉴

    • 태그
  • 링크

  • 공지사항

    • 모바일 접속 시 코드 하이라이팅 깨질 때
  • 인기 글

  • hELLO· Designed By정상우.v4.10.3
지식물원
백준 6198 < 옥상 정원 꾸미기 > JavaScript
상단으로

티스토리툴바