[구름LEVEL] Dance Dance Revolution

난이도	정답률
★★	-%

프리미엄 알고리즘 위클리 비타알고 시즌3 20년 3월 3주차

goorm

문제

DDR은 두 발을 이용하여 플레이하는 게임으로 버튼은 동시에 최대 2개까지만 누를 수 있지만, 해당 프로그램은 노래의 음과 박자에 맞춰 적절한 악보를 생성해주기 때문에 사람이 플레이할 수 있는 악보인지는 고려하지 않는다. 프로그램이 계산해준 악보를 사람이 플레이할 수 있는 악보인지 확인해보자!

입력 버튼 개수 N (1 ≤ N ≤ 500,000)

두 번째 줄부터 각 줄에는 눌러야 할 버튼과 해당 버튼을 눌러야 하는 시각이 주어진다.

사람이 플레이할 수 있는 악보라면 1을 없다면 0을 출력한다.

 

해결

key point, map사용. 시각을 key로 잡고 value값을 눌러야할 버튼 개수로 본다.

• 버튼 번호와 시각이 주어지면 해당 시각을 key로 잡고 value값을 증가시킨다.
• 그리고 증가시킨 버튼 개수가 2개를 초과하면 flg변수를 1로 갱신한다.
• 입력을 모두 받고나서 flg가 1이라면 0을 아니라면 1을 출력한다.

 

코드

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> m;
int n, flg;
int main() {
    scanf("%d", &n);
    for (int i = 0, a, b; i < n; i++) {
        scanf("%d %d", &a, &b);
        m[b]++;
        if (m[b] > 2) flg = 1;
    }
    if (flg)    printf("0");
    else printf("1");
    
    return 0;
}

고치기 전 코드

• 입력을 전부 받고나서
• 무작위 번호가 주어질 때마다 해당 번호의 value값이 2를 초과하는지 확인
• 2를 초과한다면 flg를 1로 갱신시키고 반복문을 나간다.
• 2를 초과하지 않는다면 계속해서 확인한다.
• 반복문을 나왔을 때 flg값이 1이면 0을 아니면 1을 출력한다.

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> m;
int n, flg;
int main() {
    scanf("%d", &n);
    for (int i = 0,a,b; i < n; i++) {
        scanf("%d %d", &a, &b);
        m[b]++;
    }
    map<int, int>::iterator iter;
    for (iter = m.begin(); iter != m.end(); iter++) {
        if (iter->second > 2) {
            flg = 1; break;
        }
    }
    flg ? printf("0") : printf("1");
    return 0;
}

 

후기

map iterator를 처음써봤다. vector배열 쓰던 것 처럼

for(int i = 0; i<m.size(); i++) 
    if(m[i]>2) ... 

위와 같이 접근했다가 runtime error가 떠서 배열에 잘못 접근하고 있음을 깨달았다... 

map사용할 때 잊지않기!!